Wyznacz liczbę rozwiązań całkowitych równania \(\displaystyle{ x_{1} + x_{2} + x_{3} + x_{4} = 19}\) spełniających zależności \(\displaystyle{ 0 \le x_{i } \le 8}\), dla \(\displaystyle{ i \in \left\{ 1,2,3,4\right\}}\)
Czyli mam włożyć np 19 cukierków do 4 pudełek, tak, żeby w żadnym nie było więcej niż 8. Myślałem nad tym, żeby włożyć do 1 pudełka najpierw 8, potem 7 i tak dalej (i całość przemnożyć przez 4 przypadki). resztę rozdzielić między pozostałe 3, z tym że tutaj też nie można włożyć więcej niż 8 do jednego. Nie mam pomysłu jak to rozwiązać.
Liczba całkowitych rozwiązań równania
-
Zahion
- Moderator
- Posty: 2095
- Rejestracja: 9 gru 2012, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa, mazowieckie
- Podziękował: 139 razy
- Pomógł: 504 razy
Liczba całkowitych rozwiązań równania
Generalnie zbiór rozwiązań równania \(\displaystyle{ y_{1} + ... + y_{k} = n}\) w liczbach nieujemnych ma \(\displaystyle{ {n+k-1 \choose k-1}}\) elementów.
Wezmy przykładowo dowód dla \(\displaystyle{ k = 4}\).
Ustawmy sobie trzy czarne kwadraciki, z lewej strony \(\displaystyle{ y_{1}}\) białych kwadracików, pomiędzy pierwszym a drugim \(\displaystyle{ y_{2}}\), między drugim a trzecim \(\displaystyle{ y_{3}}\) a po prawej stronie trzeciego \(\displaystyle{ y_{4}}\). Oczywiście w ten sposób powstaje nam kod dowolnego rozwiązania \(\displaystyle{ \left( y_{1},...,y_{4}\right)}\) naszego równania. Naszym zadaniem jest wyznaczyć liczbę takich ciągów.
Wezmy przykładowo dowód dla \(\displaystyle{ k = 4}\).
Ustawmy sobie trzy czarne kwadraciki, z lewej strony \(\displaystyle{ y_{1}}\) białych kwadracików, pomiędzy pierwszym a drugim \(\displaystyle{ y_{2}}\), między drugim a trzecim \(\displaystyle{ y_{3}}\) a po prawej stronie trzeciego \(\displaystyle{ y_{4}}\). Oczywiście w ten sposób powstaje nam kod dowolnego rozwiązania \(\displaystyle{ \left( y_{1},...,y_{4}\right)}\) naszego równania. Naszym zadaniem jest wyznaczyć liczbę takich ciągów.