Strona 1 z 1

funkcja tworząca

: 16 cze 2020, o 13:47
autor: parchimus
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.

Re: funkcja tworząca

: 16 cze 2020, o 14:08
autor: Janusz Tracz
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