Průvodní povídání 2

Pascalův trojúhelník

Průvodní povídání je také k dispozici ve formátu pdf.

Milý pikomaťáku,

poslední pojem, který jsme si v minulém díle průvodního povídání zavedli, je kombinační číslo. Právě kombinačním číslům se v tomto díle budeme věnovat, konkrétně budeme zkoumat takzvaný Pascalův trojúhelník. Ten na první pohled s kombinačními čísly moc nesouvisí, my si ale ukážeme, že je tomu právě naopak.

Rozehřejeme se tím, že budeme zkoumat součet čísel od jedné do n pro nějaké přirozené číslo n. Řekněme třeba, že n=20.

Představme si, že máme dvacet jedna různobarevných kuliček a chceme z nich dvě vybrat. Z minulého dílu víme, že nám vyjde \binom{21}{2}, jde to ale spočítat i bez toho. Můžeme si totiž kuličky seřadit. Když bude ve vybrané dvojici první kulička, máme dvacet možností, jaká bude další vybraná. Když bude ve dvojici druhá kulička, můžeme k ní přidat zase dvacet dalších. Z nich je jedna ale první kulička, takže tu už nechceme započítat. Máme tedy 19 možností, jak doplnit dvojici s druhou kuličkou. Podobně ke třetí kuličce jich můžeme přidat 18, až ke dvacáté můžeme přidat jen jednu. Takže víme, že počet různých dvojic kuliček z dvaceti jedna je 20+19+\cdots + 1, zároveň to ale je \binom{21}{2}. Snadným zobecněním tohoto argumentu dostaneme následující tvrzení.

Tvrzení: Součet čísel od 1 do n je \binom{n+1}{2} = n(n+1)/2.

Nyní je už na čase si říct, co je to ten Pascalův trojúhelník. Nejspíš už jsi někde potkal sčítací pyramidu -- máš cihličky naskládané na sebe a v každé cihličce je číslo, které je součtem čísel pod ním. Pascalův trojúhelník je skoro to samé, jen sčítáme čísla nad sebou, ne pod sebou, a je nekonečný.

Definice: Pascalův trojúhelník konstruujeme následovně (viz obrázek pruv21):

Do nultého řádku napíšeme 1. (Proč začínáme nultým a ne prvním řádkem se ukáže za chvíli.)
Každý další řádek bude o jedna delší než ten předchozí. Začíná a končí jedničkou, každé jiné číslo získáme tak, že sečteme dvě sousední čísla na předchozím řádku, která jsou nad ním. (I jednička je součtem čísel nad sebou, jen má nad sebou jen jedno číslo.)

Pokud máš chvíli čas, doporučujeme Ti si zkusit pár řádků Pascalova trojúhelníku napsat a pozorovat, jaká čísla vycházejí. Zvládneš uhádnout, co o nich platí?

Na kraji každého řádku bude jednička. Druhé číslo na prvním řádku je 1, na druhém 2, na třetím 3, ..., na n-tém n. Jistě si zvládneš zdůvodnit proč: Postupně si to rozmyslíme pro každý řádek od shora dolů. Třeba na dvanáctém řádku je druhé číslo součtem prvního a druhého čísla na jedenáctém řádku. První je jedna, takže když už víme, že druhé je deset, jejich součet je jedenáct. Takto to dokážeme pro všechny řádky.

Nyní se podívejme na třetí číslo na každém řádku. Na druhém řádku to je jednička, na třetím trojka, na čtvrtém šestka, ..., na (n+1)-tém to bude součet čísel od 1 do n. K důkazu použijeme úplně stejnou myšlenku jako v předchozím odstavci: Pokud o pátem řádku víme, že třetí číslo na něm je 1+2+3+4, bude třetí číslo na šestém řádku 1+2+3+4 sečtené s druhým číslem na pátém řádku, o kterém už víme, že je 5. Dohromady dostaneme, že třetí číslo na šestém řádku je 1+2+3+4+5. Obdobně bychom to dokázali i pro ostatní řádky.

