Witam.
Znaleźć funkcję tworzącą dla liczby wyborów \(\displaystyle{ r \ (r = 0, 1, \ldots , 9)}\) kul spośród trzech kul zielonych, trzech białych i trzech niebieskich.
Jeśli dobrze się orientuję, to mam znaleźć taką funkcję postaci \(\displaystyle{ (1+x+x^2+ \ldots )^n}\), że współczynnik przy \(\displaystyle{ x^r}\) ma być szukaną liczbą wyborów \(\displaystyle{ r}\) kul.
Nie wiem jednak, jak zacząć.
Z góry dziękuję.
Funkcja tworząca, wybory kolorowych kul
-
abc666
Funkcja tworząca, wybory kolorowych kul
Robi się to tak. Kul zielonych może być \(\displaystyle{ 0,1,2}\) lub \(\displaystyle{ 3}\) więc do funkcji wnoszą one
\(\displaystyle{ (1+x+x^2+x^3)}\)
Podobnie jest dla pozostałych. To co wnoszą poszczególne składniki się mnoży więc
\(\displaystyle{ f(x)=(1+x+x^2+x^3)^3}\)
Jeśli np. kul zielonych miała być parzysta ilość to wnosiły by one do funkcji
\(\displaystyle{ (1+x^2)}\)
itp. itd.
\(\displaystyle{ (1+x+x^2+x^3)}\)
Podobnie jest dla pozostałych. To co wnoszą poszczególne składniki się mnoży więc
\(\displaystyle{ f(x)=(1+x+x^2+x^3)^3}\)
Jeśli np. kul zielonych miała być parzysta ilość to wnosiły by one do funkcji
\(\displaystyle{ (1+x^2)}\)
itp. itd.
-
patry93
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
Funkcja tworząca, wybory kolorowych kul
Hmm, rozjaśniłeś mi nieco, dzięki (wcześniej wydawało mi się, że taką funkcję produkuje się "od razu" i nie wiadomo jak i skąd ).
Niestety wszystkiego nie rozumiem, a dokładniej:
Niestety wszystkiego nie rozumiem, a dokładniej:
Wyczuwam tutaj prawo mnożenia, ale w przypadku np. zliczania sposobów, gdy jeden etap przebiega przed drugim, mnożenie jest "naturalne", lecz tutaj mnożymy całe funkcje, a to dość istotnie zmienia współczynniki po wymnożeniu i nie widzę, dlaczego miałoby to być prawdą...To co wnoszą poszczególne składniki się mnoży
-
abc666
Funkcja tworząca, wybory kolorowych kul
No to wynika np. z tego że \(\displaystyle{ x^{a+b}=x^ax^b}\)
Mamy
\(\displaystyle{ x^r}\) co oznacza, że \(\displaystyle{ r}\) jest ilość kul jaką wybraliśmy. Czyli
\(\displaystyle{ r=n+b+z}\) (liczba kul niebieskich, białych i zielonych)
\(\displaystyle{ x^{n+b+z}=x^n\cdot x^b\cdot x^z}\).
Wsp. przy \(\displaystyle{ x^r}\) jest więc liczbą sposobów wybrania \(\displaystyle{ n,b}\) i \(\displaystyle{ z}\) tak żeby sumowały się do \(\displaystyle{ r}\).
A co do następowania po sobie to żadna kolejność wybierania czy coś na nie interesuje, tylko efekt końcowy.
Np. rozważmy jeszcze taki przykład. Wyznaczmy liczbę rozwiązań równania
\(\displaystyle{ x_1+x_2+x_3+x_4=k}\)
Przy czym
\(\displaystyle{ x_1,x_2\in\left\{ 0,1\right\}\\
x_3\in\left\{ 1,2,3 \right\} \\
x_4 \in \mathbb{N}_0}\)
Skoro \(\displaystyle{ x^d}\) oznacza, że \(\displaystyle{ x_1=d}\) to od x_1 dostaniemy czynnik
\(\displaystyle{ (1+x)}\)
Tak samo dla \(\displaystyle{ x_2}\)
Od \(\displaystyle{ x_3}\) mamy \(\displaystyle{ (x+x^2+x^3)}\)
A \(\displaystyle{ x_4}\) wnosi
\(\displaystyle{ (1+x+x^2+...)}\)
Czyli funkcja tworząca to
\(\displaystyle{ (1+x)^2(x+x^2+x^3)(1+x+x^2+...)}\)
i wsp. \(\displaystyle{ x^k}\) oznacza liczbę rozwiązań dla danego k.
No i dlaczego to działa. Z każdego nawiasu coś wybieramy (być może jedynkę). Więc po zsumowaniu wykładników dostajemy ilość wybranych po drodze przedmiotów. A liczba rozwiązań równania to liczba wyborów takich sposobów.
Co do jakiegoś formalnego dowodu tego. Należało by pewnie rozważyć splot funkcji tworzących czy coś podobnego.
Mamy
\(\displaystyle{ x^r}\) co oznacza, że \(\displaystyle{ r}\) jest ilość kul jaką wybraliśmy. Czyli
\(\displaystyle{ r=n+b+z}\) (liczba kul niebieskich, białych i zielonych)
\(\displaystyle{ x^{n+b+z}=x^n\cdot x^b\cdot x^z}\).
Wsp. przy \(\displaystyle{ x^r}\) jest więc liczbą sposobów wybrania \(\displaystyle{ n,b}\) i \(\displaystyle{ z}\) tak żeby sumowały się do \(\displaystyle{ r}\).
A co do następowania po sobie to żadna kolejność wybierania czy coś na nie interesuje, tylko efekt końcowy.
Np. rozważmy jeszcze taki przykład. Wyznaczmy liczbę rozwiązań równania
\(\displaystyle{ x_1+x_2+x_3+x_4=k}\)
Przy czym
\(\displaystyle{ x_1,x_2\in\left\{ 0,1\right\}\\
x_3\in\left\{ 1,2,3 \right\} \\
x_4 \in \mathbb{N}_0}\)
Skoro \(\displaystyle{ x^d}\) oznacza, że \(\displaystyle{ x_1=d}\) to od x_1 dostaniemy czynnik
\(\displaystyle{ (1+x)}\)
Tak samo dla \(\displaystyle{ x_2}\)
Od \(\displaystyle{ x_3}\) mamy \(\displaystyle{ (x+x^2+x^3)}\)
A \(\displaystyle{ x_4}\) wnosi
\(\displaystyle{ (1+x+x^2+...)}\)
Czyli funkcja tworząca to
\(\displaystyle{ (1+x)^2(x+x^2+x^3)(1+x+x^2+...)}\)
i wsp. \(\displaystyle{ x^k}\) oznacza liczbę rozwiązań dla danego k.
No i dlaczego to działa. Z każdego nawiasu coś wybieramy (być może jedynkę). Więc po zsumowaniu wykładników dostajemy ilość wybranych po drodze przedmiotów. A liczba rozwiązań równania to liczba wyborów takich sposobów.
Co do jakiegoś formalnego dowodu tego. Należało by pewnie rozważyć splot funkcji tworzących czy coś podobnego.