Pascal

[Emilga]

Definer g(n) til å være antallet odde elementer i den raden i Pascals talltrekant som begynner med 1,n,... Finnes det da en formel for g(n)?

[Emilga]

Jeg brukte metoden til Polyas mus, og har oppdaget at [tex]g(n) = 2^{s(n)}[/tex], der s(n) er lik tverrsummen av tallet n skrevet i base to. Jeg har ingen formening om hvorfor denne formelen fungerer.

[Karl_Erik]

Polyas mus er en veldig lur måte å finne hvor en skal begynne på. Vi vet at det i-te elementet i den n-te raden av Pascals trekant (strengt tatt den n+1-te siden vi hopper over 'toppen') er lik [tex]{n} \choose {i}[/tex]. La [tex]n=\sum 2^k a_k[/tex], og [tex]i=\sum 2^k i_k[/tex] være binærrepresentasjonene av n og i. Bruker vi Lucas' teorem får vi at [tex] {n \choose i} \equiv \prod {{a_k} \choose {i_k}} \pmod 2[/tex]. Vi vil finne for hvilke i dette er 1 mod 2. Siden [tex]a_k, i_k \in \{ 0, 1 \}[/tex] ser vi at en faktor er null hvis og bare hvis [tex]i_k=1, a_k=0[/tex]. Altså er [tex]i_k[/tex] nødvendigvis 0 for de [tex]k[/tex] dersom [tex]a_k=0[/tex].

Dersom [tex]a_k=1[/tex] kan vi velge [tex]i_k[/tex] til å være null eller én - uansett blir faktoren 1. Det er da klart [tex]2^{s(n)}[/tex] måter å velge [tex]i_k[/tex] (og derfor i) på for å gjøre [tex]n \choose i[/tex] odde (Siden [tex]s(n)[/tex] er antallet 1-sifre i binærrepresentasjoenn av n). Alle valgene for [tex]i_k[/tex] gir selvfølgelig gyldige i, så vi er ferdige.

[Emilga]