Kombinatorika M1030 Matematika pro biology 20.9.2022 Počet možných výberu z předem daného souboru Výběry bez opakování (vracení) Výběry s opakováním (s vracením) Příklady Princip inkluze a exkluze_ Přihrádkový princig_ Aplikace_ Počet možných výběrů z předem daného souboru Výběry bez opakování (vracení) Základní soubor - n různých rozlišitelných prvků 1. Variace k-té třídy z n prvků Vybíráme k prvků, přihlížíme k pořadí 71} vin, k) = n(n - l)(n - 2) • • • (n - k + 2) (n - k + 1) =--—- (n — /c)! 2. Permutace n prvků Vybíráme všechny prvky, přihlížíme k pořadí, tj. prvky uspořádáme p(n) = i>(n, n) = n(n — l)(n — 2) • • • 2 • 1 = n! (faktoriál) 3. Kombinace k-té třídy z n prvků Vybíráme /c prvků, k pořadí nepřihlížíme (kombinační číslo) Výběry s opakováním (s vracením) Základní soubor - prvky rozděleny do n druhů, v rámci druhu jsou nerozlišitelné 1. Variace k-té třídy z n prvků s opakováním Prvků každého druhu je alespoň k. Vybíráme k prvků, přihlížíme k pořadí V (n, k) = n ■ n - ■ ■ n = nk 2. Permutace s opakováním v situaci /c2,..., kn) Počet prvků prvního druhu je ki, druhého druhu k2, atd. až n-tého druhu je k 3. Kombinace k-té třídy z n prvků s opakováním Prvků každého druhu je alespoň k. Vybíráme k prvků a k pořadí nepřihlížíme P(k\, &2, • • •, kn) p{k1 + fc2 + • • • + ^n) _ (fci+fc2 + '-- + fcn)! p(k1)p(k2) • • -p(fcn) fci! fe! • • • fen! C(n,fc) = P(k,n- 1) (fc + n- 1)! fc!(n- 1)! /c + n — 1 k k + n — 1 n — 1 Příklady 5/ Příklady Spolek má 58 členů. Kolika způsoby si může vybrat a) tříčlenné vedení? Příklady Spolek má 58 členů. Kolika způsoby si může vybrat a) tříčlenné vedení? , /58\ 58-57-56 c(58, 3) = =-—-= 29 • 19 • 56 = 30 856 V o I 3-2 Příklady Spolek má 58 členů. Kolika způsoby si může vybrat a) tříčlenné vedení? , /58\ 58-57-56 c(58, 3) = =-—-= 29 • 19 • 56 = 30 856 \oJ 3-2 b) předsedu, místopředsedu a tajemníka? Příklady Spolek má 58 členů. Kolika způsoby si může vybrat a) tříčlenné vedení? c(58,3) = (fj = = 29 • 19 ■ 56 = 30 856 b) předsedu, místopředsedu a tajemníka? v(58,3) = 58-57-56 = 185136 Příklady V noclehárně je 50 lůžek. Kolika způsoby je možné na ně umístit 35 nocležníků? Příklady V noclehárně je 50 lůžek. Kolika způsoby je možné na ně umístit 35 nocležníků? • Z pohledu provozovatele ubytovny: c(50,35) = 50 • 49 • 48 • 47 • 46 • 45 • 44 • 43 • 42 • 41 • 40 • 39 • 38 • 37 • 36 _ 15 • 14 • 13 • 12 • 11 • 10 • 9 • 8 • 7 • -6 • 5 • 4 • 3 • 2 ~ = 2,250 829 575 • 10 Příklady V noclehárně je 50 lůžek. Kolika způsoby je možné na ně umístit 35 nocležníků? • Z pohledu provozovatele ubytovny: c(50,35) = 50 • 49 • 48 • 47 • 46 • 45 • 44 • 43 • 42 • 41 • 40 • 39 • 38 • 37 • 36 _ 15 • 14 • 13 • 12 • 11 • 10 • 9 • 8 • 7 • -6 • 5 • 4 • 3 • 2 ~ = 2,250 829 575 • 10 Z hlediska ubytovaných: v(50, 35) = ^ = 2,325 815 505 • 1052 15! Příklady Kolik různých slov je možno vytvořit přeskládáním písmen ve slově lokomotiva? 5/13 Příklady Kolik různých slov je možno vytvořit přeskládáním písmen ve slově lokomotiva? P(l, 3,1,1,1,1,1,1) 10! 1! 3! 1! 1! 1! 1! 1! 1! 604 800 Příklady Kolik různých slov je možno vytvořit přeskládáním písmen ve slově lokomotiva? P(l, 3,1,1,1,1,1,1) 10! 1! 3! 1! 1! 1! 1! 1! 1! 604 800 Tak, aby nebyla žádná dvě stejná písmena vedle sebe? Příklady Kolik různých slov je možno vytvořit přeskládáním písmen ve slově lokomotiva? 10' P(l, 3,1,1,1,1,1,1) = = 604800 v ' ' ' ' ' ' ' J 13 111111 • Tak, aby nebyla žádná dvě stejná písmena vedle sebe? Počet seřazení písmen a, i, k, l, m, t, v: p(7) Tři písmena o lze umístit na 8 pozic, tj. vybíráme 3 pozice z 8: c(8, 3) Celkem: p(7)c(8, 3) = 7! (f) = 7! = 7 • 6 • 5 • 4 • 8 • 7 • 6 = 282 240 \oj 5! 3! Příklady Kolik různých slov je možno vytvořit přeskládáním písmen ve slově lokomotiva? 10' P(l, 3,1,1,1,1,1,1) = = 604800 v ' ' ' ' ' ' ' J 13 111111 • Tak, aby nebyla žádná dvě stejná písmena vedle sebe? Počet seřazení písmen a, i, k, l, m, t, v: p(7) Tři písmena o lze umístit na 8 pozic, tj. vybíráme 3 pozice z 8: c(8, 3) Celkem: p(7)c(8, 3) = 7! (f) = 7! = 7 • 6 • 5 • 4 • 8 • 7 • 6 = 282 240 \oJ 5! 3! • Tak, aby se pravidelně střídaly souhlásky a samohlásky? Příklady Kolik různých slov je možno vytvořit přeskládáním písmen ve slově lokomotiva? 10' P(l, 3,1,1,1,1,1,1) = = 604800 v ' ' ' ' ' ' ' J 13 111111 • Tak, aby nebyla žádná dvě stejná písmena vedle sebe? Počet seřazení písmen A, i, k, l, m, t, v: p(7) Tři písmena o lze umístit na 8 pozic, tj. vybíráme 3 pozice z 8: c(8, 3) Celkem: p(7)c(8, 3) = 7! (f) = 7! = 7 • 6 • 5 • 4 • 8 • 7 • 6 = 282 240 \oJ 5! 3! • Tak, aby se pravidelně střídaly souhlásky a samohlásky? Souhlásky: k, l, m, t, v, samohlásky: A, i, o, o, o 51 Í51)2 2 • p(5) • P(l, 1, 3) = 2 • 5! • - = ^- = 4 800 Příklady Kolika způsoby lze mezi čtyři děti rozdělit 50 kuliček? Příklady Kolika způsoby lze mezi čtyři děti rozdělit 50 kuliček? «™> = jm-*^=23426 =c<4-50> Příklady Kolika způsoby lze mezi čtyři děti rozdělit 50 kuliček? P(37 50) = = 53 ' 52 ' 51 = 23 426 = C(4, 50) v ' y 3! 50! 3-2 v ' J • Tak, aby každé dostalo aspoň 5 kuliček? Příklady Kolika způsoby lze mezi čtyři děti rozdělit 50 kuliček? «™> = jm-*^=23426 =c<4-50> • Tak, aby každé dostalo aspoň 5 kuliček? Každém dítěti přidělíme 5 kuliček a rozdělujeme pouze zbývající: x 33! 33-32-31 P(50 - 4 - 5, 3) = P(30, 3) = — = =11-16-31 Příklady V trafice je 25 druhů pohlednic, všechny v dostatečném množství. Třem přátelům pošleme po dvou různých pohlednicích. Kolika způsoby to lze udělat? Příklady V trafice je 25 druhů pohlednic, všechny v dostatečném množství. Třem přátelům pošleme po dvou různých pohlednicích. Kolika způsoby to lze udělat? Dvojici různých pohlednic lze vybrat c(25,2) způsoby. Příklady V trafice je 25 druhů pohlednic, všechny v dostatečném množství. Třem přátelům pošleme po dvou různých pohlednicích. Kolika způsoby to lze udělat? Dvojici různých pohlednic lze vybrat c(25,2) způsoby. Libovolnou dvojici pohlednic lze poslat libovolné osobě, tj. f (c(25,2),3) způsoby. Příklady V trafice je 25 druhů pohlednic, všechny v dostatečném množství. Třem přátelům pošleme po dvou různých pohlednicích. Kolika způsoby to lze udělat? Dvojici různých pohlednic lze vybrat c(25,2)= (^J =^^ = 300 způsoby. Libovolnou dvojici pohlednic lze poslat libovolné osobě, tj. V(c(25,2),3) = c(25,2)3 = 3003 = 27000 000 způsoby. Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? sudé cifry: 0, 2, 4, 6, 8 liché cifry: 1, 3, 5, 7, 9 Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? sudé cifry: 0, 2, 4, 6, 8 liché cifry: 1, 3, 5, 7, 9 Číslo začínající sudou cifrou nemůže mít na prvním místě 0. Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? sudé cifry: 0, 2, 4, 6, 8 liché cifry: 1, 3, 5, 7, 9 Číslo začínající sudou cifrou nemůže mít na prvním místě 0. Počet čísel, začínajících sudou cifrou: 51 P(2, 3)-4-5-5-5-5-5 = P(2, 3) • 4 • 55 = 4 • 55^ 2! 3! Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? sudé cifry: 0, 2, 4, 6, 8 liché cifry: 1, 3, 5, 7, 9 Číslo začínající sudou cifrou nemůže mít na prvním místě 0. Počet čísel, začínajících sudou cifrou: 51 P(2, 3)-4-5-5-5-5-5 = P(2, 3) • 4 • 55 = 4 • 55^ 2! 3! Počet čísel, začínajících lichou cifrou: P(2, 3)-5-5-5-5-5-5 = P(2, 3) • 56 = 56^ 2! 3! Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? sudé cifry: 0, 2, 4, 6, 8 liché cifry: 1, 3, 5, 7, 9 Číslo začínající sudou cifrou nemůže mít na prvním místě 0. Počet čísel, začínajících sudou cifrou: 51 P(2, 3)-4-5-5-5-5-5 = P(2, 3) • 4 • 55 = 4 • 55^ 2! 3! Počet čísel, začínajících lichou cifrou: P(2, 3)-5-5-5-5-5-5 = P(2, 3) • 56 = 56^ 2! 3! Celkem: 4 • 55—— + 5b 2! 3! 2! 3! 5/13 Příklady Kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu se vyskytují tři liché a tři sudé cifry? sudé cifry: 0, 2, 4, 6, 8 liché cifry: 1, 3, 5, 7, 9 Číslo začínající sudou cifrou nemůže mít na prvním místě 0. Počet čísel, začínajících sudou cifrou: 51 P(2, 3)-4-5-5-5-5-5 = P(2, 3) • 4 • 55 = 4 • 55^ 2! 3! Počet čísel, začínajících lichou cifrou: P(2, 3)-5-5-5-5-5-5 = P(2, 3) • 56 = 56^ 2! 3! Celkem: 4 . 55 J- + 56-^- = (4 + 5)55 J- = 9 . 55 • ^ = 2 ■ 32 • 56 = 281250 2! 3! 2\3\ ' 2! 3! 2 Příklady V pytlíku je 10 různých kuliček, dítěti se do hrsti vejde nejvýše 5 kuliček. Kolik existuje takových hrstí? Příklady V pytlíku je 10 různých kuliček, dítěti se do hrsti vejde nejvýše 5 kuliček. Kolik existuje takových hrstí? Počet hrstí, obsahujících i kuliček: c(10,i) = Příklady V pytlíku je 10 různých kuliček, dítěti se do hrsti vejde nejvýše 5 kuliček. Kolik existuje takových hrstí? Počet hrstí, obsahujících i kuliček: c(10,i) = Celkem: = 1 + 10 + 45 + 120 + 210 + 252 = 638 Příklady Modifikace: V pytlíku je 10 různých kuliček, staršímu dítěti se do hrsti vejde všech 10 kuliček. Kolik existuje možných hrstí? Příklady Modifikace: V pytlíku je 10 různých kuliček, staršímu dítěti se do hrsti vejde všech 10 kuliček. Kolik existuje možných hrstí? = 1024 Příklady Modifikace: V pytlíku je 10 různých kuliček, staršímu dítěti se do hrsti vejde všech 10 kuliček. Kolik existuje možných hrstí? = 1024 Jiná úvaha: Konkrétní hrsto«««o«oo«o zakódujeme 0111010010 Příklady Modifikace: V pytlíku je 10 různých kuliček, staršímu dítěti se do hrsti vejde všech 10 kuliček. Kolik existuje možných hrstí? ž(ľ)=- Jiná úvaha: Konkrétní hrsto«««o«oo«o zakódujeme 0111010010 Počet hrstí: V(2,10) = 210 = 1 024 Příklady Modifikace: V pytlíku je 10 různých kuliček, staršímu dítěti se do hrsti vejde všech 10 kuliček. Kolik existuje možných hrstí? = 1024 Jiná úvaha: Konkrétní hrsto«««o«oo«o zakódujeme 0111010010 Počet hrstí: V(2,10) = 210 = 1 024 Závěr: 5/13 Příklady Zobecnění: Kolik existuje podmnožin n prvkové množiny? Příklady Zobecnění: Kolik existuje podmnožin n prvkové množiny ± (ľ) = *• Příklady Zobecnění: Kolik existuje podmnožin n prvkové množiny n ' n E =2" = (1 + D n i=0 Počet možných výberu z předem daného souboru Princip inkluze a exkluze Dvě vlastnosti Tři vlastnosti Při h rá d kový princip Aplikace_ Princip inkluze a exkluze Dvě vlastnosti Množina - souhrn nějakých prvků, značení A,B,... Vlastnost - to, co mají všechny prvky společné, značení A, B. 7/13 Dvě vlastnosti Množina - souhrn nějakých prvků, značení A,B,... Vlastnost - to, co mají všechny prvky společné, značení A,B,... A\ - počet prvků množiny A, počet objektů s vlastností A A U B - sjednocení množin A a B, objekty mající vlastnost A nebo B A n B - průnik množin A a B, objekty mající obě vlastnosti A a B Dvě vlastnosti Množina - souhrn nějakých prvků, značení A,B,... Vlastnost - to, co mají všechny prvky společné, značení A,B,... A\ - počet prvků množiny A, počet objektů s vlastností A A U B - sjednocení množin A a B, objekty mající vlastnost A nebo B A n B - průnik množin A a B, objekty mající obě vlastnosti A a B AU B A + B - AnB Dvě vlastnosti AuB A + B - AnB Příklad: Rybáři lovili v rybníku, v němž žijí kapři a cejni. Každý z nich něco ulovil. Kapra si odnášelo 8 rybářů, cejna 5 rybářů a oba druhy měli 3 rybáři. Kolik je rybářů? 7/13 Dvě vlastnosti AuB A + B - AnB Příklad: Rybáři lovili v rybníku, v němž žijí kapři a cejni. Každý z nich něco ulovil. Kapra si odnášelo 8 rybářů, cejna 5 rybářů a oba druhy měli 3 rybáři. Kolik je rybářů? K =8, C =5, KnC =3 7/13 Dvě vlastnosti AuB A + B - AnB Příklad: Rybáři lovili v rybníku, v němž žijí kapři a cejni. Každý z nich něco ulovil. Kapra si odnášelo 8 rybářů, cejna 5 rybářů a oba druhy měli 3 rybáři. Kolik je rybářů? K =8, C =5, KnC =3 KUC = K + C - KnC = 8 + 5- 3 = 10 7/13 8/13 8/13 Tři vlastnosti AuBuC A + B + c - AnB - Anc - Bnc + AnBnC Příklad: Kolika způsoby je možno na šachovnici umístit dvě figury, nikoliv na jedno pole, tak, aby byly současně v jedné řadě, nebo v jednom sloupci, nebo na poli stejné barvy? Tři vlastnosti AuBuC = A + B + C - AnB - AnC - BnC + AnBnC Příklad: Kolika způsoby je možno na šachovnici umístit dvě figury, nikoliv na jedno pole, tak, aby byly současně v jedné řadě, nebo v jednom sloupci, nebo na poli stejné barvy? |Ä| = 8 • c(8,2) = 8^=8-^ = 224, S =224 /x , 32\ 32-31 B\ = 2 • c(32, 2) = 2 ( 2 ) = 2 • = 992 Tři vlastnosti AuBuC = A + B + C - AnB - AnC - BnC + AnBnC Příklad: Kolika způsoby je možno na šachovnici umístit dvě figury, nikoliv na jedno pole, tak, aby byly současně v jedné řadě, nebo v jednom sloupci, nebo na poli stejné barvy? |P|=8.c(8,2) = 8(f) =8-^ = 224, S =224 /x , 32\ 32-31 B\=2- c(32, 2) = 2 ( 2 ) = 2 • = 992 4 • 3 RnS\ = 0, |ižn£| = 8-2-c(4, 2) = 8-2--= 96, \SnB\ = 96, \RnSnB\ = o Tři vlastnosti AuBuC = A + B + C - AnB - AnC - BnC + AnBnC Příklad: Kolika způsoby je možno na šachovnici umístit dvě figury, nikoliv na jedno pole, tak, aby byly současně v jedné řadě, nebo v jednom sloupci, nebo na poli stejné barvy? |Ä| = 8 • c(8,2) = 8^=8-^ = 224, S =224 /x , 32\ 32-31 B\ = 2 • c(32, 2) = 2 ( 2 ) = 2 • = 992 4 • 3 RnS\ = 0, ližn^l = 8-2-c(4, 2) = 8-2--= 96, \SnB\ = 96, \RnSnB\ = o RUSUB = 224 + 224 + 992 - 0 - 96 - 96 + 0 = 1 248 Počet možných výberu z předem daného souboru Princip inkluze a exkluze_ Přihrádkový princip Aplikace Přihrádkový princip Příklad: Existují mezi obyvateli Brna dvě osoby, které mají přesně stejný počet vlasů? 10 / Příklad: Existují mezi obyvateli Brna dvě osoby, které mají přesně stejný počet vlasů? Počet obyvatel Brna: 369 299 Maximální možný počet vlasů na jedné hlavě: 150 000 10 / 13 Příklad: Existují mezi obyvateli Brna dvě osoby, které mají přesně stejný počet vlasů? Počet obyvatel Brna: 369 299 Maximální možný počet vlasů na jedné hlavě: 150 000 Nejvýše existuje 150 001 hlav s různým počtem vlasů 10 / 13 Příklad: Existují mezi obyvateli Brna dvě osoby, které mají přesně stejný počet vlasů Počet obyvatel Brna: 369 299 Maximální možný počet vlasů na jedné hlavě: 150 000 Nejvýše existuje 150 001 hlav s různým počtem vlasů Matematika zaručuje existenci nějakého objektu, přitom neexistuje efektivní postup, jak ho najít. Příklad: Existují mezi obyvateli Brna dvě osoby, které mají přesně stejný počet vlasů? Počet obyvatel Brna: 369 299 Maximální možný počet vlasů na jedné hlavě: 150 000 Nejvýše existuje 150 001 hlav s různým počtem vlasů Matematika zaručuje existenci nějakého objektu, přitom neexistuje efektivní postup, jak ho najít. Princip: Nechť k, n jsou přirozená čísla, k > n. Při jakémkoliv rozdělení k předmětů do n přihrádek existuje přihrádka, v níž jsou alespoň dva předměty. Počet možných výberu z předem daného souboru Princip inkluze a exkluze_ Přihrádkový princip_ Aplikace Počet prokaryotických chromozomů Počet fylogenetických stromu Aplikace Počet prokaryotických chromozomů Počet genů: n Počet prokaryotických chromozomů Počet genů: n Gen má směr Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet možných uspořádání n genů: n Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet možných uspořádání n genů: Počet možností „nasměrování" genu: Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet možných uspořádání n genů: n! Počet možností „nasměrování" genu: 2n 1 Spojení řetězce genů do uzavřené křivky (nepoznáme, který gen je „první"): — n Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet možných uspořádání n genů: n! Počet možností „nasměrování" genu: 2n Spojení řetězce genů do uzavřené křivky (nepoznáme, který gen je „první"): Nezáleží na orientaci celé uzavřené křivky: 1 n 1 2 Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet možných uspořádání n genů: n! Počet možností „nasměrování" genu: 2n Spojení řetězce genů do uzavřené křivky (nepoznáme, který gen je „první"): Nezáleží na orientaci celé uzavřené křivky: Celkem 2nn! 2n = 2n-1(n-l)! 1 n 1 2 Počet prokaryotických chromozomů Počet genů: n Gen má směr Prokaryotický chromozom tvoří uzavřenou křivku Počet možných uspořádání n genů: Počet možností „nasměrování" genu: Spojení řetězce genů do uzavřené křivky (nepoznáme, který gen je „první"): Nezáleží na orientaci celé uzavřené křivky: n! 1 n 1 2 Celkem 2nn! 2n = 2n-1(n-l)l Pro n = 4 000 je výsledný počet 3,013417 773 • 10 13 873 12 / 13 Počet fylogenetických strom taxonů Počet fylogenetických strom n taxonů Stromy s kořenem Počet fylogenetických stromů n taxonů Stromy s kořenem n A & V/ \ y n^/ Počet fylogenetických stromů n taxonů Stromy s kořenem n A & V/ \ y n^/ xn - počet stromů, i>n - počet větví ^n=^n-l+2, Xn = Xn_i(>n_i + 1), X2 = 1 Počet fylogenetických stromů n taxonů Stromy s kořenem xn - počet stromů, vn - počet větví vn = vn-i+2, xn = xn-i(vn-i + 1), x2 = 1, v2 = 2 vn = 2 + (n - 2) • 2 = 2n - 2, xn = xn_i(2n - 3) Počet fylogenetických stromů n taxonů Stromy s kořenem xn - počet stromů, vn - počet větví vn = vn-1+2, xn=xn-1(vn-1 + ľ), #2 = 1, v2 = 2 v. n = 2 + (n - 2) • 2 = 2n - 2, xn = xn_i(2n - 3) x2 ^3 X4 1 3-1 5-3-1 n (2n-3)(2n-5)---3-l (2n-3)! (2n-4)(2n-6)---2 (2n-3)! (2n-3)! (2(n - 2)) (2(n - 3)) • • • (2(n - (n - 1))) ~ 2™-2(n-2)! 13 / 13 Počet fylogenetických strom n taxonů Stromy bez kořene Počet fylogenetických stromů n taxonů Stromy bez kořene n Počet fylogenetických stromů n taxonů Stromy bez kořene n A - B A. . ti Y C A O c A e. yn - počet stromu, wn - počet větví a ~~j wn=wn_i+2, yn = Vn-\Wn-\, 2/2 = l: Počet fylogenetických stromů n taxonů Stromy bez kořene yn - počet stromů, wn - počet větví wn = wn-i + 2, yn=yn~iwn-i, 2/2 = 1, w2 = 1 wn = 1 + (n - 2) • 2 = 2n - 3, yn = ž/n_i(2rc - 5) Počet fylogenetických stromů n taxonů Stromy bez kořene yn - počet stromů, wn - počet větví wn=wn-1+2, yn = yn-iwn-i, 2/2 = 1, w2 = 1 w n 1 + (n - 2) • 2 = 2n - 3, 2/n = yn_i(2n - 5) 2/2 = 1 2/3 = 1 2/4 = 3-1 2/5=5-3-1 to 7^ q i (2n-5)! (2n-5)! nn = (2n - 5)(2n - 7) • • • 3 • 1 =---s- = —---— V A J (2n-6)(2n-8)---2 2™~3(n-3)! 13 / 13