Počátky kombinatoriky v díle J. Bernoulliho Ars conjectandi

MASARYKOVA UNIVERZITA BRNO Přírodovědecká fakulta Katedra matematiky

Počátky kombinatoriky v díle J. Bernoulliho Ars conjectandi DIPLOMOVÁ PRÁCE

Brno, 2003

Pavla Klusáčkova

íPňÍRODOVŕDECtíL,

-

.

,

PROHLÁŠENÍ Prohlašuji, že diplomovou práci na téma „Počátky kombinato­ riky v díle J. Bernoulliho Ars conjectandi" jsem vypracovala samostatně a s použitím literárních pramenů, které jsem uvedla v přiloženém seznamu literatury.

V Brně dne 7. května 2003

. .fe^í^fV.

PODĚKOVÁNÍ Děkuji vedoucímu mé diplomové práce RNDr. Pavlu Šišmovi, Dr. za poskytnutí odborného zázemí, cenných rad a literatury, které mi pomohly vytvořit tuto práci. Zároveň chci poděkovat rodičům a sourozencům za podporu a pomoc při mém studiu.

Obsah Předmluva

5

1 Vznik kombinatoriky 1.1 Počátky kombinatoriky 1.2 Jakob Bernoulli 1.3 Ars conjectandi

7 7 12 16

2 Permutace 2.1 Permutace

19 19

3 Kombinace 3.1 Obecně o kombinacích 3.2 Kombinace bez opakování v určitých třídách; fi­ gurální čísla a jejich vlastnosti 3.3 Kombinace bez opakování v určité třídě 3.4 Počet kombinací s opakováním 3.5 Počet kombinací s omezeným opakováním . . . .

24 24

4 Variace 4.1 Variace bez opakování 4.2 Variace s opakováním 4.3 Počet variací s omezeným opakováním

49 49 52 55

Závěr

59

Literatura

60 4

27 36 39 45

Předmluva I když první kombinatorické úvahy lze nalézt v nejstarších dochovalých textech staré Indie, samotná kombinatorika, kterou dnes chápeme jako část matematiky studující vlastnosti koneč­ ných množin a struktury jejich podmnožin, vznikla v 17. století a to v souvislosti s úvahami o pravděpodobnosti výhry při ha­ zardních hrách. Dnes již ke klasickým otázkám kombinatoriky patří otázka výběru prvků a jejich rozmístění do určitých uskupení daných vlastností, především pak otázka stanovení počtu všech usku­ pení určitého typu. Pro nejjednoduší uskupení se ustálily pojmy variace, kombinace a permutace, s nimiž se studenti střední školy seznamují. Klasická kombinatorika patří mezi nepříliš oblíbené disciplíny studentů, a to možná proto, že je zde zapotřebí pro­ jevit samostatný způsob uvažování, navíc zde neexistuje žádný způsob ověření správnosti výsledků a je tedy třeba se spolehnout na vlastní úsudek. V tom však nakonec můžeme spatřovat krásu kombinatoriky. Bouřlivý rozvoj kombinatoriky ve 20. století vedl k vnitřní di­ ferenciaci kombinatoriky a vzniku nových matematických disci­ plín, mezi které můžeme zařadit teorii grafů či kombinatorickou geometrii. Podněty k rozvoji byly čistě praktické a to moderní výpočetní technika, která umožňuje řešit složité teoretické pro­ blémy. Cílem této diplomové práce je ukázat jakým způsobem Jakob Bernoulli zavádí ve svém díle Ars conjectandi, které patří mezi 5

první rozsáhlejší práce věnované kombinatorice, základní kombi­ natorické pojmy, se kterými se setkávají studenti středních škol a dále je zde snaha zařadit tuto práci do vývoje kombinatoriky. Samotnou práci lze rozdělit do dvou částí. První část před­ stavuje krátký úvod do historie kombinatoriky, měla by však také sloužit k poznání osoby Jakoba BernouUiho a jeho díla Ars conjectandí Druhá část představuje komentovaný, volný překlad Bernoulliho spisu Ars conjectandi, který je doplněn autentickými ukáz­ kami jednotlivých kombinatorických pravidel a moderním způ­ sobem jejich formulace. V některých případech pak bylo prove­ deno zobecnění problému. Východiskem pro tuto práci se stal německý překlad, který byl pod názvem Wahrscheintlichkeitsrechnung vydaný v roce 1899 v Lipsku.

6

Kapitola 1 Vznik kombinatoriky 1.1

Počátky kombinatoriky

Kombinatorická problematika doprovázela algebru a aritmetiku již od počátku historie matematiky. Nejranější záznamy formu­ lace kombinatorických úloh pocházejí z Indie. Například Susru­ tův 1 lékařský spis obsahuje systematický seznam kombinací šesti základních chutí - sladký, kyselý, slaný, ostrý, hořký a trpký; jme­ novitě šest jedinců, patnáct dvojic, dvacet trojic, atd. Susrutův výsledek můžeme prostřednictvím moderního způsobu zápisu vyjádřit takto: © = 6 , © = 15, © = 2 0 , © = 1 5 , © = 6 , © = 1. Z pozdějších řešitelů kombinatorických úloh zmíním Varáhamihiru (6. století), který uvádí, že existuje 1820 způsobů výběrů 4 přísad z celkových šestnácti k vytvoření vůně. V moderním zápisu: tf(4,16) = (x46) = 1820. A protože je nepravděpodobné, že by všech 1820 kombinací vy­ psal, lze předpokládat, že znal metodu výpočtu daného čísla. 1

Susruta (6.století př.n.l) - indický lékař. Autor nejstaršího indického lékařského spisu Ajurvéd, jenž je psán formou dialogu.

7

Za autora algoritmu pro výpočet počtu kombinací lze pova­ žovat Mahávíru (9. století), a to i přesto, že algoritmus, který dnes zapisujeme takto:

*(*.») = *-$:£?*" = 0 nepodrobil žádnému důkazu a jen jej jednoduše aplikoval na dva případy, a to již na uvedenou úlohu o kombinacích chutí a dále na úlohu: Kolik náhrdelníků lze vyrobit z určitého počtu z diamantů, safírů, smaragdů, korálů a perel. Na Mahávírovy poznatky navázal Bháskara (12. století), který dále připojil obecné pravidlo k výpočtu pořadí n prvků, které aplikuje na příklad: Kolik existuje obměn symbolů boha Sambhu, které drží ve svých pěti párech rukou. O kombinatorické úvahy se zajímali i islámští matematici. Například Ahmed al-Abdari ibn Munim (13.století) stejně jako řada jiných řeší otázku: Kolik slov lze vytvořit z písmen arabské abecedy. Před tím, než na tuto otázku odpoví, však řeší úlohu: Kolik různých svazků barev lze vyrobit z deseti různých ba­ rev hedvábí. Je jasné, že existuje 10 jednobarevných možností. Využije-li ibn Munim dvě barvy, získá dvojice v následujícím pořadí: (fc2, A*); (fa, fci), (fa, fa)\...; (k10j fa), (fcio, fa), •• • > (fcio> fa)Následně zjistil: K(2,10) = K(l, 1)+K(1,2) + .. .+üf(l, 9) = 1 + 2 + . . .+9 = 45. Pro fc-tice prvků, kde k = 3,4,..., 10 pak vždy využije (k — 1)tice prvků z předchozího příkladu. Na příklad: (fa(k2, fci)); (k^ (fc2, fa)), (&4, (fc3,fci)),(fe4, (**, fo)); (fa, (fc2, fei)),... Tedy: 8

If (3,10) = 1 + 3 + 6 + ... + 36 K(2,2) + K(2,3) + if (2,4) + ... + if (2,9), atd. Následně vypíše jednotlivé možnosti do tabulky a obdrží tak aritmetrický (Pascalův) trojúhelník. V rámci problematiky slov podal důkaz o počtu permutací. Z islámských matematiků bych dále upazornila na Abu-1Abbas Ahmad al-Marrakushi ibn al-Banná (1256-1321), který pojednával o kombinatorice zcela obecně, nezajímal se, jaké druhy objektů kombinuje, navíc bych schopen odvodit vztah pro počet kombinací a to na základě vzorce, který dnes zapisujeme

K{k,n) = *=&=£-K{k-lfn). Na závěr zdůrazním, že jak vzorec pro počet kombinací, tak vzorec pro počet permutací byl odvozen induktivní metodou. Kombinatorická tématika byla rozvíjena i v Evropě, přede­ vším pak v židovské komunitě. Mezi první okruhy problémů patří i zde otázka, kolik slov lze vytvořit z písmen hebrejské abecedy2. Podrobnějším studiem kombinatoriky se zabýval Abrhama ben Meir ibn Ezru3 či Levi ben Gerson. Levi ben Gerson (1287-1344) - je autor díla Maasei Hoshev. Text tohoto spisu je rozdělen do dvou částí. V první teoretické části se objevují pečlivé důkazy obecných kombinatorických pravidel, druhá část je věnována jejich procvičení. Mezi formule, které byl Levi ben Gerson schopen odvodit, patří pravidlo pro stanovení počtu per­ mutací n prvků, tedy P(n) = 1 • 2 • ... • n, v rámci variací věděl že, V(j + 1, n) — (n — j) • V(j, n) a tedy 2

Tuto kombinatorickou úlohu lze nalést v mystické knize Sefer Yetsirah, pocházející zřejmě z 8. století, 3 Abrhama ben Meir ibn Ezru (1090-1167) - filozof, astrolog, biblický komentátor, za­ bývající se mimo jiné i úlohou kterou později nacházíme u Bernoulliho, a to kolik existuje konjukcí planet Sluneční soustavy. Stanovil tedy počet /c-prvkových kombinací 7 prvků. Židovské komunitě přiblížil desítkovou soustavu.

9

V(j, n) = n(n - 1) • . . . • (n - j + 1), z oblasti kombinací znal, K (k, n) — ^V. Přímým důsledkem tohoto tvrzení je standardní vzorec pro K(k,n)

Základní kombinatorická pravidla existovala v Evropě již ve 14. století. Je zde však otázka, nakolik vstoupily tyto poznatky ve známost, neboť je velmi podivuhodné, že kombinatorická pro­ blematika se začala opětovně rozvíjet v Evropě až o takřka dvě století později. Můžeme tedy předpokládat, že většina poznatků upadla v zapomnění a musela být znovu objevena. Rozvoj kombinatorické tématiky v Evropě 16. století úzce souvisí s počátky pravděpodobnostního počtu, v rámci kterého byly řešeny dva okruhy otázek: 1. Kolika způsoby může padnout jistý počet ok při házení se dvěma, třemi, atd. kostkami. 2. Jak má být spravedlivě rozdělena částka, jestliže dva hráči spolu hrají sérii her o částku C; tuto částku získá ten hráč, který jako první vyhraje k her. Pravděpodobnost výhry v každé jednotlivé hře je pro oba hráče stejná. Série her je předčasně ukončena ve chvíli, kdy jednomu hráči chybí do výhry m her, druhému hráči chybí do výhry n her. Úlohami, které bychom dnes zařadili do oblasti pravděpo­ dobnostního počtu, se zabývali již Nicolo Trtaglia (1499 - 1557) či Hieronymus Cardano (1501 - 1576). V Cardanových spisech se nalézá aritmetický trojúhelník, který Cardano využívá pro stanovení fc-prvkových kombinací n prvků. Lze tedy snadno do­ vodit, že znal alespoň některé vlastnost aritmetického trojúhel­ níku, jako na příklad K{k, n) = (n ~ fe+1) f (/c~1}-n . Dále bych zmí­ nila Marina Mersenna (1588 - 1648), v jehož spisu lze mimo jiné nalézt vztah pro stanovení počtu /c-prvkových variací z n prvku, 10

