1 Funkcje generujące w kombinatoryceAutor: Kacper Walentynowicz III Liceum Ogólnokształcące w Gdyni Funkcje generujące w kombinatoryce

2 Czym są funkcje generujące?Funkcja generująca G(x) dla ciągu liczb rzeczywistych (lub zespolonych) to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) x postaci: 𝑛=0 ∞ 𝑔 𝑛 𝑥 𝑛 = 𝑔 0 + 𝑔 1 ∗𝑥+ 𝑔 2 ∗ 𝑥 Brzmi nieprzyjemnie, prawda?

3 Inne spojrzenie na te funkcjeMamy 10 kul białych i 5 czarnych. Na ile sposobów możemy wybrać spośród nich dokładnie K kul? Zacznijmy od czegoś prostszego. A co jeśli mamy tylko 10 kul białych? A tylko 5 czarnych? 𝑛=0 10 𝑔 𝑛 𝑥 𝑛 =1+1∗𝑥+1∗ 𝑥 ∗ 𝑥 10 𝑛=0 5 𝑔 𝑛 𝑥 𝑛 =1+1∗𝑥+1∗ 𝑥 ∗ 𝑥 5

4 Z powrotem do pierwotnego problemuMusimy więc pomnożyć obydwa wielomiany Co będzie stało przy współczynniku dla K-tej potęgi? Czyli – wynik! 1+𝑥+ 𝑥 𝑥 10 ∗ 1+𝑥+ 𝑥 𝑥 5 1∗ 𝑥 𝐾 +𝑥∗ 𝑥 𝐾−1 + 𝑥 2 ∗ 𝑥 𝐾− 𝑥 𝐾 ∗1

5 Czas na coś trudniejszegoNa ile sposobów możemy stworzyć ciąg N liter, w którym istnieje parzyście wiele liter A, nieparzyście wiele B oraz dowolna liczba liter C? Stwórzmy funkcję generującą dla samych liter C. Dlaczego w ten sposób? 𝑛=0 ∞ 𝑔 𝑛 𝑥 𝑛 =1+𝑥+ 𝑥 2 2! + 𝑥 3 3! +... 𝑥 𝐾 𝐾! ∗ 𝑥 𝐿 𝐿! = 𝐾+𝐿 ! 𝐾!∗𝐿! ∗ 𝑥 𝐾+𝐿 𝐾+𝐿 !

6 Podążamy dalej Chcemy więc podać wynik współczynnika przy N-tej potędze wyrażenia : FFT? Da się prościej! 1+ 𝑥 2 2! + 𝑥 4 4! 𝑥+ 𝑥 3 3! + 𝑥 5 5! 𝑥+ 𝑥 2 2! + 𝑥 3 3! + 𝑥 4 4!

7 Szereg Taylora Szereg Taylora jest efektywnym narzędziem aproksymacji funkcji dostatecznie dużo razy różniczkowalnych. Jak wygląda więc nasz iloczyn? 𝑒 𝑥 = 𝑛=0 ∞ 𝑥 𝑛 𝑛! 1+ 𝑥 2 2! + 𝑥 4 4! +... = 𝑒 𝑥 + 𝑒 −𝑥 2

8 Rozwijamy nasze wyrażenie𝑥+ 𝑥 3 3! + 𝑥 5 5! +... = 𝑒 𝑥 − 𝑒 −𝑥 2 Wobec tego iloczyn tych funkcji zapisujemy jako: 1+𝑥+ 𝑥 2 2! + 𝑥 3 3! + 𝑥 4 4! = 𝑒 𝑥 1+ 𝑥 2 2! 𝑥+ 𝑥 3 3! 𝑥+ 𝑥 2 2! +... = 𝑒 𝑥 + 𝑒 −𝑥 𝑒 𝑥 − 𝑒 −𝑥 𝑒 𝑥

9 Mnożymy! Co teraz? 𝑒 𝑥 + 𝑒 −𝑥 𝑒 𝑥 − 𝑒 −𝑥 𝑒 𝑥 = 𝑒 𝑥 𝑒 2𝑥 − 𝑒 −2𝑥 4 = 𝑒 3𝑥 − 𝑒 −𝑥 4 𝑒 3𝑛 − 𝑒 −𝑛 4 = 3 𝑛 − −1 𝑛 𝑒 𝑛 = 3 𝑛 − −1 𝑛 𝑥 𝑛 𝑛!

10 Końcowe odliczanie Otrzymaliśmy wynik:„Na ile sposobów możemy stworzyć ciąg N liter, w którym istnieje parzyście wiele liter A, nieparzyście wiele B oraz dowolna liczba liter C?” → znaleźliśmy odpowiedź. Co jeszcze potrafimy dzięki tym funkcjom zrobić? 𝐹 𝑛 = 3 𝑛 − −1 𝑛 4

11 Dziękuję za uwagę.