Kombinatorikk i tretallssystemet

[Karl_Erik]

For en gitt $n$, hvor mange n-sifrede tall finnes det i tretallssystemet slik at antallet sifre som er lik 1 er et partall?

(Sifrene kan altså være lik 0, 1 eller 2, og selv om det 'største' sifferet er null går dette helt fint. For n=2 er altså de mulige sifrene 00, 20, 02, 11, og 22.)

[BMB]

Skal 22 også være en mulighet for n=2-tilfellet? Isåfall tror jeg svaret skal bli

$S_n=\sum _{j=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{2j})\cdot 2^{n-2j}$

[Karl_Erik]

Beklager, ja, dette var selvfølgelig sløvhet fra min side. Summen du har kommet fram til er selvfølgelig helt riktig, men lar det seg gjøre å få den på lukket form også?

[BMB]

Ved å putte inn noen smarte tall i binomialformelen, får man

$\sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})\cdot 2^{n-j}=3^n$

og

$\sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})\cdot (-1{)}^j{2}^{n-j}=1$.

Ved litt addisjon/subtraksjon og halvering får vi da

$S_n=\sum _{j=0}^{\lfloor \frac{n}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{2j})\cdot 2^{n-2j}=\frac{3^n+1}{2}$.

Du har kanskje en raskere måte å telle dette på?

[Charlatan]

Det blir vel tallene som er delelig med 2. Modulo 2 er
$N=a_0+3a_1+...+a_{n-1}{3}^{n-1}\equiv a_0+...+a_{n-1}$
som er 0 hvis og bare hvis N har et partallig antall 1'ere.

Hvis vi tillater 0 som første siffer er det $3^n$ tall, hvorav $\frac{3^n+1}{2}$ er partallige.

[Karl_Erik]

Jeg hadde ikke sett den andre, forøvrig fine, løsningen før, men begge er selvfølgelig helt riktige.