O součtu čísel od 1 do n jsme si ale už dokázali, že je roven \binom{n+1}{2}. Když si navíc uvědomíš, že \binom{n}{1} = n a že \binom{n}{0} = 1 (je jeden způsob, jak vybrat žádnou věc z n, totiž nijak), začneš už jistě větřit následující důležité tvrzení. Toto tvrzení Pascalův trojúhelník velmi dobře popisuje.

Tvrzení: Na n-tém řádku Pascalova trojúhelníku je (k+1)-té číslo rovno \binom{n}{k}.

Důkaz: Důkaz je velmi podobný tomu, co jsme dělali před chvílí, totiž postupně si to dokážeme pro všechny řádky odshora dolů tak, jak si Pascalův trojúhelník píšeme. Formálně se tomu říká matematická indukce, pokud jsi o ní nikdy nic neslyšel, tak věz, že to opravdu není nic neintuitivního.

Pro první a poslední číslo na každém řádku tvrzení platí, \binom{n}{0} = 1 a \binom{n}{n} = 1 pro všechna přirozená čísla n. Tím jsme to dokázali i pro první a druhý řádek. Nyní už můžeme předpokládat, že tvrzení máme dokázané pro (n-1)-tý řádek a ukážeme ho pro n-tý. Tedy ukážeme, že když tvrzení platí pro druhý, platí i pro třetí, když platí pro třetí, platí i pro čtvrtý, a tak dále, čímž tvrzení postupně dokážeme pro všechny řádky. Číslo, o kterém chceme ukázat, že je rovno \binom{n+1}{k}, získáme sečtením čísel, o nichž už víme, že jsou rovna \binom{n}{k-1} a \binom{n}{k}. K dokončení důkazu nám tedy stačí následující tvrzení, které je hodno zapamatování samo o sobě.

Tvrzení: Pro všechna přirozená čísla n>1 a k\geq 1, n>k, platí \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

Pokud chceš, můžeš si rozepsat kombinační čísla pomocí faktoriálů a chvíli upravovat zlomky. My si to ale rozmyslíme pomocí takzvaného počítání dvěma způsoby. To využívá toho, že máme hezký kombinatorický význam jedné strany a ukážeme, že druhá strana má tentýž význam. Neboli vezmeme nějakou hromádku věcí (množinu) a spočítáme její velikost (počet prvků) dvěma různými způsoby. Protože velikost hromádky se nemění v závislosti na tom, jak ji počítáme, musí si být výrazy, které takto získáme, rovny.

Důkaz tvrzení: Víme, že \binom{n}{k} je počet způsobů, jak vybrat k kuliček z n různobarevných. Z těchto n kuliček si vybereme jednu, řekněme, že je zelená. Rozdělíme si k-tice kuliček podle toho, zda obsahují, nebo neobsahují zelenou kuličku. Ty, co neobsahují zelenou kuličku, vybíráme z n-1 zbývajících, tedy jich je \binom{n-1}{k}. Pokud k-tice obsahuje zelenou kuličku, musíme k ní vybrat ještě k-1 kuliček ze zbylých n-1. Tedy takových k-tic je \binom{n-1}{k-1}. Zjistili jsme, že počet způsobů, jak vybrat k kuliček z n, je \binom{n-1}{k} + \binom{n-1}{k-1}, zároveň ale už víme, že tento počet způsobů je \binom{n}{k}.

Z toho, jak jsme Pascalův trojúhelník zkonstruovali, můžeme tušit, že bude osově souměrný podle své svislé osy (obrázek pruv22). I to má svou kombinatorickou interpretaci.

Tvrzení: Pro každé přirozené n a k, n>k, platí \binom{n}{k} = \binom{n}{n-k}.

Důkaz: Můžeme využít symetrii Pascalova trojúhelníku, upravovat zlomky nebo využít následující kombinatorický argument. Když někdo vybere k kuliček z n různobarevných a řekne, které barvy vybral, získáme stejnou informaci, jako když řekne, kterých n-k barev nevybral. Tedy počet způsobů, jak vybrat k kuliček, které si vezmeme, je stejný jako počet způsobů, jak vybrat n-k kuliček, které si nevezmeme.

