Number of trits matching count criteria

Question

For all trinary numbers with length 36 (including those starting with 0's), how many have exactly equal counts of 1's and 2's, or exactly one more 1 than 2?

For example:

• 00 - yes
• 01 - yes
• 02 - no
• 10 - yes
• 11 - no
• 12 - yes
• 20 - no
• 21 - yes
• 22 - no

So for all trinary numbers of length 2, 5 out of 9 possibilities match. This presumably gets smaller as the length increases. For length 3, there are 13 out of 27.

If we were dealing with binary numbers, there are a number of solutions available here but it isn't clear to me how to generalise these to trinary numbers.

Answer 1

The process seems straightforward enough as a combinatorial exercise. For every N in [1..18], find all the different arrangements of "1" in a 36-place tritstring. Then multiply that by the number of different arrangements of N "2"s in the positions not taken by a "1", and also for N-1 "2"s. Find the sum of those 36 numbers. After all that, add 1 for N=0, that being a tritstring of all "0"s.

The number of different arrangements of N trits in a 36-long tritstring should be

36! / N!(36-N)!

The problem sounds like a brainteaser. I haven't developed the above further, but I highly suspect the presence of shortcuts.

Answer 2

A friend of mine gave me the following answer, and he knows more math than I do. I have marked this as 'community' because it is not my work.

You would need to know the number of ways for every (most?) combination, not just equal 1s/2s. EG you can put together +18 and -18 to get an equal number of 1s and 2s

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

Solving directly seems much easier.

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

Do the combinatorics

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 script to print out lines for bc, because I'm too lazy to write code that balances the multiplications and divisions nicely.

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