Количество переходов, соответствующих критерию подсчета

Question

Для всех тройных чисел длиной 36 (включая те, которые начинаются с 0), сколько из них имеет одинаковое количество единиц и 2 или ровно одно больше 1 чем 2?

Например:

• 00 - да
• 01 - да
• 02 - нет
• 10 - да
• 11 - нет
• 12 - да
• 20 - нет
• 21 - да
• 22 - нет

Таким образом, для всех тройных чисел длины 2, 5 из 9 вариантов совпадают. Это предположительно становится меньше с увеличением длины. Для длины 3, есть 13 из 27.

Если бы мы имели дело с двоичными числами, есть ряд доступных решений здесь , но мне не ясно, как обобщить их в триальные числа.

Answer 1

Процесс кажется достаточно простым как комбинаторное упражнение. Для каждого N в [1..18] найдите все различные расположения «1» в тристрине из 36 мест. Затем умножьте это на количество различных расположений N "2" в позициях, не занятых "1", а также на N-1 "2" s. Найдите сумму этих 36 чисел. После всего этого, добавьте 1 для N = 0, что является строкой всех «0».

Количество различных расположений N тритов в тристрине длиной 36 должно быть

36! / N!(36-N)!

Проблема звучит как головоломка. Я не развивал вышеупомянутое далее, но я очень подозреваю наличие ярлыков.

Answer 2

Мой друг дал мне следующий ответ, и он знает больше математики, чем я. Я отметил это как «сообщество», потому что это не моя работа.

Вам нужно знать количество способов для каждого (больше всего?) комбинация, а не просто равна 1 с / 2 с. Например, вы можете собрать +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