tedy V(k, n) = n(n — 1 ) . . . (n — k + 1) a pravidlo pro stanovení počtu permutací s opakováním P0(ri) = n.2. -fc VL22+fc 1^1-2- -fc r Počátky kombinatoriky jako samostatné části matematiky jsou kladeny do poloviny 17. století. Mezi první samostatné práce, které se věnují kombinatorice jpatří Pojednáni o aritme­ tickém trojúhelníku, jehož autor je Blaise Pascal, Leibnizův spis Ars combinatoria a Bernoulliho kniha Ars conjectandi. Jak Blaise Pascal (1623 - 1662), tak Gottfried Wilhelm Leib­ niz (1646 - 1716) patřili k osobnostem s rozsáhlým přehledem a to nejen v oblasti matematiky či fyziky, ale i například v oblasti filozofie a teologie, v rámci nichž byli schopni vést disputace. Blaise Pascal publikoval ve věku 16 let pojednání o kuže­ losečkách, ve 20 sestrojil počítací strojek, v letech 1648 - 1653 prověřil správnost Toricelliho pokusu, v letech 1653 - 1654 se za­ býval pravděpodobnostní problematikou a v letech 1658 - 1659 cyklojdou. Gottfried Wilhelm Leibniz působil po ukončení právnického vzdělání v diplomatických službách mohučského kurfiřta, což ho roku 1672 přivedlo k francouzskému královskému dvoru s po­ sláním přimět francouzského krále Ludvíka XIV. k tažení do Egypta. Čtyřletý pobyt v Paříži využil Leibniz k navázání vě­ deckých kontaktů, nejen matematických. Od roku 1676 působil až do své smrti jako knihovník a dvorní rada v Hannoveru. Pascalovo Pojednáni o aritmetickém trojúhelníku vyšlo v roce 1665, nicméně danou problematikou se Pascal zabýval již v roce 1654, což je patrné z korespondence vedené s Fermatem, která položila základy pravděpodobnostnímu počtu. Jedná se tedy o soubor pojednání, které se částečně obsahově překrývají, které nejsou zřetelně odděleny a které jsou navíc psány různými jazyky (francouzsky a latinsky). V první části spisu studuje vlastnosti aritmetického trojúhelníku a následné aplikace v kombinatorice. Samotné kombinatorice se věnují pouze dvě z dvanácti kapitol. Je zajímavé, že pozornost věnoval pouze kombinacím bez opá­ lí

kování. Leibnizův spis Ars combinatorial který byl vydán v roce 1666, je často řazen mezi spisy filozofické, neboť matematice se vě­ nuje pouze část spisu, navíc byl tento spis psán v době kdy se Leibniz matematikou nezabýval. Z hlediska matematickéhokombinatorického obsahu se zde nalézá aritmetický trojúhelník a jeho použití pro stanovení počtu kombinací. Co se týče Bernouliho knihy Ars conjectandi, zmíním pouze z hlediska chronologického rok 1685, kdy tato kniha vznikla. Podrobně se jí věnuji v kapitole 1.3. Zatímco Pascal považuje kombinatoriku za pouhý aplikační obor aritmetiky a Leibniz za nástroj řešení logicko-filosofických problémů, Bernoulli ji chápe jako zcela samostatnou část mate­ matiky a možná proto, nebo především proto můžeme jeho dílo považovat za historický předěl ve vývoji této části matematiky. A i když všechny tyto osobnosti chápaly kombinatoriku tak, jak ji znají dnes studenti středních škol, tedy nauku o variacích, permutacích a kombinacích s opakováním i bez opakování, uza­ vírají dané spisy dlouhé období formování kombinatoriky jako moderní části matematiky. Dnes je kombinatorika chápána jako část matematiky studu­ jící vlastnosti konečných množin a struktury jejich podmnožin. Ve 20. století prožívala a neustále prožívá bouřlivý rozkvět. Na prahu rozvoje kombinatoriky stál však právě Jakob Bernoulli a jeho spis Ars conjectandi

1.2

Jakob Bernoulli

Jakob Bernoulli pochází z rodiny, jejíž členové přispěli k rozvoji mnoha vědeckých disciplín, nejen matematických. Předkové Ja­ koba Bernoulliho opustili z důvodu náboženského pronásledo­ vání v druhé polovině 16. století, za vlády vévody z Alby, ho­ landské Antverpy a přes Prankfurt nad Mohanem se ve 20. letech 12

17. století dostali do Basileje. Zde Nikolas Bernoulli (1623-1708) jako majitel obchodu s kořením a především jako člen městské rady a soudu požíval značné vážnosti. Jeho nejstarším synem byl právě Jakob. Matka Jakoba Bernoulliho pocházela z vážené basilejské rodiny bankéře a člena městské rady. Jakob Bernoulli, který se narodil 27. prosince 1654 v Basileji, je první v řadě významných Bernoulliů-matematiků. Na přání svých rodičů studoval filozofii a teologii. Studie ukončil v letech 1671, respektive 1676, kdy dosáhl teologického licenciátu. Během pobytu na univerzitě věnoval pozornost studiu matematiky a astronomie, a to i přes odpor svých rodičů. V roce 1676 působí Bernoulli nejprve jako domácí vychovatel. Poté odchází do Francie, kde takřka dva roky strávil studiem u Descartesových stoupenců. V roce 1681 odcestoval do Nizozemí, kde se setkává s mnohými matematiky. Své matematické studie plně rozvinul v Anglii pod vedením čelních matematiků a vědců z celé Evropy, mezi jinými se zde setkává s Boylem4 a Hookem5. Navázal zde tak vztahy pro budoucí rozsáhlou korespondenci. V roce 1683 se Jakob Bernoulli vrací do Basileje a poté, co odmítl kazatelské místo ve Štrasburku, neboť jeho životní vášní byla matematika a teoretická fyzika, zahájil první veřejné před­ nášky z mechaniky pevných látek a plynů na basilejské univer­ zitě. Během tohoto období studuje Leibnizovy a Schootenovy matematické práce a to v latinském překladu. V roce 1687 byl Jakob Bernoulli jmenován profesorem mate­ matiky na basilejské universitě. Mezi jeho vynikající žáky patřil mimo jiné bratr Johann6 a též Paul Euler, otec Leonharda Eu4 sir Robert Boyle (1627-1691) - anglický fyzik a chemik; prezident Royal Society v Londýně. 5 Robert Hooke (1635-1703) - anglický přírodovědec a vynálezce. Profesor geometrie na Gresham-College v Kolíně. 6 Johann Bernoulli (1667-1748) - švýcarský matematik. Profesor na universitě v Gronnigenu a v Basileji. Přispěl k rozvoji diferenciální geometrie, problémy mechaniky řešil pomocí diferenciálních rovnic, k integraci racionálních funkcí využíval rozklad na parciální zlomky.

13

lera. Bernoulli patřil k prvním matematikům, kteří si osvojili di­ ferenciální počet. V roce 1690 uveřejnil v Acta Eruditorum po­ jednání o izochroně7, kde se poprvé vyskytuje slovo integrál8. Záhy mezi oběma bratry vzniká spor, na němž mají obě strany nemalý podíl, který však nakonec přispěl k hlubšímu poznání sporných záležitostí. Roku 1691 vydal Bernoulli důležité pojednání, v němž podal vzorec pro délku poloměru křivosti a souvislosti mezi křivostí a evolutou křivky9. Vyšetřil logaritmickou spirálu, loxodromii10 a řetězovku11. Logaritmická spirála, kterou nazýval spirálou podi­ vuhodnou, jej tak zaujala, že si ji vyžádal na náhrobek s citátem Eadem mulata resurgo. Zabýval se nekonečnými řadami, dokázal divergenci harmonické řady, řešil kombinatorické úlohy. Roku 1696 předložil Johann matematikům problém brachystochrony12, kterou roku 1697 Jakob řeší v Acta Eruditorium; zároveň připojil k řešení izoperimetrický problém a vyzval bra­ tra k vědeckému zápasu. Polemika mezi oběma bratry vedla k položení základů variačního počtu, jenž byl zbudován Eulerem a Lagrangerem. V oblasti fyziky vyřešil problém složeného kyvadla; zde se objevuje základní myšlenka dÁlembertova principu13. V roce 1699 se stává spolu s bratrem členem Pařížské aka7

Předpokládejme, že v gravitačním poli zvolíme pevný bod a rovinu procházející tímto bodem. Izochrona je množina bodů v dané rovině, do nichž se hmotný bod dostane vlivem gravitačního působení ze zvoleného bodu za zvolenou časovou jednotku. 8 Symbol pro integrál pochází od Leibnize. 9 Evoluta křivky je množina středů křivosti v bodech této křivky. 10 Loxodromie je čára spojující dvě místa na glóbu a protínající všechny poledníky pod týmž úhlem. 11 Řetězovka je rovinná transcendentní křivka vytvořená gravitačním působením na ho­ mogenní, dokonale ohebné a neroztažné vlákno zavěšené mezi dvěma pevnými body. 12 Brachystochrona je křivka spojující dva body v gravitačním poli, po níž se vlivem gra­ vitačního působení dostane hmotný bod z jednoho zvoleného bodu do druhého za nejkratší dobu. 13 DAlembertův princip říká, že při pohybu mechanické soustavy jsou vnější síly v rov­ nováze se silami setrvačnými.

14

demie a v roce 1701 členem Berlínské akademie. Jeho vědecká bádání však nečekaně skončila jeho náhlou a předčasnou smrtí 16. srpna 1705. Pro úplnost dodám, že roku 1684 se Jakob Bernoulli oženil s Judith Stupanusovou. Z manželství pocházejí dvě děti, syn Nikolas a dcera.

Obrázek 1.1: Jakob Bernoulli

15

1.3

Ars conjectandi

Kombinatorikou a pravděpodobnostním počtem se Jakob Ber­ noulli zabýval v letech 1678 - 1685 a své poznatky shrnul v prv­ ním souvislém, i když nedokončeném spisu - Ars conjectandi K vydání tohoto spisu však došlo až v roce 1713, za značného při­ spění Nicolase I. Bernoulli14. Za své předchůdce v oblasti kombi­ natoriky označuje Jakob Bernoulli Schootena15, Leibnize, Wallise 16 a Presteta17, nikoliv však Pascala, tudíž lze předpokládat, že jeho Pojednání o aritmetickém trojúhelníku neznal. Vlastní dílo Ars conjectandi má 239 stran formátu A5 a je rozděleno do 4 částí. První část (str.l - 71) obsahuje plné znění Huygensova18 po­ jednání s názvem - O počínání při hře v kostky čili o počínání při hazardních hrách, které je opatřeno Bernoulliho poznámkami. Tyto poznámky jsou stěžejní pro celou první část a jimi Huy­ gensova pojednání daleko přesahuje. Jakob Bernoulli v těchto poznámkách zobecnil Huygensova zjištění a doplnil je svými po­ střehy. 14

Nicolas I. Bernoulli (1687-1759) matematik, právník, filozof. Synovec Jakoba a zároveň jeho žák, který již v roce 1704 dosáhl magisterského stupně; při této příležitosti disputo­ val o nekonečných řadách, k nimž se často později vrací. V roce 1709 dosáhl právnického licenciátu. Pro zajímavost uvedu - disertační práce pojednává o upotřebení pravděpodob­ nostního počtu při právnických záležitostech. V roce 1722 se stal profesorem logiky a v roce 1731 profesorem lenního práva na basilejské universitě. 15 Franciscus van Schooten mladší (1615-1690), profesor na universitě v Leydenu, autor z matematicko-historického hlediska významného díla Exercitationes mathematicae. 16 John Wallis (1616-1703) byl profesor geometrie na Oxfordu a člen Royal Society. Mimo jiné autor díla Arithmetica infinitorum (1655) nebo Treatise of Algebra both historical and practical with some additional treatises (1685). 17 Jean Prestet (7-1690) autor ve své době významné učebnice Elemens des Mathematiques, která dle Wallisova tvrzení obsahovala všechny tehdy známé algebraické poznatky. 18 Christiaan Huygens (1629 - 1695) - nizozemský fyzik, matematik a astronom; člen Královské spol. v Londýně a Akademie věd v Paříži. Patřil k nejvýznamnějším fyzikům své doby. V oblasti matematiky se zabýval infinitesimálním a pravděpodobnostním počtem. Lze jej považovat za zakladatele pravděpodobnostního počtu, autora prvního spisu z této oblasti O počínání při hře v kostky čili o počínání při hazardních hrách pocházejícího z roku 1657. Latinský originál nese název De ratiociniis in ludo ale.

16

