符合计数标准的trits数量

作为一项组合练习,这个过程似乎很简单。对于[1..18]中的每一个N,找到36位tritstring中“1”的所有不同排列。然后将其乘以N“2”在非“1”位置的不同排列数量,以及N-1“2”s。找到这36个数字的总和。在所有这些之后,为N=0加1,即所有“0”的tritstring。

一个36长的trits串中N trits的不同排列数量应为

36! / N!(36-N)!

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

我的一个朋友给了我以下答案,他比我懂更多的数学。我把这个标记为“社区”,因为这不是我的工作。

你需要知道每种(大多数?)方法的数量 组合,而不仅仅是等于1s/2s。你可以把+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

Perl脚本打印出bc的行,因为我懒得写 很好地平衡乘法和除法的代码。

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