matematikk.net

På hvor mange måter kan et gitt positivt heltall [tex]n[/tex] skrives som en sum av positive heltall hvis vi regner [tex]a+b[/tex] og [tex]b+a[/tex] som forskjellige?

Eks: 3 kan skrives som 1+1+1, 2+1, 1+2 og 3

Regner ut et par verdier og hypotetiserer at tallet [tex]n[/tex] kan skrives som en ordnet sum av minst ett tall på [tex]2^{n-1}[/tex] måter.

La oss si at [tex]s(n,m)[/tex] er antall måter tallet [tex]n[/tex] kan skrives som summen av nøyaktig [tex]m \leq n[/tex] tall på. Ser at [tex]s(n,m=1) = s(n,m=n) = 1[/tex] og [tex]s(n,m=2) = s(n,m=n-1) = n-1[/tex]. Nå begynner vi å mistenke rad n-1 i Pascals talltrekant.

Hvis vi skriver n som n enere, f.eks. 5 : 11111, og skiller enerene fra hverandre med m plusstegn, har vi n-1 skillerom å putte dem i. Antall måter å putte m plusser i n-1 mellomrom er [tex]{n-1} \choose m[/tex].

[tex]s(n) := \sum^{n-1}_{m=0} s(n,m) = \sum^{n-1}_{m=0} {n-1 \choose m} = 2^{n-1}[/tex].