Czy są jakieś sposoby i tricki przydatne przy wyznaczaniu postaci współczynnika przy x^k (lub odpowiednio innych dla funkcji tworzących wielu zmiennych) w enumeratorze?
Dla przykładu, w zadaniu:
Na ile sposobów można zamówić dwanaście porcji lodów spośród pięciu rodzajów, jeśli nie wolno wziąć więcej niż czterech porcji jednego rodzaju?
Funkcja tworząca to \(\displaystyle{ (\sum_{k=0}^{4} x^{k})^{5}}\), a szukaną odpowiedzą jest współczynnik przy x^12. Jest sposobem policzenie tego ręcznie, ale odpowiedź podana do zadania, czyli \(\displaystyle{ {16 \choose 12} - 5 {11 \choose 7} + {5 \choose 2} {6 \choose 2}}\) nie została raczej otrzymana w ten sposób. Jak to policzyć?
Enumeratory - postać współczynnika przy x^k
-
gardner
Enumeratory - postać współczynnika przy x^k
Na pewno tak to wygląda? Z tego co pamiętam to stosowałem funkcje tworzące ale wtedy gdy nie było podanego ograniczenia ( tu \(\displaystyle{ 4}\)). Na pewno wyjdzie metodą - na ile sposobów możesz rozmieścić
\(\displaystyle{ 12}\) porcji lodów w pięciu ich rodzajach. Znasz tą metodę?-- 12 lip 2015, o 14:50 --Skorzystaj z tego
\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=12}\)
gdzie \(\displaystyle{ x_{i} \le 4}\) Po prostu od wyniku będziesz musiał odjąć te opcje,gdzie do jednego "pudełka i " trafiło więcej niż \(\displaystyle{ 4}\) porcje
\(\displaystyle{ 12}\) porcji lodów w pięciu ich rodzajach. Znasz tą metodę?-- 12 lip 2015, o 14:50 --Skorzystaj z tego
\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=12}\)
gdzie \(\displaystyle{ x_{i} \le 4}\) Po prostu od wyniku będziesz musiał odjąć te opcje,gdzie do jednego "pudełka i " trafiło więcej niż \(\displaystyle{ 4}\) porcje
-
MatXXX
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
Enumeratory - postać współczynnika przy x^k
Ok, byłem w tym miejscu, ale nie potrafiłem znaleźć prostego sposobu na odrzucenie niepoprawnych rozwiązań równania i sobie odpuściłem, ale teraz widzę, że rozwiązanie z jednym iksem większym od 4, to jak rozwiązanie analogiczego równania, tyle, że z prawą stroną pomniejszoną o 5. A potem włączanie-wyłączanie. Dzięki.
A co do sposobu funkcji tworzących z ograniczeniem: Mamy pięć nawiasów, każdy reprezentuje jeden rozdaj lodów. W każdym nawiasie jest \(\displaystyle{ x^{0}+x^{1}+x^{2}+x^{3}+x^{4}}\), gdzie potęga przy \(\displaystyle{ x}\) mówi, ile wybranych zostało lodów tego rodzaju (od 0 do 4). Po wymnożeniu tego i odczytaniu współczynnika przy \(\displaystyle{ x^{r}}\) odstajemy ilość możliwości wyboru \(\displaystyle{ r}\) lodów z zadanymi ograniczeniami. Dlaczego to działa? Weźmy pięć nawiasów takich jak wyżej, tyle, że w każdym niech będzie inna niewiadoma i interpretujmy je tak samo jak wcześniej, czyli jako ilość wystąpień w naszej kombinacji. Po wymnożeniu dostaniemy wielomian będący sumą jednomianów postaci \(\displaystyle{ x^{a} y^{b} z^{c} w^{d} t^{e}}\), każdy z nich reprezentuje jedną możliwą kombinację. Rozwiązaniem byłoby zliczenie jednomianów, dla których \(\displaystyle{ a+b+c+d+e=r}\), czyli rozwiązanie podanego przez Ciebie równania z ograniczeniami. Zamiana wszystkich zmiennych na jedną powoduję, że współczynnikiem przy \(\displaystyle{ x^{r}}\) jest liczba takich jednomianów, więc jest ona odpowiedzią.
A co do sposobu funkcji tworzących z ograniczeniem: Mamy pięć nawiasów, każdy reprezentuje jeden rozdaj lodów. W każdym nawiasie jest \(\displaystyle{ x^{0}+x^{1}+x^{2}+x^{3}+x^{4}}\), gdzie potęga przy \(\displaystyle{ x}\) mówi, ile wybranych zostało lodów tego rodzaju (od 0 do 4). Po wymnożeniu tego i odczytaniu współczynnika przy \(\displaystyle{ x^{r}}\) odstajemy ilość możliwości wyboru \(\displaystyle{ r}\) lodów z zadanymi ograniczeniami. Dlaczego to działa? Weźmy pięć nawiasów takich jak wyżej, tyle, że w każdym niech będzie inna niewiadoma i interpretujmy je tak samo jak wcześniej, czyli jako ilość wystąpień w naszej kombinacji. Po wymnożeniu dostaniemy wielomian będący sumą jednomianów postaci \(\displaystyle{ x^{a} y^{b} z^{c} w^{d} t^{e}}\), każdy z nich reprezentuje jedną możliwą kombinację. Rozwiązaniem byłoby zliczenie jednomianów, dla których \(\displaystyle{ a+b+c+d+e=r}\), czyli rozwiązanie podanego przez Ciebie równania z ograniczeniami. Zamiana wszystkich zmiennych na jedną powoduję, że współczynnikiem przy \(\displaystyle{ x^{r}}\) jest liczba takich jednomianów, więc jest ona odpowiedzią.