Kytice
Příklad na vytvarajúcu posloupnost (kombinování s podmínkou)
Při vázání kytek do kytice jsou dány tyto podmínky:
- kytice může obsahovat maximálně 3 lilie
- kytice musí obsahovat alespoň 4 červené růže
- kytice musí obsahovat nepárný (lichý) počet bílých růží
Kolik různých kytic mohu uvázat
a) ze tří kusů kytek b) ze čtyř kusů kytek c) z šesti kytek? b) z jedenácti kytek? c) z n kytek?
Příklad vyřešíme nejdřívě obecně pro n kdytek a pak si za n dosadíme 6 a 11.
1. Vytvoříme si posloupnosti jednotlivých podmínek a k nim vytvárajúce funkce
Posloupnost tvořím tak že se ptám: "Kolik možností mám umístit 0 / 1 / 2 / 3 / 4 / 5 / 7 /... lilí / červených růží / bílých růží do kytice?" Tip: najeď myší na prvek následujících posloupnosti.
Podmínka slovně | Podmínka v posloupnosti | Podmínka ve vytvarajúcí funkci |
---|---|---|
max 3 lilie : | < 1, 1, 1, 1, 0, 0, 0, 0,...> | 1 + 1x1 + 1x2 + 1x3 |
min 4 červené růže : | < 0, 0, 0, 0, 1, 1, 1, 1 ...> | x4/ (1-x) |
nepárný počet bílých růží: (0 je párná) |
<0, 1, 0, 1, 0, 1, 0, 1, ...> | x / (1-x2) |
2. Vynásobíme vytvarajúce funkce
Jelikož vynásobit rovnou posloupnosti neumíme :(, tak to musíme prohnat přes jejich funkce. A proč násobíme? Protože ke každé z možnosti jak umístit do kytice lilie může být libovolná z možností jak tam umístit červené růže, atd.
(1 + x1 + x2 + x3) * x4/ (1-x) * x / (1-x2) = x5(1 + x1 + x2 + x3) / ((1-x)(1-x2)) =
= x5(1 + x1 + x2 + x3) / ((1-x)(1-x)(1+x)) = x5(x2 + 1)(x + 1) / ((1-x)(1-x)(1+x)) =
= x5(x2 + 1) / ((1-x)(1-x)) = x5(x2 + 1) / (1-x)2
Kdybchom z této funkce (který nám zbyl po vykrácení všeho zbytečného) byli schopni dostat zpátky posloupnost, měli bychom vystaráno a nemuseli bychom už nic řešit. Co můžeme funkce zatím vyčíst je, že výsledná posloupnost bude začínat 5ti nulami (protože v čitateli je x5). Zde si zapomatuju že do výsledné posloupnosti vložím na začátek 5 nul a dál budu pracovat s funkcí
(x2 + 1) / (1-x)2
Bohužel už nic víc o posloupnosti z této funkce nevyčteme a nezbývá nám nic jiného než ji převést na součet pěkných zlomků (sčítat posloupnosti není problém narozdíl od násobení), tedy:
3. Rozklad na parciální zlomky
Abychom si úplně nezavařili hlavičky, použijeme wolfram ;)
(x2 + 1) / (1 - x)2 = - 2 / (1 - x) + 2 / (1 + x )2 + 1
-2 / (1-x) <-> <-2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,... >
2 / (1+x)2 <-> <2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24...> = 2 * <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ...>
1 <-> <1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...>
suma <-> <1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22,...>
Zde si vzpomenu na zapomenuté x5, které jsme si odložili v bodě 3 a do výsledné posloupnosti vložím 5nul na začátek.
<0, 0, 0, 0, 0, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22,...>
4. Z posloupnosti přečteme odpovědi
a) Kolik různých kytic uvážu z 3 kusů kytek? Podívám se na 4. prvek posloupnosi a vím že žádnou.
Proč? Protože v podmínkách na začátku bylo že kytice musí mít minimálně 4 červené růže.
a) Kolik různých kytic uvážu z 4 kusů kytek? Podívám se na 5. prvek posloupnosi a vím že žádnou.
Proč? Můžu mít čtyři červené růže (ČČČČ)! Nemůžu, protože v podmínce na začátku jsme si řekli že 0 je párná a kdybychom měli jen 4 červebé růže, pak by to znamenalo že máme 0 bílých růží tedy párný počet bílých růží, což je zakázáno.
b) Kolik různých kytic uvážu z 6ti kusů kytek? Podívám se na 7. prvek posloupnosi a vím že odpověď je 2 kytice.
ČČČČBL, ČČČČLL protože 0 (práný počet Bílých růží), ČČČČČL, ČČČČBB protože 2 (práný počet Bílých růží), ČČČLLB protože málo Červených růží.
c) Kolik různých kytic uvážu z 11ti kusů kytek? Podívám se na 12. prvek posloupnosti (první prvek hovoří o 0ks) a vím že 12 kytic.
d) Kolik různých kytic uvážů z n kusů kytek? 2n kytic pro n>5 , 0 kytic pro n<5, 1 kytici pro n=5