0

对于所有长度为 36 的三进制数（包括以 0 开头的三进制数），有多少个具有完全相同的 1 和 2 计数，或者恰好多 1 比 2？

例如：

  • 00 - 是
  • 01 - 是的
  • 02 - 没有
  • 10 - 是的
  • 11 - 没有
  • 12 - 是的
  • 20 - 没有
  • 21 - 是的
  • 22 - 没有

因此，对于所有长度为 2 的三进制数，9 种可能性中有 5 种匹配。这大概会随着长度的增加而变小。对于长度 3，27 个中有 13 个。

如果我们正在处理二进制数，这里有许多可用的解决方案，但我不清楚如何将这些推广到三进制数。

4

2 回答 2

1

作为一个组合练习，这个过程似乎很简单。对于 [1..18] 中的每个 N，在 36 位三元串中找到“1”的所有不同排列。然后将其乘以 N“2”在未被“1”占据的位置上的不同排列的数量，对于 N-1 个“2”也是如此。求这 36 个数字的总和。毕竟，为 N=0 添加 1，这是所有“0”的三元串。

在一个 36 长的 tritstring 中 N 个 trit 的不同排列的数量应该是

36! / N!(36-N)!

这个问题听起来像是一个脑筋急转弯。我没有进一步开发上述内容，但我高度怀疑存在快捷方式。

于 2009-01-20T16:43:52.573 回答
0

我的一个朋友给了我以下答案，他的数学知识比我多。我已将此标记为“社区”，因为这不是我的工作。

您需要知道每个（大多数？）组合的方式数，而不仅仅是等于 1s/2s。EG 你可以把 +18 和 -18 放在一起得到相等数量的 1 和 2

18
0/0
0/1
...
0/18
1/0
1/1
...
1/17
...
18/0

直接求解似乎容易得多。

0/0
1/0
1/1
2/1
2/2
3/2
3/3
...
18/17
18/18

做组合学

0/0 = 1 way
1/0 = (36C1) = 36 possibilities
1/1 = (36C1) * (36-1C1) = 1260 possibilities
2/1 = (36C2) * (36-2C1) = 21420
2/2 = (36C2) * (36-2C2) = 353430
3/2 = (36C3) * (36-3C2) = 3769920
3/3 = (36C3) * (36-3C3) = 38955840
4/3
4/4
5/4
5/4

18/17 = (36C18) * (36-18C17) = 163352435400
18/18 = (36C18) * (36-18C18) = 9075135300

用于打印 bc 行的 Perl 脚本，因为我懒得编写代码来很好地平衡乘法和除法。

sub print_choose
{
    $n = $_[ 0 ];
    $c = $_[ 1 ];

    if( $c == 0 ) { print "1"; return; }

    for( $j = 0; $j < $c; ++$j ) {
        if( $j ) { print "*"; }
        print $n - $j;
    }
    for( $j = 0; $j < $c; ++$j ) {
        print "/", $c - $j;
    }
}

for( $i = 0; $i <= 18; ++$i ) {
    if( $i > 0 ) {
        print_choose( 36, $i );
        print "*";
        print_choose( 36 - $i, $i - 1 );
        print "\n";
    }

    print_choose( 36, $i );
    print "*";
    print_choose( 36 - $i, $i );
    print "\n";
}


foo.pl | bc | perl -ne '$sum += $_; print "$sum\n"'
1
37
1297
22717
376147
4146067
43101907
335270707
2453494507
14315547787
78370635499
355942682251
1512492877051
5477807830651
18506699821051
54336152794651
148388466850351
357393609196351
798626687482351
1592846228397151
2943019447952311
4906907767305271
7584937293695671
10709305074484471
14094036837005671
17218404617794471
19862100432308071
21750454585532071
22964396541176071
23611832250852871
23913968915368711
24027270164562151
24062676804935101
24071007779140501
24072477951059101
24072641303494501
24072650378629801
于 2009-01-20T17:32:59.977 回答