For en gitt [tex]n[/tex], 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.)
Kombinatorikk i tretallssystemet
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Ved å putte inn noen smarte tall i binomialformelen, får man
[tex]\sum_{j=0}^n {n \choose j} \cdot 2^{n-j}=3^n[/tex]
og
[tex]\sum_{j=0}^n {n \choose j} \cdot (-1)^j 2^{n-j}=1[/tex].
Ved litt addisjon/subtraksjon og halvering får vi da
[tex]S_n=\sum_{j=0}^{\lfloor \frac n2 \rfloor}{ {n \choose 2j} \cdot 2^{n-2j}}=\frac{3^n+1}{2}[/tex].
Du har kanskje en raskere måte å telle dette på?
[tex]\sum_{j=0}^n {n \choose j} \cdot 2^{n-j}=3^n[/tex]
og
[tex]\sum_{j=0}^n {n \choose j} \cdot (-1)^j 2^{n-j}=1[/tex].
Ved litt addisjon/subtraksjon og halvering får vi da
[tex]S_n=\sum_{j=0}^{\lfloor \frac n2 \rfloor}{ {n \choose 2j} \cdot 2^{n-2j}}=\frac{3^n+1}{2}[/tex].
Du har kanskje en raskere måte å telle dette på?
Det blir vel tallene som er delelig med 2. Modulo 2 er
[tex]N = a_0+3a_1+...+a_{n-1}3^{n-1} \equiv a_0+...+a_{n-1}[/tex]
som er 0 hvis og bare hvis N har et partallig antall 1'ere.
Hvis vi tillater 0 som første siffer er det [tex]3^n[/tex] tall, hvorav [tex]\frac{3^n+1}{2}[/tex] er partallige.
[tex]N = a_0+3a_1+...+a_{n-1}3^{n-1} \equiv a_0+...+a_{n-1}[/tex]
som er 0 hvis og bare hvis N har et partallig antall 1'ere.
Hvis vi tillater 0 som første siffer er det [tex]3^n[/tex] tall, hvorav [tex]\frac{3^n+1}{2}[/tex] er partallige.