Druhá kapitola19 (str. 72 - 137), která je předmětem mého studia, se výlučně věnuje kombinatorice a lze ji považovat za učebnici kombinatoriky. Bernoulli si byl vědom, že zčásti opa­ kuje známé výsledky, to ho však nakonec přivedlo k mnohem hlubšímu poznání, nežli si sám uvědomil. Tato část má zcela ma­ tematický charakter, kde se studují permutace, kombinace, va­ riace bez opakování i s opakováním. Z matematicko-historického hlediska je druhá část významná tím, že se zde poprvé objevují tak zvaná Bernoulliho čísla, což můžeme považovat za vrchol druhé části díla. Bernoulli tuto část rozdělil do devíti kapitol. I. kapitola obsahuje poznatky o permutacích, v kapitolách II.VI. se věnuje kombinacím a kapitoly VIL, VIII., IX. pojedná­ vají o „kombinacích ve spojení s permutacemi" (o variacích). K uspořádání jednotlivých kapitol bych podotkla, že Bernoulli na jednoduchém příkladu, který bývá rozvinut do složitějších podob, demonstruje pravidlo, které následně přesně formuluje a vše završí jednoduchým příkladem. Ve třetí části (str. 138 - 209) Bernoulli udělal značný krok mimo kombinatorická studia psaná dávno před ním a to pou­ žitím kombinatorických pravidel jako metod řešení různých zo­ becněných úloh s herní motivací, jako například hry v kostky. Jedná se tedy o sbírku kombinatorických úloh. Čtvrtá část (str. 210 - 239) se skládá z pěti kapitol a přesto, že je nedokončená, přesahuje význam předešlých částí i proto, že obsahuje redukovanou větu o velkých číslech, kterou dnes nazýváme Bernoulliho větou. Bernoulli v této části ukázal nový směr vývoje pravděpodobnostního počtu. Vydání díla Ars conjectandi můžeme považovat za završení období formování kombinatoriky. Další vývoj kombinatoriky je tímto dílem silně ovlivněn, dochází k navazování a rozšiřování Bernoulliho poznatků. Za všechny jeho následovníky jmenujme 19 Plný titul této části zní Artis conjectandis pars secunde, continens doctrinam de permutationibus combinationibus.

17

jednoho z největších matematiků všech dob Leonharda Eulera20.

JACOBi BERNOULLI,

ProfeíC Bafil. & utriufquc Societ. Rcg. Scientiar. GilL & PruC Sodal. MATHEMATICI

CELEIERJUMI,

ARS CONJECTANDI, OPUS POSTHUMUM. AatAH

T R A C T A T U S

D E SERIEBUS INFINITIS, Et E P 11 T o Ĺ A Gal lice feripta D E L Ü D O P I L A RETICULARIS.

B A S ILEiE, ImpennsTHURNISIORUM.Frattum. cid Iscc xiii.

Obrázek 1.2: Titulní stránka knihy Ars conjeetandi

20

Leonhard Euler (1707 - 1783) byl švýcarský matematik, fyzik, astronom. Působil v Pe­ trohradě a v Berlíně. Autor mnoha učebnic matematiky. Pracoval v teorii čísel a integrálů; zabýval se diferenciálními rovnicemi, variačním počtem, exponenciálními a goniometric­ kými funkcemi i úlohami s geometrickou tématikou. Známá je např. Eulerova úloha o 36 důstojnících.

18

Kapitola 2 Permutace 2.1

Permutace

Jakob Bernoulli nazývá permutacemi prvků ty změny, při kte­ rých se zachovává počet prvků, jejich uspořádání a poloha se však různě zaměňuje. Permutationen von Dingen nenne ich die Aenderungen, durch welche unter Beibehaltung derselben Anzahl von Dingen ihre Ordnung und Stellung verschiedentlich vertauscht wird. Otázka, kolikrát mohou dané prvky mezi sebou permutovat, je tedy shodná s otázkou, jak často se může jeden prvek mezi jinými přemístit, zaměnit své pořadí s ostatními prvky. V první části této kapitoly se Bernoulli věnuje počtu per­ mutací bez opakování. Při hledání počtu permutací prvků klade důraz na systematický postup od nejjednoduššího případu k pří­ padům složitějším. Ukazuje, že u jednoho prvku a je možné pouze jediné posta­ vení. U dvou prvků jsou možná dvě uspořádání, neboť na první místo můžeme umístit prvek a a následovat bude prvek b nebo na první místo můžeme umístit prvek b a následovat bude prvek a. 19

Tři prvky a, 6, c se poté mohou uspořádat tak, že na první místo umístíme písmeno a nebo b nebo c. Stojí-li prvek a na počátku, pak mohou oba zbývající prvky zaměnit svá pořadí právě dvakrát, jak to bylo ukázáno v předešlém případu, stejně tak stojí-li na počátku písmeno 6, popřípadě c. Tedy počet změn pořadí, počet permutací, je u třech prvků roven 3 - 2 = 6, totiž abc, acb, bac, bca, cab, cba. Jsou-li dány 4 prvky, pak můžeme každým písmenem obsadit první pozici, zatímco tři zbývající prvky mohou 6x zaměnit své postavení. Počet záměn pořadí je tedy roven 4 • 3 • 2 = 4 • 6 = 24. Ze stejného důvodu je možno po přidání pátého prvku e, pětkrát tolik změn, tedy 5 - 2 4 = 120. Zobecněním Bernoulli dostane, že počet permutací z n prvků je n-krát větší než z n — 1 prvků. První část kapitoly je uzavřena pravidlem pro určení počtu permutací z n prvků. Regel zur Auffindung der Anzahl aller Permutation für eine beliebige Zahl von Dingen: Man multiplicire alle ganzen Zahlen von 1 bis zur ge­ gebenen Zahl in ihrer natürlichen Reihenfolge ineinan­ der; das Product liefert die gesuchte Anzahl1. Ačkoliv bychom mohli toto pravidlo, stejně jako pravidla ná­ sledující, formulovat jako vetu, je záměrně ponecháván způsob Bernoulliho dikce. Předchozí pravidlo dnes vyjadřujeme takto: Pravidlo 2.1.1.

Počet permutací z n prvků je

P(n) = 1 • 2 • 3 • . . . • (n - 1) • n. 1

Pravidlo k nalezení počtu všech permutací z libovolného počtu věcí: Vynásobíme všechna celá čísla od jedné k danému číslu v jejich přirozeném pořadí; součin poskytne hledaný počet.

20

Pro názornost Bernoulli doplňuje tabulku s počtem permu­ tací. Počet prvků: 1 2 3 4 5 6 7 8 9... Počet permutací: 1 2 6 24 120 720 5040 40320 362880 ... Druhá část první kapitoly se věnuje permutacím s opaková­ ním. Hned na počátku Bernoulli upozorňuje, že počet permutací bez opakování z n prvků, tzn. počet permutací n prvků, kde se každý prvek vyskytuje právě jedenkrát, je větší, než počet permutační s opakováním z daného počtu prvků, tzn. než po­ čet permutací, kde se každý prvek vyskytuje alespoň jedenkrát. Což ilustruje na příkladu permutací s opakováním ze 4 písmen - a, &, c, d, kde se písmeno a 3x opakuje. Tedy - v případě, že by všechna písmena byla různá je možno získat l - 2 - 3 - 4 - 5 - 6 = 720 permutací. V situaci, kde se písmeno a 3x opakuje, a je tedy možné získat 1-2-3 = 6 záměn pořadí v případě jejich rozlišitelnosti, musíme dané permutační číslo 6x zmenšit. Počet permutací s opakováním ze 4 písmen, z nichž se libovolné jedno písmeno opakuje třikrát je roven ™ = 120. V případě, že se vedle třikrát opakujícího se písmena a, ještě dvakrát opakuje písmeno 6, zmenší se zjištěné permutační číslo ještě o | , tedy počet permutací s opakováním bude v daném případě roven l%'.'2\ — 420. Z tohoto příkladu Bernoulli opět vyvozuje pravidlo pro urční počtu permutací s opakováním.

21

Regel zur Auffindung der Permutationszahl, wenn einige Dinge gleich sind: Die Anzahl der Permutationen, welche die gegebenen Dinge, wenn sie sämmtlich von einander verschieden wären, zulassen würden, theile man durch alle Permu­ tationszahlen, welche zu den einzelnen Gruppen der mehrfach vorkommenden Dinge gehören2. Studenti středních škol znají dnes toto pravidlo takto: Pravidlo 2.1.1. Počet permutací s opakováním z n prvků, v nichž se jednotlivé prvky opakují A4, A:2, . . . , A;n-krát, je roven podílu počtu možných permutací n prvků a součinu počtu per­ mutací ze skupin opakujících se prvků, tedy p /'N _ 0Vh) -

r

(k1+k2+...+kn)\ (h2:.,k1)(V2:.,k2)...(h2:.,kn)'

Zbytek úvodní kapitoly se zabývá využitím permutací při zjiš­ ťování počtu možných přeskupení písmen slova (anagram), ale i celých slov. Zde bych upozornila pouze na latinský verš oslavu­ jící Pannu Marii: „Tot Tibi sunt dotes, Virgo, quot sidera coelo3." Tvorbou anagramů vzniklých přeskupením slov tohoto verše, jež by vyhovovaly požadavkům latinské metriky, se v 17. století za2 Pravidlo k nalezení permutačního čísla, jestliže jsou některé věci stejné: Počet permutací, které by připustily dané věci, jestliže by všechny byly navzájem různé, se dělí všemi permutačními čísly, která patří k jednotlivým skupinám několikanásobně se vyskytujících věcí. 3 Překlad tohoto verše by mohl znít: Tolik je tvých darů, Panno, jako je hvězd na nebi. Autorem verše je jezuitský kněz Bernhard Bauhusius (1575 - 1619), autor mnoha knih epigramů a duchovních písní.

22

bývalo mnoho učenců, mezi nimi například Erycius Puteanus 4 , Gerhard Johann Vossius5 či John Wallis. Jakob Bernoulli se v la­ tinském originálu spisu Ars conjectandi věnuje podrobnému ro­ zepsání všech anagramů, zachovávajících pravidla metriky. Při­ chází k závěru, že pravidlům latinské metriky vyhovuje pouze 3 312 permutací ze všech možných, kterých je 8! = 40 320. V německém překladu z roku 1899, které se stalo východiskem pro moji práci, je tato část vypuštěna. Permutace ve středoškolské učebnici. Tématem permutace se studenti zabývají poté, co proberou kapitolu s názvem variace. Permutace z n-prvků je zavedena jako uspořádaná n-tice sesta­ vená z těchto prvků tak, že se každý prvek v ní vyskytuje právě jednou. Pro větší představivost se někdy mluví o pořadí namísto o permutacích. Studenti jsou dále seznámeni se symbolem n!. Pro počet P(n) všech permutacích z n prvků je odvozen vzorec P(n) = l - 2 - . . . - n = n!. V rámci „okruhu skupiny s opakováním" se studenti zabývají permutacemi s opakováním. Permutace s opakováním z n prvků se zavádí jako uspořádaná fc-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje aspoň jednou. Počet permutací s opakováním z n prvků, v nichž se jednotlivé prvky opakují kifa ... fcn-krát je P (h,

hc

h \ — (fci+fc2+...+fcw)!

4

Erycius Puteanus nebo van der Putten (1574 - 1646) byl profesorem výmluvnosti, poz­ ději španělský historiograf působící v Miláně, především však dopisovatel, udržující neoby­ čejně rozsáhlou korespondenci jednak s vysoko společensky postavenými, ale i věhlasnými lidmi. Pro zajímavost v jeho pozůstalosti bylo nalezeno přes 16 000 dopisů. 5 Gerhard Jahann Voss latinsky Vossius (1577 - 1649) byl jeden z největších polyhis­ torů své doby s rozsáhlými vědomostmi nejen z oblasti filologické, teologické, historické a matematické. Autor díla De universae mathesios natura et constitutione liber. Mimo jiné v roce 1622 působil na univerzite v Laydenu - profesor výmluvnosti, roku 1643 profesor dějin na Athenaeu v Amsterodamu.

23

Kapitola 3 Kombinace 3.1