Následující tvrzení se týká toho, jak vyjde součet čísel v jednom řádku Pascalova trojúhelníku (obrázek pruv23).

Tvrzení: Pro všechna přirozená čísla n platí \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n-1} + \binom{n}{n} = 2^{n}.

Důkaz: Ukážeme si dva možné důkazy.

První bude zase matematickou indukcí. Uvědomíme si, že zkoumáme součet čísel v jednom řádku Pascalova trojúhelníku, a dokážeme to postupně pro řádky odshora dolů. Pro nultý řádek opravdu platí, že 2^{0}=1. Představme si, že už jsme napsali několik prvních řádků trojúhelníku. Když budeme psát další řádek, pro každé číslo sečteme čísla nad ním. Každé číslo z posledního již napsaného řádku se tedy „dostane“ do právě dvou čísel právě psaného řádku. Tedy i součet se zdvojnásobí.

Druhý důkaz je opět kombinatorický náhled pomocí počítání dvěma způsoby. Tentokrát si vezmeme n různobarevných kuliček a zamyslíme se nad tím, kolik různých skupinek si z nich můžeme vzít a dát do pytlíčku. Skupinka klidně můžou být všechny kuličky, jedna kulička nebo i žádná kulička. (Pro množin znalé poznamenejme, že počítáme počet podmnožin n-prvkové množiny.) Takovou skupinku můžeme dostat tak, že se u každé kuličky zvlášť rozhodneme, zda si ji vezmeme, nebo ne. U každé kuličky máme dvě možnosti, celkem tedy máme 2^{n} možností, jakou skupinku si vezmeme. U druhého způsobu počítání si nejdřív zafixujeme, jakou velikost skupinky si vezmeme, zjistíme, kolik takových skupinek si můžeme vzít, a výsledky pro jednotlivé skupinky nakonec sečteme. Už ale víme, že různých skupinek velikosti k je \binom{n}{k}. Dohromady nám tedy vyjde \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n}, přesně jak jsme chtěli.

Tvrzení (o hokejce): Pro všechna přirozená čísla n a k, taková že n>k, platí \binom{k}{k} + \binom{k+1}{k} + ... + \binom{n}{k} = \binom{n+1}{k+1}.

Důkaz: Toto tvrzení lze snadno dokázat matematickou indukcí za využití toho, že \binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k} (můžeš si to zkusit dokázat a nakreslit v Pascalově trojúhelníku). My si tu opět ukážeme kombinatorický důkaz pomocí počítání dvěma způsoby.

Pravá strana nám říká, co máme počítat -- jsou to různé (k+1)-tice vybrané z n+1 různobarevných kuliček. Zbývá už jen rozklíčovat levou stranu. Kuličky dáme do řady. Rozdělíme si (k+1)-tice podle toho, která kulička se v nich objeví jako první. Pokud to bude první kulička, vybíráme zbylých k kuliček z n kuliček, které jsou za ní, což můžeme udělat \binom{n}{k} způsoby. Pokud druhá, tak už nám za ní zbývá jen n-1 kuliček, z nichž zbývajících k vybíráme, což můžeme udělat \binom{n-1}{k} způsoby. Pokud bude první vybraná kulička třetí v řadě, zbyde nám za ní už jen n-2 kuliček. Z těch můžeme k vybrat \binom{n-2}{k} způsoby. Takto pokračujeme, až dojdeme k (n-k-1)-té kuličce, za níž už jich zbývá jen k. Žádná další kulička už nemůže být první z vybraných, protože už za ní není dost dalších. Dohromady jsme dostali přesně součet na levé straně.

Na závěr poznamenejme, že tímto jsme zdaleka nevyčerpali všechny vlastnosti Pascalova trojúhelníku. Například úzce souvisí s teorií pravděpodobnosti, konkrétně s binomickým rozdělením, které se blíží normálnímu rozdělení. (Pokud jsi poslední větu ani trochu nepochopil, vůbec se tím netrap. Pokud chceš vidět hezké obrázky, vygoogli si „Galton board“.)