funkcja tworząca
-
parchimus
- Użytkownik
- Posty: 43
- Rejestracja: 28 maja 2020, o 18:02
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 6 razy
funkcja tworząca
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.
-
Janusz Tracz
- Użytkownik
- Posty: 4068
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: funkcja tworząca
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}\)
\(\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}\)