Obecně o kombinacích

Na středních školách jsou kombinace k-té třídy z n prvků zavá­ děny, jako skupiny prvků obsahující k různých prvků z daných n prvků, v nichž nezáleží na pořadí, tedy jako neuspořádané A:-tice sestavené z n prvků tak, že každý se v ní vyskytuje nej­ výše jednou. Zcela analogickým způsobem chápe kombinace i Bernoulli. Combinationen von Dingen sind Verbindungen solcher Art, dass aus einer gegebenen Anzahl von Dingen ei­ nige herausgenommen und mit einander verbunden wer­ den, ohne dass ihre Ordnung und Stellung irgendwie berücksichtig wird. Protože však kombinacemi se studenti zabývají až poté, co se se­ známili s variacemi, bývá počet kombinací k-té třídy z n prvků, jenž je na středních školách značen K(k, n), odvozen z počtu va­ riací V(/c, n). Bernoulli však studuje kombinace před variacemi, a tudíž získaná posloupnost poznatků je odlišná. První otázkou, kterou si Bernoulli klade, je počet všech mož­ ných kombinací n prvků. Počet možných kombinací n prvků chápe jako součet všech jedinců, dvojic, trojic, . . . , n-tic, při­ čemž je každá fc-tice (k G N, k < n) prvků vybrána právě jeden24

krát. Pro výčet možných kombinací prvků a, b, c, d,... využívá Bernoulli následující postup. Vytvoříme právě tolik řádků jako je prvků-písmen a to ná­ sledně: Na první řádek samostatně napíšeme písmeno a. Na druhý řádek nejprve samostatně napíšeme písmeno b, a poté b napíšeme ve spojení s písmenem a. (Protože pořadí pís­ men zůstává nepovšimnuto, jsou obě spojení ab, ba započtena jako jediné.) Na třetí řádek napíšeme nejprve samostatně písmeno c, poté ve spojení s písmeny a a b, tak vznikají dvojice ac a be a konečně ve spojení s dvojicí písmen ab, kdy dostaneme trojici abc. Obdobně pokračujeme při tvorbě následujících řádků, tedy na čtvrtém řádku se na prvním místě napíše samostatně pís­ meno d, poté jednotlivě ve spojení s písmeny a, b, c, následně ve spojení s každou dvojicí ab, ac, bc a konečně ve spojení s trojicí abc. Tak vzniknou nové dvojice ad, bd, cd, trojice, abd, acd, bed, a čtveřice abed , atd. Tím obdržíme schéma: a; b,ab; c, ac, bc, abc; d, ad, bd, cd, abd, acd, bed, abed; e,ae,be,ce,de, abe, ace, bce, ade, bde, ede, abce, abde, acde, bede, abede;

Držíme-li se tohoto Bernoulliho postupu, žádnou kombinaci ne­ přehlédneme a zároveň žádná kombinace nebude započtena dva­ krát. Odpověď na otázku, kolik je všech možných kombinací n prvků, Bernoulli nalézá na základě vlastnosti řádků schématu: Na libovolném řádku se daný prvek (písmeno) vyskytuje nej­ prve samostatně a následně ve spojení se všemi kombinacemi z 25

předchozích řádků. Nutně tedy platí: Na prvním řádku se objevuje jediná kombinace, na druhém řádku - dvě kombinace, na třetím řádku - čtyři kombinace, na čtvrtém řádku - osm kombinací, atd. Dostali jsme tak rostoucí geometrickou řadu s kvocientem 2. Geometrická řada s kvoci­ entem 2 a počátečním členem 1 má tu vlastnost, že libovolný člen této řady je vždy o jedničku větší než součet všech před­ chozích členů, neboli EjLi ak=(an+i — 1) a tedy počet kombinací na libovolném řádku je o jednu kombinaci větší než počet všech kombinací na řádcích předchozích. Z této vlastnost Bernoulli vy­ vozuje pravidlo pro stanovení počtu všech možných kombinací n prvků: Regel für die Bestimmung der Anzahl aller Combinationen, welche gegebene Dinge zu allen Classen bilden: Man multiplicire die Zahl 2 so oft in sich selbst, als die Anzahl der gegebenen Dinge angiebt, und substrahire davon 1; die Differenz ist die gesuchte Zahl1. Dnes bychom řekli: 3.1.1 Počet možných kombinací n prvků je roven n

Y,K(k,n) =

2n-l.

k=i

Protože existuje možnost, kdy z daných n prvků nevybereme žádný, upozorní Bernoulli, že skutečný počet možných kombi­ nací n prvků je roven

tK(k,n) = 2n. k=0 1

Pravidlo k určení počtu všech kombinací, které dané věci tvoří ve všech třídách: Vynásobíme číslo 2 samo sebou tak často, jako je počet daných věcí a odečteme 1; rozdíl je hledaný počet.

26

Pravidlo Bernoulli aplikuje na příklad, který již ve 12. století vyřešil zmiňovaný ibn Ezra. Příklad: Kolik různých konjunkcí planet Sluneční soustavy existuje? Protože 27 — 1 = 127, je počet konjunkcí planet Sluneční soustavy právě 127. V závěrečné poznámce Bernoulli ukazuje, že na libovolném řádku (s výjimkou prvního), je počet možných kombinací li­ chých tříd, tedy tříd s lichým počtem prvků roven počtu mož­ ných kombinací sudých tříd. Zobecněním tohoto tvrzení se Ber­ noulli dostane k zjištění, že počet možných kombinací lichých tříd (včetně k=l) je roven počtu možných kombinací sudých tříd (včetně k=0) a každé z těchto čísel je rovno polovině počtu všech možných kombinací n prvků, tedy \ • 2n = 2n~l.

3.2

Kombinace bez opakování v určitých tří­ dách; figurální čísla a jejich vlastnosti

Na úvod třetí kapitoly se Bernoulli záměrně vrací ke kapitole předchozí, konkrétně k výčtu všech kombinací. Zde ukazuje, že na libovolném řádku je počet dvojic roven součtu jedinců na předchozích řádcích, počet trojic je roven počtu dvojic na předchozích řádcích, počet čtveřic je roven počtu trojic, atd. Obecně je počet kombinací určité třídy na libovolném řádku ro­ ven součtu kombinací nejbližší nižší třídy na všech předchozích řádcích. Z čehož vyplývá: Jedinci, kteří se na každém řádku vyskytují právě jedenkrát, tvoří řadu 1, 1, 1, 1, 1, . . . - řada jednotek. Dvojice se na prvním řádku nevyskytuje, na druhém lx, na třetím 2x, na čtvrtém 3x, na pátém 4x, atd. Dvojice tvoří řadu 0, 1, 2, 3, 4, . . . - řada přirozených čísel. 27

F

Trojice se v prvním a druhém řádku nevyskytují, na třetím řádku je 1, na čtvrtém řádku jsou 3, na pátém řádku je jich 6, v šestém řádku 10, atd. Trojice tvoří číselnou řadu 0, 0, 1, 3, 6, 10, 15, . . . - řada trojúhelníkových čísel. Čtveřice se v prvních třech řádcích nevyskytují, na čtvrtém je 1, na pátém 4, na šestém 10, na sedmém 20, atd. Čtveřice tvoří řadu 0, 0, 0, 1, 4, 10, 20, . . . - řada čtyřúhelníkových čísel. Stejným způsobem určujeme počet pětic na jednotlivých řád­ cích - řadu pětiúhelníkových čísel - 0, 0, 0, 0, 1, 5, 15, 35, . . . , počet šestic - řadu šestiúhelníkových čísel - 0, 0, 0, 0, 0, 1,5, 21, . . . a takto můžeme při určování počtu kombinací ve vyšších třídách pokračovat až do nekonečna. Zde Bernoulli využije příležitosti, připomene pojem figurál­ ních (obrazcových) čísel a vytvoří tabulku figurálních čísel. V tabulce figurálních čísel označují římské číslice prvního řádku kombinační třídu, arabské číslice prvního sloupce počet prvků podléhající kombinacím.

171nr 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

i i i i i i i i i i i

ii. III. IV. V. VI. VIL VIII. IX. X. XI. XII.

0 1 2 3 4 5 6 7 8 9 10 11

0 0 1 3 6 10 15 21 28 36 45 55

0 0 0 1 4 10 20 35 56 84 120 165

0 0 0 0 1 5 15 35 70 126 210 330

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 6 0 0 0 0 21 7 1 0 0 0 56 28 8 1 0 0 126 84 36 9 1 0 252 210 120 45 10 1 462 462 330 165 55 11

0 0 0 0 0 0 0 0 0 0 0 1

Na tabulce figurálních čísel Bernoulli ukazuje některé její 28

význačné vlastnosti, jichž využívá. Jednotlivé vlastnosti však pouze slovně opisuje, což občas vede k jisté nepřehlednosti, proto jsem zde zavedla matematickou symboliku podobnou matico­ vému značení: Symbolem a^j rozumím člen tabulky figurálních čísel, nachá­ zející se v i-tém sloupci a j-tém řádku. Vlasntosti tabulky figurálních čísel. 1. Libovolný z-tý sloupec tabulky vždy začína i — 1 nulami. 2. První, druhý, třetí, ... od nuly různé členy sloupců, shora zleva šikmo dolů doprava, dávají čísla prvního, druhého, třetího, ... sloupce, tzn. jedná se o řadu jedniček, řadu při­ rozených čísel, řadu trojúhelníkových čísel, atd. 3. Pořadové číslo libovolného ž-tého sloupce je i + 1 členem z-tého sloupce. 4. Libovolný j-tý člen z-tého sloupce je roven součtu prvního až j — 1 členu i — 1 sloupce, neboli j-i a

hj — Yl

a

i-l,k-

k=l

5. Pro libovolný j-tý člen ž-tého sloupce platí

6. Členy každého řádku vzrůstají od jedné až po určitou nej­ vyšší hodnotu, od které stejným způsobem opět klesají. 7. Členy libovolného řádku jsou si mezi sebou rovny tím způ­ sobem, že první člen je roven poslednímu členu (člen po kterém následuje už jen nula), druhý člen je roven předpo­ slednímu, atd. v případě, že se řádek skládá z více nenulo­ vých členů. 29

8. Vybereme-li z tabulky figurálních čísel prvních n sloupců a řádků a sečteme-li členy každého sloupce, je součet prv­ ního sloupce roven součtu předposledního sloupce, součet druhého sloupce je roven součtu třetího sloupce od konce, třetí je roven čtvrtému od konce, atd. Zároveň součty členů sloupců vytvoří n+1 řádek, avšak s výjimkou prvního členu. Tedy například členy šestého řádku s výjmkou prvního členu, kterým je jednička, obdržíme, sečteme-li prvních pět členů pěti prvních sloupců. 1 1 1 1 1 5

0 0 0 0 1 0 0 0 2 1 0 0 3 3 1 0 4 6 4 1 10 10 5 1

9. Cleny libovolného n-tého řádku jsou koeficinty binomického rozvoje n — 1 mocniny dvojčlenu (a + 6), kde a, & G C. Například čtvrtý řádek udává koeficinty třetí mocniny bi­ nomického rozvoje dvojčlenu (a + b) a tedy (a + &)3 = a 3 + 3a2Ď + 3a&2 + Ď3. 10. Součet členů j-tého řádku je roven j — 1 mocnině dvojky, tedy 2= 1

Zároveň součet členů prvních n řádků je roven n

j

£ E ^ = 2" +1 -i. j=\ i=l

11. Dělíme-li členy libovolného i-tého sloupce (počínaje členem cbij nebo členem a ^ - i ) členy i — l sloupce (začínaje členem 30

a^_i5;_i), dostaneme členy aritmetické posloupnosti s dife­ rencí d — T-^-T. z—1

Dělíme-li například členy čtvrtého sloupce členy třetího sloup­ ce, obdržíme aritmetickou posloupnost s diferenccí d = | a tedy dělitel dělenec podíl dělitel dělenec podíl 1 1 3/3 1 0 0 4 4/3 3 3 1 1/3 6 10 5/3 6 4 2/3 10 20 6/3 10 10 3/3 15 35 7/3 15 20 4/3 12. Poměr mezi součtem prvních n členů j-tého sloupce a nnásobku n-tého členu tohoto sloupce je roven poměru 1 : j . Nebo také poměr mezi součtem j-tého až n-tého členu j tého sloupce a (n — j)-násobku n + 1 členu tohoto sloupce je roven poměru 1 : j . Například:

0 3 1 3 2 3 3 3 6 :12 =1 :2

1 5 2 5 3 5 4 5 10 :20

0 0 0 1 4 10 =1 :2 15

10 10 10 10 10 10 :60 =1 :4

1 56 4 56 10 56 20 56 35 56 70 :280 =1 :4

Vlastnost číslo 12 považuje Bernoulli za nejdůležitější a pro účel kapitoly nejužitečnější, proto ji postupnými kroky odvozuje prostřednictví „lemmat". 31

L e m m a 1. Součet n členů prvního sloupce je roven n. L e m m a 2. Poměr mezi součtem prvních j členů j-tého sloupce a j-násobku j-tého členu tohoto sloupce je roven 1 : j , tedy j

L e m m a 3. V libovolném j - t é m sloupci je poměr mezi n-tým a n + 1 členem roven poměru (n — j):n, tedy a^n : a^n+i = (n - j ) : n L e m m a 4. Protože v libovolném j - t é m sloupci je poměr mezi součtem n členů tohoto sloupce a n-násobku n-tého členu roven poměru 1 : j a protože v j + 1 sloupci je poměr mezi součtem n členů tohoto sloupce a n-násobku n-tého členu roven poměru 1 : j + 1, zůstane poměr v j + 1 sloupci po přidání n + 1 členu mezi součtem n + 1 členů j + 1 sloupce a n + 1 násobku n + 1 členu tohoto sloupce stejný a to 1 : j + 1. L e m m a 5. Protože v libovolném j - t é m sloupci je poměr mezi součtem n členů tohoto sloupce a n-násobku n-tého členu roven poměru 1 : j , je v (j + 1) sloupci poměr mezi souč­ tem k členů tohoto sloupce a fc-násobku A;-tého členu roven poměru 1 : (j + 1). Vlastnost dvanáct tabulky figurálních čísel můžeme tedy zfor­ mulovat jako větu: Věta: V tabulce figurálních čísel je poměr mezi součtem n členů j-tého sloupce a n-násobku n-tého členu tohoto sloupce a stejně tak poměr mezi součtem j-tého až n-tého členu j tého sloupce a (n — j) násobku n + 1 členu tohoto sloupce roven 1 : j , tedy n

J2 o,j,k • najtn = 1 : j , nebo k=i

32

n

Y, Hk : (n - j K > + i = 1 : j . k=j

Z vlastností 1, 4, 12 tabulky figurálních čísel Bernoulli vyvo­ zuje: Důsledek 1. Součet prvních n členů A;-tého sloupce je roven

ODůsledek 2. Libovolný n-tý člen fc-tého sloupce je roven (£lj). Vrchol třetí kapitoly, ale i celé druhé části díla Are conjectandi, je umístěn právě zde, kde se Bernoulli zabývá součtem prvních, druhých, . . . , desátých mocnin řady přirozených čísel. Protože n-tý člen druhého sloupce tabulky figurálních čísel je roven číslu n — 1 a protože pro součet těchto členů platí

S(n - 1) = g) = üigÜ můžeme psát S(n - 1) = S(n) - S(l) = %*. Poněvadž S(l) je roven součtu n jedniček, tedy 5(1) =n platí S(n) = \n2 + \n. Stejně tak n-tý člen třetího sloupce je podle předchozího dů­ sledku roven (n~x) = \n2 — | n + 1 a součet členů třetího sloupce od 1 po n je roven Q) = | n 3 — \nL + | n a tedy

s(y-in+i)=y-y + in. Proto

S ( | n 2 - f n + l)= S(±n2) - 5(|n) + S(l)=|S(n2) - §S(n) + 5(1). 33

Protože jsou hodnoty S(n) a S(l) známé, můžeme napsat S(n 2 )=±n 3 - \n2 + \n. Zcela analogickým způsobem můžeme pokračovat při získá­ vání součtu vyšších mocnin řady přirozených čísel. iV-tý člen čtvrtého sloupce je roven ( r l 3 1 )=|^ 3 — n2 + | n — 1 a součet prvních n členů je roven (™)=gn4 — n 3 + y n 2 — n, proto je S(\v? -n2 + f n - l ) = | n 4 - n 3 + ^ n 2 - n a I S ( n 3 ) = X - n 3 + ±±n2 - n + S(n 2 ) - %S(n) + S(l). Dosadíme-li již nalezené hodnoty 5(n 2 ), 5(71), 5(1), obdržíme pro součet třetích mocnin n přirozených čísel

S(n*)=y + |n3 + \n\ Snadno můžeme obdržet následující tabulku součtu mocnin n přirozených čísel.

34

Součet mocnin přirozených čísel S(n) S(n2) S{n3) 4

= =

=

5(n ) S(n5) S{n6)

=

S(n?)

=

S{n*) S(n') S{nw)

=

= —

¥2 y y y y y y y

=

>

1 0

=

>

n

+5n

+y +y +y +y +y +y +y +y +y°

+±n

+y +y +T2^

+y

30

U

2

-±n

-y

12 "

+>2

24"

+y +y +y

15

n

-77

10'* 7

-ln

+±n

6

+y +y

+ln 5

30

n

-Ä-2

-y

+ěn

Důkladným studiem tabulky Bernoulli objevil jisté pravi­ delně se opakující zákonitosti, pomocí nichž pak vyjadřuje sou­ čet libovolné A;-té mocniny řady přirozených čísel, tedy

Písmena A, í?, C, D)... jsou přiřazeny k řadám ve významu 5(n 2 ), S(n4), S(n6), S(ns)..., a mají tu vlastnost, že zbývající koeficinty vyskytující se u příslušného mocninného součtu dopl­ ňují na jedničku, tedy A = \,B = - ^ , C = ±, D = - ^ , neboli například l + l + l~IŠ + 1 + D = 1 Toto téma Bernoulli završuje příkladem. Příklad: Určete součet desátých mocnin prvních tisíce čísel. Řešení: S pomocí předchozí tabulky snadno zjistíme, že hle­ dané číslo je rovno: Sř(100010)=1?r100011 + il000 1 0 +|l000 9 -1000 7 +1000 5 -il000 3 + ^ 1 0 0 0 - 91 409 924 241 424 243 424 241 924 242 500. 35

Poznámka: Pro čísla skrývající se pod písmeny A, B, C, D ... Euler zavedl označení Bernoulliho čísla. Sám Bernoulli určil prv­ ních pět čísel a Euler dalších deset. Dnes je využíváme například k vyjádření některých neurčitých integrálů nekonečnou řadou.

3.3

Kombinace bez opakování v určité třídě

V předchozí kapitole Bernoulli odvodil, že pro libovolné A;, n G TV, kde k < n tvoří počet kombinací fc-té třídy z n prvků a kde n nabývá postupně všech hodnot, odpovídající řadu figurálních čísel. V této kapitole se Bernoulli zabývá, součtem prvních n členů A:-tého sloupce, neboli počtem kombinací k-té třídy z n prvků. Pravidlo pro stanovení počtu kombinací k-té třídy z n prvků zní: Regel für die Bestimmung der Anzahl aller Combinationen ohne Wiederholung zu einer bestimmten Classe: Man bilde sich zwei aritmetische Reihen, deren eine von der Anzahl der zu combinirenden Dinge an fällt, deren andere von 1 an steigt und welche beide die Di­ fferenz 1 und so viele Glieder haben, als die gegebene Classenzahl Einheiten hat. Der Quotient gebildet aus dem Producte der Glieder der ersten Reihe dividirt durch das Product der Glieder der zweiten Reihe liefert die gesuchte Anzahl von Combinationen2. Tvrzení předchozího pravidla můžeme vyjádřit: 2

Pravidlo k určení počtu všech kombinací bez opakování v určité třídě: Vytvoříme dvě aritmetické řady, z nichž jedna klesá od počtu daných věcí a druhá vzrůstá od 1 a které obě mají diferenci rovnu 1 a právě tolik členů, jako je jednotka čísla třídy. Podíl tvořený ze součinu členů první řady dělené součinem členů druhé řady poskytne hledaný počet kombinací.

36

Pravidlo 3.3.1 Počet kombinací (bez opakování) k-té třídy z n prvků je roven _ n(n-l)(n-2)...(n-k K[k n)

'

-

+ l) _

l-2-3-...-ib

ín\

" U •

Z pravidla Bernoulli odvozuje „dodatky", které bychom dnes mohli formulovat takto: D o d a t e k 1. Počet kombinací k-té třídy z n prvků roste s ros­ toucím fc, pokud je k < ^ y ^ ; jestliže je k > ^ y ^ , pak počet kombinací klesá s rostoucím k. D o d a t e k 2. Počet kombinací k-té třídy z n prvků je roven po­ čtu kombinací /-té třídy z n prvků právě tehdy, když platí k + l = n. Tyto třídy Bernoulli nazývá paralelními třídami D o d a t e k 3. Počet kombinací A:-té třídy z n prvků je při sudém n největší, je-li k = | , při lichém n je počet kombinací největší v A:-té a (k + l)-vé třídě, je-li k = ^ y ^ . D o d a t e k 4. Počet kombinací k-tiídy z n prvků je roven počtu permutací těchto prvků, ze kterých jsou „vyjmuty" k-té a (n — /c)-té permutace. Počet kombinací je roven

K{k)n)

P(n)

