funkcja tworząca

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
parchimus
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

funkcja tworząca

Post autor: parchimus » 16 cze 2020, o 13:47

Wyznaczyć funkcję tworzącą liczby rozmieszczeń kul w 4 szufladkach. Takich, że w 1 i 2 jest nieparzysta liczba kul a w 3 i 4 conajwyżej 3. Wyznaczyć liczbę takich rozmieszczeń dla 7 kul.

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2985
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 73 razy
Pomógł: 996 razy

Re: funkcja tworząca

Post autor: Janusz Tracz » 16 cze 2020, o 14:08

Pytanie sprowadza się do wyznaczenia liczby rozwiązań układu warunków:

\(\displaystyle{ \begin{cases} x_1+x_2+x_3+x_4=n\\ x_1,x_2\in \left\{ 1,3,5,...,\ell\right\} \\ x_3,x_4\in \left\{ 0,1,2,3\right\} \end{cases} }\)

gdzie \(\displaystyle{ n}\) to liczba wszystkich rozmieszczanych kul znajdujących się w szufladach w liczbie \(\displaystyle{ x_i}\), a \(\displaystyle{ \ell}\) to największa liczba nieparzysta nie większa niż \(\displaystyle{ n}\). Ogólnie współczynnik przy \(\displaystyle{ x^n}\) funkcji tworzącej mówi o liczbie tych rozwiązań a samą funkcją tworzącą jest wielomian

\(\displaystyle{ \mathcal{G}(x)= \left( x^1+x^3+x^5+...+x^{\ell}\right)^2\left( x^0+x^1+x^2+x^3\right)^2 }\)

zatem zgodnie ze standardowym oznaczeniem szukamy \(\displaystyle{ \left[ x^n\right]\mathcal{G} }\) przy \(\displaystyle{ n=7}\) (i rzecz jasna \(\displaystyle{ \ell=7}\) wynikającym z takiego wyboru \(\displaystyle{ n}\)). Z pomocą Wolfaram można te wielomiany wymnożyć i odczytać, że wynik to \(\displaystyle{ 16}\) klik

ODPOWIEDZ