P(k)-P(n-ky

D o d a t e k 5. Počet kombinací k-té třídy z n-prvků je roven součtu počtu kombinací v k-té a v (k — l)-vé třídě z (n — 1) prvků, neboli K(k, n) = K{k, n-l)

+

K(k-l,n-l).

D o d a t e k 6. Počet kombinací v sudých třídách z n prvků je roven počtu kombinací v lichých třídách z těchto prvků a každé z čísel je rovno polovině počtu možných kombinací. 37

V rámci této kapitoly se Bernoulli také zabývá odpovědí na otázku, v kolika kombinacích se může vybraný prvek nebo sku­ pina prvků nacházet samostatně nebo ve vzájemném spojení. A protože řešení konkrétní úlohy bývá stejně tak „složité" jako ře­ šení obecné situace, provádí Bernoulli následné zobecnění úlohy: Kolik kombinací k-té třídy z n prvků lze vytvořit tak, aby každá k-tice prvků obsahovala všechny prvky A,B,C,..., jejíž počet je b a nevyskytoval se v ní žádný z prvků D,E, Počet vybraných prvků A, B, C , . . . , D, E,... je roven m (kde m > k nebo m < k). Řešení: Tvoříme fc-tici prvků, ze které právě b prvků známe, zbývá vybrat (k — b) prvků. Vybereme-li tyto prvky z množiny (n — rn), nebude se v dané (k — 6)-tici vyskytovat žádný z prvků A, J3, C , . . . , D, JB, ... a tedy kombinací k-té třídy z n prvků je '

v

ín—m\

pravé ( Ä _J. Nejsou-li prvky A, 5 , C , . . . pevně stanoveny, pak existuje právě (™) možností, jak je vybrat a celkový počet kombinací je tedy (™)-krát větší, je roven (™)(7-T)Je-li n — m < k — 6, pak neexistuje žádná kombinace, která by splňovala předchozí podmínky. Následně Bernoulli umístil několik konkrétní příkladů. 1. V kolika kombinacích se vyskytuje vybraný prvek A? Pro m = b = 1 je hledaný počet kombinací roven (^1™) = (i:i1).Dalfiplati(I:i):(i)=fc:n. 2. Kolik kombinací obsahuje prvek A, nesmí-li tato kombinace obsahovat prvek Bl Protože je m = 2 a b — 1, má hledaný počet hodnotu ( ^ ) ; dvojnásobek tohoto čísla udává, v kolika kombinacích se nachází vždy jeden z prvků A, B.

38

3. V kolika kombinacích se vyskytují prvky A,B současně? V tomto případě je hledaná hodnota rovna (^I^)? ne boť m=b=2. 4. Ptáme-li, se v kolika kombinacích se žádný z prvků A a, B nevyskytuje, obdržíme číslo ( \ 2 ) , protože m = 2 a b = 0. 5. Kolika způsoby lze z n-prvků vybrat trojici prvků tak, aby každá trojice obsahovala vybrané prvky A, B a neobsaho­ vala vybraný prvek C? Zde j e m = 3 a 5 = 2 a tudíž je hledané číslo rovno (^I^). Protože ze tří prvků můžeme vybrat vždy třikrát dva prvky, zvýší se počet kombinací, ve kterých se vždy dva ze tří vybraných prvků vyskytují na 3 (£"2). Obdobným způsobem kladení otázek a hledaní odpovědí mů­ žeme pokračovat dále.

3.4

Počet kombinací s opakováním

Ve všech předchozích kapitolách, které se věnovaly kombina­ cím, jsme předpokládali, že každý prvek se v příslušné fc-tici prvků vyskytuje nejvýše jeden-krát. Nyní tuto podmínku Ber­ noulli změní tak, že každý prvek se bude moci v příslušné fc-tici opakovat a to nejvýše A:-krát. Chceme-li vytvořit všechny kombinace s opakováním z prvků a, 6, c, d,... budeme postupovat obdobným způsobem, který Ber­ noulli již ukázal v kapitole 3.1. Vytvoříme právě tolik řádků jako příslušných prvků-písmen a každý z těchto řádků bude začínat jedincem. Hledáme-li dvojice každého řádku, musí se počáteční písmeno zkombinovat nejen s jedinci z předchozích řádků, ale musí vytvo­ řit dvojici i samo se sebou. Již na prvním řádku získáme jednu 39

dvojici - (aa), na druhém řádku to jsou dvojice dvě (ab, 66), na třetím - tři (ac, bc, cc), atd. Obdobným způsobem pokračujeme při tvorbě trojic. Na libo­ volném řádku vznikne trojice buď spojením jedince příslušného řádku a všech dvojic na předešlých řádcích nebo kombinací da­ ného jedince se sebou samým či s jedinci z předchozích řádků. Tedy na prvním řádku vznikne trojice aaa, na druhém řádku to jsou již trojice tři aab, abb, bbb a konečně na třetím řádku získáme šest trojicí - aac, abc, 66c, acc, bcc, ccc, atd. Takto můžeme snadno a přehledně pokračovat při tvorbě kombinací s opakováním vyšších tříd a obdržet tím následující schéma: a, aa, aaa] 6, ab,66, aa6, a66,666; c, ac, bc, cc, aac, abc, 66c, acc, bcc, ccc; d, ad, bd, cd, dd, aad, abd, bbd, acd, bed, ced, add, bdd, edd, ddd;

Prohlédneme-li si pozorně toto schéma, zjistíme, stejně jako Bernoulli: Počet jedinců každého řádku vytvoří řadu jedniček, počet dvojic vytvoří řadu přirozených čísel, počet trojic - řadu trojú­ helníkových čísel a počet kombinací ve vyšších třídách vytvoří odpovídající řady figurálních čísel vyššího řádu. Vynesením jednotlivých řad do příslušných sloupců získáme Pascalův trojúhelník, Bernoulli však mluví o kombinační ta­ bulce. Kombinační tabulka se od tabulky figurálních čísel, kte­ rou jsme vytvořili v kapitole 3.2., liší tím, že libovolná řada čísel začne členem 1, a nikoliv příslušným počtem nul.

40

XII. 1.n. III. IV. V. VI. V I L VIII. IX. X. XL 1 1 1 1 1 lHnr i 1 1 1 1 1 7 8 2 i 2 3 4 5 6 9 10 11 12 28 36 45 3 i 3 6 10 15 21 55 66 78 84 120 165 4 i 4 10 20 35 56 220 286 364 715 1001 1365 5 i 5 15 35 70 126 210 330 495 6 i 6 21 56 126 252 462 792 1287 2002 3003 4368 7 i 7 28 84 210 462 924 1716 3003 5005 8008 12376 8 i 8 36 120 330 792 1716 3432 6435 11440 19448 31824 9 i 9 45 165 495 1287 3003 6435 12870 24310 43758 75582 10 i 10 55 220 715 2002 5005 11440 24310 48620 92378 167960 11 i 11 66 286 1001 3003 8008 19448 43758 92378 184756 352716 12 i 12 78 364 1365 4368 12376 31824 75582 167960 352716 705432

Římské číslice prvního řádku označují kombinační třídu, arabské číslice prvního sloupce počet kombinovaných věcí. Na kombinační tabulce si Bernoulli záměrně povšiml násle­ dujících vlastností: Vlastnost 1. Členy libovolného fc-tého sloupce jsou po řadě rovny členům k-tého řádku. Vlastnost 2. Pro k-tý a (k + l)-vý sloupec platí, že součet prv­ ních n členů fc-tého sloupce je roven n-tému členu (k + 1)vého sloupce, neboli n 2^ ak,j

=

a

k+l,n-

Díky těmto vlastnostem a vlastnosti číslo 12 tabulky figu­ rálních čísel Bernoulli snadno zjišťuje součet členů libovolného sloupce a tím také počet kombinací s opakováním v libovolné třídě.

41

Předpokládejme tedy, že počet prvků, které kombinujeme, je roven n. Pak je počet všech jedinců roven součtu n členů první řady, nebo také n-tému členu druhého sloupce, je roven n. Druhou řadu pomyslně doplníme jednou nulou. Počet členů této řady je nyní roven (n + 1). Vynásobíme-li polovinu tohoto čísla n-tým členem druhé řady, tedy n ^+ ? získáme počet dvojic, počet kombinací druhé třídy z n prvků a také n-tý člen třetí řady. Doplníme-li třetí řadu dvěmi nulami, je počet jejích členů roven (n + 2). Vynásobíme-li třetinu tohoto čísla n-tým členem druhé řady, získáme součin ~hl^~ a tedy počet všech trojic a také n-tý člen čtvrté řady. Stejným způsobem najdeme součet prvních n členů k-tého sloupce. Počet všech fc-tic, počet kombinací fc-té třídy z n prvků, či n-tý člen (k + l)-vého sloupce je roven n(n+l)(n+2)...(n+fc-l) _

fn+k-l\

Je-li k > n, upozorňuje Bernoulli, že čitatel a jmenovatel předchozího zlomku můžeme krátit číslem n(n + l)(n + 2 ) . . . k a tím obdržíme (fc+l)(fc+2)...(fc+n-l) _ (k+n-l\ l-2-...-(n-l) ~~ V n-l ) '

Tento zlomek současně udává součet prvních (A; + 1) členů v (n — 1) řadě. Tedy platí, že součet prvních n-členů v A;-té řadě se rovná součtu prvních (k + 1) členů v (n — 1) řadě. Což je velmi pěkná vlastnost horní tabulky. Zobecněním tvrzení tohoto odstavce se Bernoulli dostane k pravidlu, jež nám určí počet kombinací s opakováni fc-té třídy z n prvků a které můžeme formulovat takto: Pravidlo 3.4.1. Počet kombinací s opakováním k-té třídy z n prvků je roven r^n

Ko n)

^

^

=

n(n + l)(n + 2 ) . . . ( n +

1 . 2 . 3 . ....* 42

fc-l)

=

ín +

[

k-l\

kj*

V knize Wahrscheinlichkeitsrechnung je dané pravidlo uve­ deno takto: Regel für die Bestimmung der Anzahl aller Combinationen mit Wiederholung zu einer bestimmten Classen: Man bilde zwei steigende aritmetische Reihen, deren eine mit der Anzahl der zu combinirenden Dinge und deren andere mit 1 beginnt, welche beide die Diffe­ renz 1 und soviele Gliedern haben, als die Classenzahl Einheiten hat. Das Product aus den Gliedern der ers­ ten Reihe dividirt durch das Product aus den Gliedern der letzten Reihe giebt die gesuchte Zahf. Protože součet n členů prvních fc-sloupců je roven součtu dru­ hého až (n + l)-vého členu /c-tého sloupce, je počet možných kombinací s opakováním A:-té třídy z n prvků pro k nabývající postupně všech hodnot 1,2,3,..., k o jedničku menší než počet kombinací s opakováním k-té třídy z (n + 1) prvků, neboli Z K0(j,n) = K0{k,n+

1)-1.

3= 1

Dále Bernoulli připomíná, že jednotlivé fc-tice z (n + 1) prvků neobsahují prvek n + 1 vůbec nebo právě lx, 2x, . . . , kx. Počet fc-tic, ve kterých se n+1 prvek nevyskytuje, je roven počtu fc-tic z n prvků. Počet /c-tic, ve kterých se prvek n + 1 vyskytuje právě jedenkrát, je roven počtu (k — l)-tic zbývajících n věcí. Obdobně počet /c-tic, ve kterých se prvek n + 1 vyskytuje právě dvakrát, je roven počtu (k — 2)-tic z n prvků, atd. Kromě toho je zde k-tice prvků, která prvek n + 1 obsahuje právě /c-krát. To však 3

Pravidlo pro stanovení počtu všech kombinací s opakováním v určité třídě: Vytvoříme dvě rostoucí aritmetické řady, z nichž jedna začíná počtem kombinovaných věcí a druhá jedničkou, které obě mají diferenci rovnu jedné a právě tolik členů, jako je jednotka čísla třídy. Součin členů první řady dělené součinem členů druhé řady dá hledané číslo.

43

vede k obdobnému závěru a to, že počet k-tic z n +1 prvků je o jednu kombinaci větší než počet kombinací k-té třídy z n prvků pro k = 1, 2 , . . .fc,nebo se rovná počtu kombinací /c-té třídy z n prvků pro k = 0,1, 2 , . . . &, tedy E ^ 0 ( j » = ^o(A;,n + l ) - l J'=l

nebo A;

Z čehož vyplývá následující pravidlo: Regel für die Bestimmung der Anzahl von Combinationen mit Wiederholung zu mehreren von 0 an aufeinanderfolgenden Classen: Man bilde zwei steigende aritmetische Reihen, deren eine mit der um 1 vermehrten Zahl der Dinge und de­ ren andere mit 1 beginnt, welche beide die Differenz 1 und so viele Glieder haben, als die grösste Classenzahl Einheiten hat. Ist aber diese grösser als die Anzahl der Dinge, so ist es vorteilhafter, die erste Reihe mit der um 1 vermehrten grössten Classenzahl zu beginnen und von jeder Reihe so viele Glieder zu nehmen, als Dinge gegeben sind. Dividirt man dann das Product aus den Gliedern der ersten Reihe durch das Product aus den Gliedern der letzten Reihe, so giebt der Quotient die gesuchte Anzahl aller Combination (einschliesslich der Nullion)4. 4 Pravidlo k určení počtu kombinací s opakováním z několika od nuly následujících tříd: Vytvoříme dvě rostoucí aritmetické řady, z nichž jedna začíná o jedničku větším číslem než je počet věcí a druhá začíná jedničkou, které obě mají diferenci rovnu 1 a tolik členů, jako je jednotka nejvyšší třídy. Je-li tato jednotka větší než počet věcí, je výhodnější první řadu začít číslem o jedničku větším, než je největší číslo třídy a z každé řady vzít tolik členů jako daných věcí. Dělíme-li potom součin členu první řady součinem členů druhé řady, dá podíl hledaný počet všech kombinací (včetně té, kdy jsme nevybrali žádný prvek).

44

Pravidlo 3.4.2. Počet kombinací s opakováním A;-té třídy z n prvků, kde k nabývá postupně všech hodnot 0, 1, 2, . . . , k je roven: Je-li k < n, je počet kombinací s opakováním k-té třídy z n prvků, kde k nabývá postupně všech hodnot 0, 1, 2, . . . , k roven JTO

oU

'

j

~

1-2-3-....Jfc

Je-li k > n, je počet kombinací s opakováním k-té třídy z n prvků, kde k nabývá postupně všech hodnot 0, 1, 2, . . . , k roven l • z • ... • n

j=o

3.5

Počet kombinací s omezeným opaková­ ním

Pod tímto tajemným názvem se skrývá kapitola, hledající od­ pověď na otázku, kolik existuje kombinací z n prvků a, Ď, c,..., nesmí-li se prvek a v kombinacích opakovat více než fc-krát, pr­ vek b více než /-krát, prvek c více než m-krát, atd., kde /c, /, m , . . . G AT, respektive kolik existuje všech dělitelů veličiny akblcm... a tato otázka se stává těžištěm celé kapitoly. Postup hledání všech dělitelů Bernoulli vyložil na příkladu veličiny a564c3d2. Jedním z dělitelů veličiny a564c3d2 je číslo 1, v rámci kombi­ nací nedošlo k výběru žádného prvku. Samotný prvek a nám poskytne právě tolik dělitelů, jako je hodnota jeho exponentu, tedy pět dělitelů - a, a2, a?, a4, a?. Požadujeme-li, aby dělitel veličiny obsahoval prvek b samo­ statně nebo ve spojení s prvkem a, získám šest nových děli­ telů tvaru 6, ab, a26, a36, a46, a56. 3x6 nových dělitelů obdržíme, požadujeme-li, aby dělitel obsahoval prvek b ve druhé, třetí a čtvrté mocnině. Tedy nalezli jsme 6 • 5 = 30 dělitelů veličiny aWd2. 45

Spojíme-li každého z 30 obdržených dělitelů s prvkem c v jeho první, druhé a třetí mocnině, získáme dalších 3 • 30 = 90 dělitelů. Vynásobíme-li každýho ze 6 • 5 • 4 = 120 dělitelů prvkem d nejprve v prvé a následně v druhé mocnině, obdržíme 2 • 120 = 240 nových dělitelů. Celkový počet dělitelů veličiny a564c3d2, respektive počet všech kombinací prvků a, Ď, C, d, v nichž se prvek a smí vyskytovat nej­ výše pětkrát, prvek b nejvýše čtyřikrát, prvek c nejvýše třikrát a prvek d nejvýše dvakrát, je roven 6 • 5 • 4 • 3 = 360. Z tohoto postupu je zřejmé, že přidáním libovolného prvku se počet dělitelů zvýší právě tolikrát, jako mocnina daného prvku navýšená o jedničku. Zobecněním předchozího příkladu a tímto tvrzením se Bernoulli dostane k pravidlu, jež určí počet všech dělitelů libovolné veličiny. Regel um die Anzahl aller Theiler einer beliebigen Grösse oder aller Combinationen mehrerer Dinge, von denen einige einander gleich sind zu bestimmen: Man vermehre die Exponenten, mit welchen die eine gegebene Grösse bildenden Buchstaben in derselben vor­ kommen, um 1 und multiplicire die so vergrösserten Zahlen ineinander. Das Product derselben ist gleich der Anzahl aller Theiler der gegebenen Grösse oder aller Combinationen, welche die jene Grösse zusam­ mensetzenden Buchstaben bilden können. Von dieser Zahl ist 1 zu subtrahiren, wenn man die Eins von den Theileren oder die Nullion von den Combinationen ausschliessen wiW. 5 Pravidlo určující počet všech dělitelů libovolné veličiny nebo všech kombinací více věcí, které mohou být navzájem stejné: Zvětšíme exponenty, ve kterých se vyskytují písmena tvořící danou veličinu, o jedničku a tato zvětšená čísla dohromady vynásobíme. Součin je počet všech dělitelů dané veli-

46

Toto pravidlo můžeme zformulovat takto: Pravidlo 3.5.1. Počet všech dělitelů veličiny akblcm ..., tedy počet všech kombinací prvkům, z nichž se veličina skládá, je roven součinu jejich mocnin navýšených o jedničku, tedy K{k,n) = {k + l)(l + l)(m +

l)...

Ze získaného čísla odečteme jedničku, chceme-li vyloučit ze všech dělitelů dělitele 1, či z kombinací tu, kdy nevybereme žádný z prvků. Poznámka: Je-li počet prvků tvořící daný výraz roven n a vyskytují-li se všechny prvky ve stejné mocnině p, obdržíme právě (p + l)n dělitelů. Je-li speciálně p = 1, je počet všech kombinací roven 2 n , což se zcela shoduje se závěrem kapitoly 3.1. Zabýváme-li se otázkou, kolik existuje všech dělitelů stejné di­ menze, využijeme postup velmi podobný tomu, který Bernoulli již využil při řešení úlohy devět první části spisu Ars conjectandi Vytvoříme tabulku, kde čísla sloupců odpovídají všem možným dimenzím dané veličiny, respektive třídám kombinací. Postup vyplnění tabulky pak probíhá, při využití příkladu z úvodu ka­ pitoly, následně: Do prvních šesti sloupců vepíši šest jedniček a vytvořím tak první řádek tabulky. Šesti jedničkami vyplníme i druhý, třetí, čtvrtý a pátý řádek, avšak každý následující řádek posuneme o jedno místo (sloupec) doprava oproti řádce předcházející. Vypl­ níme tolik řádků, jako je hodnota exponentu prvku a. Následně sečteme jedničky v příslušných sloupcích, čímž zís­ káme řádek s čísly 1, 2, 3, 4, 5, 5, 4, 3, 2, 1. Tento řádek opíšeme činy nebo všech kombinací, které mohou vytvořit písmena dané veličiny. Z daného čísla odečteme jedničku, jestliže chceme vyloučit možnost, kdy nevybereme žádný prvek či z dělitelů jedničku.

47

4x (mocnina prvku b) pod sebe opět tak, že každý následující řádek je posunut o jeden sloupec doprava a sečteme nově ve­ psané členy jednotlivých sloupců a obdržíme řádek 1, 3, 6, 10, 14, ... Tento řádek opíšeme stejným způsobem 3x pod sebe a opět sečteme nově vepsané členy sloupců a obdržíme řádek 1, 4, 10, 19, ... Získaný řádek přehledně vykazuje nejen počet dě­ litelů příslušných dimenzí, tedy počet kombinací s opakováním určitých tříd, ale také součet čísel tohoto řádku je roven počtu všech dělitelů výrazu a?b4c3d2. Tedy:

5

a

5 4

a 6

aW aWd 2

[o_ i HT i

2 3 4 5 6 7 8 9 10 11 12 13 14

1 1 i 1 1 1 1 1

i2 3 4 5 5 1 2 3 4 1 2 3 1 2 i 3 6 10 14 1 3 6 10 1 3 6

5 4 3 17 14 10

1 1 1 1 4 5 5 4 18 17 14

1 1 1 3 4 5 5 17 18 17

1 1 2 3 4 5 14 17 18

1 1 2 3 4 10 14 17

1 2 3 6 10 14

1 2 3 6 10

1 1 3 1 6 3 1

i 4 10 19 30 41 49 52 49 41 30 19 10 4 1

48

Kapitola 4 Variace 4.1

Variace bez opakování

V kombinacích, kterými jsme se dosud zabývali, jsme nebrali na zřetel pořadí prvků, zajímali jsme se o neuspořádané k-tice prvků. V jistých situací je však zapotřebí rozlišit pořadí prvků, což je nejvíce patrné u slov a čísel. Na středních školách jsou variace k-té třídy z n prvků (k,n £ N,k < n) zaváděny jako uspořádané k-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje nejvýše jedenkrát. Počet variací k-té třídy z n prvků pak bývá zpravidla odvozen užitím kombinatorického pravidla součinu, tedy V(k, n) = n{n - l)(n - 2 ) . . . (n - k + 1), a poté, co jsou studenti seznámeni se symbolem n\ je vzorec pro počet variací fc-té třídy z n prvků vyjádřen ve tvaru

Na úvod této kapitoly bych chtěla poznamenat, že samotné slovo „variace" Bernoulli nepoužívá a význam slova opisuje, mluví o p er mutuj í cích kombinacích. V souladu s tímto opisem slova variace Bernoulli řeší otázku počtu variací k-té třídy z n

49

prvků na základě závěrů předchozích kapitol. Neboť všechny va­ riace k-té třídy z n prvků dostaneme, utvoříme-li všechny kom­ binace k-té třídy z n prvků a v každé kombinaci permutujeme prvky. Počet kombinací A;-té třídy z n prvků je Q) a každá kom­ binace poskytuje 1 • 2 • 3 - ... • k — k\ permutací. Tedy počet variací A:-té třídy z n prvků je A;!-krát větší než počet kombinací z těchto prvků a je roven g ) • 1 • 2 • 3 • . . . • k = n(n - l)(n - 2 ) . . . (n - k + 1). Tento výsledek Bernoulliho přivedl k pravidlu pro stanovení po­ čtu variací k-té třídy z n prvků. Regel für die Bestimmung der Anzahl aller Variation ohne Wiederholung zu einer bestimmten Classe: Man bilde eine fallende arithmetische Reihe mit der Differenz 1, deren Anfangsglied gleich der Anzahl der Dinge ist und welche so viele Glieder hat, als die Classenzahl Einheiten; das Product dieser Glieder liefrt die gesuchte Anzahl1. Studenti středních škol znají dnes toto pravidlo takto: Pravidlo 3.1.1 roven

Počet všech /c-členných variací z n prvků je

V(k, n) = n(n - l)(n - 2 ) . . . (n - k + 1). Pravidlo Bernoulli demonstruje na příkladu: Příklad: Určete počet všech čtveřic, které můžeme vytvořit z deseti prvků. 1 Pravidlo k určení počtu variací bez opakování v určité třídě: Vytvoříme klesající aritmetickou řadu s diferencí 1, jejíž počáteční člen je roven počtu věcí a která má právě tolik členů, jako je jednotka čísla třídy. Součin těchto členů dodá hledaný počet.

50

Řešení: V(4,10) = 10 • 9 • 8 • 7 = 5040. Počet čtveřic je 5040. Z předchozího pravidla Bernoulli odvozuje „důsledky": Důsledek 1: Variace n-té třídy z n prvků jsou permutacemi. Počet permutací je tedy roven n{n - l)(n - 2 ) . . . (n - n + 1) = n(n - l)(n - 2 ) . . . 1 = 1 • 2 • 3 • ... • n, což se zcela shoduje s pravidlem, uvedeném v kapitole 2.1. Důsledek 2: Počet permutací n prvků je roven počtu variací (n — l)-vé třídy z n prvků, neboli

P(n) = V(n,n) =

V(n-l,n).

Důsledek 3: Součet variací prvé a druhé třídy z n prvků je roven druhé mocnině n, neboli V(l, n) + 1/(2, n)=n

+ (n2 -n) = n 2 .

Tak například pomocí číslic 1,2,..., 9 můžeme vytvořit právě 92 = 81 čísel a právě tolik čísel, která neobsahují nulu nebo dvě stejné číslice, je mezi jedničkou a stem. Důsledek 4: Počet variací k-té třídy z n prvků je roven

V(k,n)

P{n-k)'

V závěru kapitoly Bernouli řeší otázku počtu možných va­ riací n prvků. Počet variací k-té třídy z n prvků, kde k na­ bývá postupně všech hodnot 1,2,3,..., n, je roven součtu po­ čtu variací v jednotlivých třídách. Toto číslo snadno obdržíme, povšimneme-li si následující vlastnosti variací. Pro počet variací k-té třídy z n prvků platí 51

V(k,n) = k.[V(k-l,n)

+ Í\.

A tedy u jediného prvku je možná jediná variace, u dvou prvků je počet všech variací roven 2- (1 + 1) = 4, u třech prvků 3- (4+1) = 15, atd. Tímto postupem můžeme vytvořit následující tabulku počet prvků 1 2 3 4 5 6 7 8 9 ... počet variací 1 4 15 64 325 1956 13699 109600 986409 . . . Z tabulky Bernoulli snadno zjišťuje, že počet všech devíticiferných čísel vytvořených z číslic 1,2,..., 9, nesmí-li se žádná z číslic opakovat, je roven 986 409.

4.2

Variace s opakováním

V předchozí kapitole jsme předpokládali, že každý z n prvků se mohl v fc-tici prvků vyskytovat nejvýše jedenkrát. Nyní tento předpoklad změníme tak, jak to bylo učiněno u kombinací a budeme předpokládat, že každý z n prvků se v každé fc-tici může opakovat, tedy v každé A:-tici vybrané z daných n prvků může být každý prvek obsažen až A;-krát. Záleží-li v těchto fc-ticích na pořadí prvků mluvíme, o variacích k-té třídy z n prvků s opakováním. Výčet a počet všech variací s opakováním z prvků a\) a
Z důvodu srozumitelnosti textu jsem pozměnila zadání příkladu, podstata věci je však zachována.

52

Čtveřice obdržíme, jestliže každé trojici ak^aj předsadíme každý prvek a/, počet čtveřic aia^a^ se rovná m 3 • m = ra4, atd. Obdobným postupem bychom dostali výčet variací s opa­ kováním ve vyšších třídách. Z postupu tvorby všech variací můžeme také zjistit, že libo­ volná variace A;-té třídy je m-tou částí počtu variace (k + l)-vé třídy. Tedy počet pětic je roven m4 • m = m5, atd. Obecně po­ čet variací n-té třídy je roven mn. Z čehož Bernoulli odvozuje pravidlo pro stanovení počtu variací s oapkováním A;-té třídy z n prvků. Regel für die Bestimmung der Anzahl aller Variation mit Wiederholung zu einer bestimmten Classe: Die gegebene Anzahl von Dingen erhebe man zur Po­ tenz, deren Exponent gleich der Classenzahl ist, wodurch man die gesuchte Zahl finder. V souladu se středoškolským učivem můžeme toto pravidlo formulovat: Pravidlo 4.2.1. Počet všech /c-členných variací s opakováním z n prvků je

V0{k,ri) =nk. Užití pravidla Bernoulli demonstruje na příkladu: Příklad: Určete počet všech čísel mezi čísly 1000 a 10000, které neobsahují číslici 0. Äesem;K(4,9) = 94 = 6561. Počet daných čísel je 6561. 3

Pravidlo ke stanovení počtu všech variací s opakováním v určité třídě: Daný počet věcí umocníme na mocninu, jejiž exponent je roven číslu třídy, čímž nalezneme hledaný počet

53

Stejně jako v předchozí kapitole řeší Bernoulli na závěr této kapitoly otázku počtu možných variací s opakováním z n prvků. Počet variací k-té třídy z m prvků, kde k nabývá postupně všech hodnot 1,2,..., n, tedy počet všech možných variací z m prvků je podle předchozího pravidla roven geometrické řadě 2

3

n

n

m + m + m + ... + m = J2 ™*> k=i

pro jejíž součet platí &n

(mn — \)m (m-l)

Čímž se Bernoulli dostal k pravidlu pro stanovení počtu mož­ ných variací n prvků s opakováním. Regel für die Bestimmung der Anzahl aller Variation mit Wiederholung zu allen Classe von 1 bis n: Die gesuchte Zahl verhält sich zu der um 1 verminder­ ten n-ten Potenz der Anzahl aller Dinge, wie die Zahl aller Dinge zu der um 1 verkleinerten Zahŕ. Pravidlo 3.2.2. Počet variací s opakováním k-té třídy z m prvků, kde k nabývá postupně hodnot 1, 2, . . . , n je VM/o. K 1 - l)m J2 V0{k,m)^ = — —. (m - 1)

*=i

Téma variace s opakováním Bernoulli završuje příklady: 4

Pravidlo k určení počtu variací s opakováním ve všech třídách od 1 po n: Hledané číslo se chová k n-té mocnině počtu věcí snížené o jedničku, jako počet všech věcí ku tomuto číslu sníženému o jedničku.

54

Příklad: Kolik přirozených čísel menších než 107 lze sestavit z cifer 0,1,2,..., 9, připustíme-li, že se v sestaveném čísle mohou cifry opakovat? Řešení: K nalezení odpovědi na tuto otázku není zapotřebí zvláštních kombinatorských znalostí, nejvyšší šesticiferné přiro­ zené číslo je číslo 999 999 a toto číslo zároveň udává počet všech přirozených čísel menších než 107. Chceme-li využít kombinato­ rické znalosti, pak je počet čísel sestavených z číslic 0,1,2,..., 9 menších než 107 roven *—^—=1 111 HO. Mezi těmito varia­ cemi se objevují čísla, která jsou vícekrát započtena a je tedy třeba „nadbytečné" variace vyloučit. Například počet všech šes­ ticiferných posloupností včetně těch, které mají nulu na začátku je K(6,10)=1 000 000 a počet jen těch šesticiferných posloup­ ností, které mají nulu na začátku je K(5,10) =100 000, a tedy ze všech možných šesticiferných variací jich právě 100 000 musíme vyloučit. Obdobné úvahy musíme provést i pro jedno-, dvou-, . . . , pěticiferné posloupnosti. Tedy počet všech přirozených čísel menších než 107 je

^L=po _ K(6) 10) _ K(Ö510) _ K(4? 10) _ K(3? 10) _ K(2,10) - K ( l , 10) - 1 = 999 999. Příklad: Kolik slov je možné vytvořit ze všech 24 písmen abecedy, považujeme-li za slovo jakoukoliv posloupnost písmen s maximálním počtem 24 písmen? Rešení-ZtU V0{k, 24)= %~_1^ = 1391 • 1030. Počet možných slov je 1391 • 1030.

4.3

Počet variací s omezeným opakováním

Obdobně jako v kapitole 3.5. se Bernoulli i zde zabývá otázkou, kolik existuje variací n prvků a, Ď, c,..., nesmí-li se prvek a ve 55

variacích opakovat více než fc-krát, prvek b více než /-krát, prvek c více než ra-krát, atd., kde k,l,m,... E 7V. Postup hledání všech 4 3 2 variací ilustruje na příkladu a b c , a to následujícím způsobem: Prvek oř nám poskytne právě pět kombinací: 1, a, a 2 , a 3 , a 4 . Spojíme-li každou z těchto pěti kombinací s prvkem b v jeho prvé, druhé a třetí mocnině, obdržíme obdobně jako v kapitole 3.5. následující kombinace: b, ab, a2b, a3b, a4b; b2,ab2,a2b2,a3b2,a4b2; b3,ab\a2b3,a*b3,a4b3. Prvních pět kombinací, které obsahují prvek b v prvé mocnině, připustí postupně 1, 2, 3, 4, 5 permutací, tedy b; ab, ba; aab, aba, baa;... Pětice kombinací obsahující b v druhé mocnině povolí právě 1, 3, 6, 10, 15 permutací (podle řady trojúhelníkových čísel), a to bb;abb,bab,bba;... a pětice kombinací, v nichž se prvek b vyskytuje ve třetí mocnině, poskytne právě 1, 4, 10, 20, 35 permutací tvaru bbb; abbb, babb, bbab, bbba; (podle řady čtyřúhelníkových čísel). Dosud jsme obdrželi variace: i; a,b; aa, bb, ba, bb; aaa, aab, aba, baa, abb, bab, bba, bbb;

Připojíme-li k těmto variacím prvek c v jeho prvé a druhé mocnině, obdržíme nové skupiny prvků. Každá ze skupin prvků obsahující prvek c v jeho prvé mocnině, tzn. c; ac, bc; aac, abc,..., poskytne 1 , 2 , 3 , . . . permutací, nesmí-li být pořadí zbylých prvků zaměněno. Tedy jedinec poskytne jednu permutaci, každá dvo­ jice může permutovat dvěma způsoby, každá trojice třemi způ56

soby, čtveřice čtyřmi způsoby, atd. Každá ze skupin prvků obsahující c v jeho druhé mocnině, tzn. cc; acc, bcc; aacc, abcc, bace, bbec, poskytne 1, 3, 6,10,... per­ mutací podle řady trojúhelníkových čísel, nesmí-li být pořadí zbylých prvků zaměněno. Tedy dvojice poskytne jednu permu­ taci, každá trojice tři permutace, každá čtveřice šest permutací, Snadno tedy pochopíme konstrukci Bernoulliho tabulky slou­ žící k nalezení nejen počtu variací určité třídy, ale i počtu mož­ ných variací prvků. Záhlaví tabulky vyplníme možnými třídami variací, v našem případě čísly 0, 1, 2, ...,9. V prvním řádku vyplníme jedničkami tolik sloupců, dokud nedosáhneme mocniny prvku a, tedy vyplníme pět sloupců. Do druhého řádku vepíšeme právě tolik přirozených čísel, do třetího, respektive čtvrtého řádku odpovídající počet prvků trojúhelní­ kové, respektive čtyřúhelníkové řady čísel. Každý následující řá­ dek posuneme o jeden sloupec doprava. Vyplníme tolik řádků, jako je exponent prvku a, tedy 4 řádky. Členy jednotlivých sloupců sečteme, čímž obdržíme řádek s čísly 1,2,4,8,15,... Tento řádek vynásobíme nejprve řadou při­ rozených čísel. Tím obdržíme řádek s čísly 1, 4, 12, 32, 75, ... a následně řadou trojúhelníkových čísel 1, 6, 24, 81, 225, ... Každý následující řádek opět posuneme o jeden sloupec doprava a vy­ plníme tolik řádků, jako je mocnina prvku 6, včetně řádku s čísly 1,2,4,8,... Sečteme-li nově vypsané členy sloupců, obdržíme řádek s čísly 1, 3, 9, 26, 71, ... Tento řádek zobrazuje počet variací v jednot­ livých třídách a zároveň součet členů tohoto řádku je počtem možných variací prvků a4b3c2. Tedy:

57

|0 1 2 a 1 1 1 1 2 1 4

erb3 l 1 2

aW

4 1 4 1 13 9

3 1 3 3 1 8 12 6 26

4 5 6 7 8 9 1 1 4 5 6 10 15 4 10 20 35 15 25 35 35 32 75 150 245 280 24 80 225 525 980 1 260 71 180 410 805 1 260 1 260

58

Závěr Jedním z cílů této diplomové práce bylo ukázat, jakým způso­ bem Bernoulli zavedl základní kombinatorické pojmy, se kte­ rými se dnešní studenti na střední škole setkávají. Jak z textu vyplývá, Bernoulliho kniha Ars conjectandi, která sehrála tak významnou roli v průběhu formování kombinatoriky, zahrnuje takřka veškeré kombinatorické znalosti současného gymnaziál­ ního maturanta, které by mohly být i Bernoulliho způsobem pro zájemce dále rozvíjeny v nepovinném semináři. Typickým příkladem rozšíření středoškolské látky je otázka počtu všech možných uskupení určitého typu, která zpravidla bývá opomíjena, i když veškeré potřebné informace student ob­ držel. Tato otázka navíc umožňuje studentům rozvinout deduk­ tivní způsob myšlení a propojit nové poznatky s poznatky star­ šími, což ve svém důsledku vede k utvrzení veškerých vědomostí. Na závěr bych zdůraznila, že ačkoliv Bernoulliho kniha Ars conjectandi vznikla v 17. století, způsob zavedení kombinatoric­ kých pojmů zůstává takřka po třech století nejen pro středoškol­ ské studenty stejný.

59

Literatura [1] Bernoulli, J., Wahrscheinlichkeitsrechnung (Ars jectandi), Leipzig, 1899.

con-

[2] Katz, V. J., A History of Mathematics, New York, 1998. [3] Fuchs, E., Kombinatorika a teorie grafů, SPN, Praha, 1986. [4] Mačák, K., Poznámky k formováni kombinatoriky v 16. a 17. století , in Matematika v 16. a 17. století,Dějmy ma­ tematiky, SV.12. (ed. J. Bečvář, E. Fuchs), Prometheus, Praha, 1999. [5] Mačák, K., Počátky počtu pravděpodobnosti, Dějiny mate­ matiky, sv. 9, Prometheus, Praha, 1997. [6] Calda, E., Dupač, V., Matematika pro gymnázia - Kombi­ natorika, pravděpodobnost a statistika, Prometheus, Praha, 1995. [7] Herman, J., Kučera, R., Simša, J., Metody řešení matema­ tických úloh II., MU Brno, 1997. [8] Wilson, R.J., Lloyd E. K., Combinatorics, in Companion encyclopedia of the history and philosophy of the mathema­ tical sciences. Vol. II., London, 1994.

60

Knihovna PřF MU

•i m ii m n m •!

__

3145317362