Liczba rozwiązań.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
choko
Użytkownik
Użytkownik
Posty: 281
Rejestracja: 2 wrz 2009, o 21:10
Płeć: Mężczyzna
Podziękował: 9 razy
Pomógł: 2 razy

Liczba rozwiązań.

Post autor: choko »

Wyznaczyć ilość różnych rozwiązań równania \(\displaystyle{ x_1+x_2+x_3+x_4=30}\) w zbiorze liczb całkowitych, a ile w naturalnych.

Proszę o pomoc i wyjaśnienie, z góry dziękuję.
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Liczba rozwiązań.

Post autor: JakimPL »

Przyjmijmy, że:

\(\displaystyle{ x_1 + x_2 = 30}\)

Na mocy tego \(\displaystyle{ x_3=-x_4}\). W zbiorze liczb całkowitych istnieje nieskończenie par liczb przeciwnych do siebie.

Natomiast w zbiorze liczb naturalnych (niech \(\displaystyle{ 0 \in \mathbb{N}}\)) nie możemy operować liczbami ujemnymi, zatem:

\(\displaystyle{ x_1, x_2,x_3,x_4 \ge 0}\)

Problem pomocniczy: ile jest rozwiązań w zbiorze liczb naturalnych \(\displaystyle{ a+b=c}\), a ile \(\displaystyle{ a+b+c=d}\)?

Co do pierwszego, to innych możliwości niż \(\displaystyle{ a}\) oraz \(\displaystyle{ c-a}\) nie ma, co daje nam równe \(\displaystyle{ c+1}\) (ilość elementów \(\displaystyle{ \left\lbrace 0,1,2,\ldots,c\right\rbrace}\)) par rozwiązań.

Drugi problem łatwiej zobrazować, pokazując metodykę działania. Niech \(\displaystyle{ a=0}\), stąd:

\(\displaystyle{ b=i \Rightarrow c=d-i}\), gdzie \(\displaystyle{ i \in \left\lbrace 0,1,2,\ldots,d\right\rbrace}\)

Dla \(\displaystyle{ a=0}\) wychodzi \(\displaystyle{ d=1}\) rozwiązań. Zwiększmy \(\displaystyle{ a}\) o \(\displaystyle{ 1}\) - na mocy tego \(\displaystyle{ b+c=d-1}\). Tym razem:

\(\displaystyle{ b=i\Rightarrow c=d-i-1}\), gdzie \(\displaystyle{ i \in \left\lbrace 0,1,2,\ldots,d-1\right\rbrace}\)

Sumując, daje nam to \(\displaystyle{ d}\) rozwiązań. Myślę, że ułożeniem formuły, która doda wszystkie możliwe rozwiązania \(\displaystyle{ a+b+c=d}\) nie będzie problemu. Teraz tylko uogólnić na więcej zmiennych, podstawić i wychodzi .
choko
Użytkownik
Użytkownik
Posty: 281
Rejestracja: 2 wrz 2009, o 21:10
Płeć: Mężczyzna
Podziękował: 9 razy
Pomógł: 2 razy

Liczba rozwiązań.

Post autor: choko »

Słuchaj a w rozwiązaniu nie powinno sie pojawić coś takiego: \(\displaystyle{ {n+k-1\choose k}}\)?
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Liczba rozwiązań.

Post autor: JakimPL »

Powinno.

EDIT: Ale nie jest to obligatoryjne .
choko
Użytkownik
Użytkownik
Posty: 281
Rejestracja: 2 wrz 2009, o 21:10
Płeć: Mężczyzna
Podziękował: 9 razy
Pomógł: 2 razy

Liczba rozwiązań.

Post autor: choko »

A mógłbyś napisać jak to idzie tą metodą?
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Liczba rozwiązań.

Post autor: JakimPL »

Dla \(\displaystyle{ 4}\) zmiennych będzie to, zgodnie z tym, co napisałem powyżej:

\(\displaystyle{ a+b+c+d=n}\)

Zaczynamy od \(\displaystyle{ a=0, b=0 \Rightarrow c=i, d = n-i}\)

Liczba rozwiązań dla takich par to oczywiście \(\displaystyle{ n+1}\). Zwiększamy \(\displaystyle{ b}\) o \(\displaystyle{ 1}\), co daje nam \(\displaystyle{ n-1}\) rozwiązań. Powtarzamy kroki aż do \(\displaystyle{ b=n}\). Reasumując, do tej pory uzyskaliśmy:

\(\displaystyle{ \begin{array}{|c|c|c|c|}
\hline
b=0 & b=1 & \ldots & b=n \\ \hline
n+1 & n & \ldots & 1 \\ \hline
\end{tabular}}\)


Sumując:

\(\displaystyle{ \sum_{i=0}^{n} n-i+1 = \frac{1}{2} \left(n+1\right)\left(n+2\right)}\)

Zwiększając teraz \(\displaystyle{ a}\) o \(\displaystyle{ 1}\). Powtórzmy całą metodę opisaną powyżej, dla zobrazowania rozpiszę ją mimo wszystko:

\(\displaystyle{ a=1, b=0 \Rightarrow c=i, d = n-i-1}\)

Dla \(\displaystyle{ b=0}\) mamy \(\displaystyle{ n}\) rozwiązań (o jedno mniej niż poprzednio, ponieważ \(\displaystyle{ a}\) się zwiększyło \(\displaystyle{ 1}\)), \(\displaystyle{ b=1}\) implikuje \(\displaystyle{ n-1}\), natomiast ostatnim krokiem będzie \(\displaystyle{ b=n-1}\), co można zapisać również w tabelce:

\(\displaystyle{ \begin{array}{|c|c|c|c|}
\hline
b=0 & b=1 & \ldots & b=n-1 \\ \hline
n & n-1 & \ldots & 1 \\ \hline
\end{tabular}}\)


Również sumujemy:

\(\displaystyle{ \sum_{i=0}^{n-1} n-i = \frac{1}{2} n\left(n+1\right)}\)

Jak widać, można przewidzieć następne elementy .

Powtarzamy kroki, tym razem dla rosnącego \(\displaystyle{ a}\) - i znów tabelka .

\(\displaystyle{ \begin{array}{|c|c|c|c|c|}
\hline
a=0 & a=1 & \ldots & a=n-1 & a=n \\ \hline
\displaystyle \frac{1}{2} \left(n+1\right)\left(n+2\right) & \displaystyle \frac{1}{2} n\left(n+1\right) & \ldots & \displaystyle \frac{1}{2} \cdot 2 \cdot 3 & 1 \\ \hline
\end{tabular}}\)


No to ostatni krok, sumujemy!

\(\displaystyle{ \sum_{i=0}^{n} \frac{1}{2}\left(i+1\right)\left(i+2\right) = \frac{1}{6}\left(n+1\right)\left(n+2\right)\left(n+3\right)}\)

No tak, ale gdzie symbol Newtona? Zauważmy, że:

\(\displaystyle{ \frac{1}{6}\left(n+1\right)\left(n+2\right)\left(n+3\right)= {n+3 \choose n}}\)

Dlaczego akurat \(\displaystyle{ n+3}\) i \(\displaystyle{ n}\)?

Napisałeś: \(\displaystyle{ {n+k-1\choose k}}\) - \(\displaystyle{ n}\) tutaj to liczba zmiennych, natomiast \(\displaystyle{ k}\) to "nasze" \(\displaystyle{ n}\). I się zgadza.

Pozdrawiam.
choko
Użytkownik
Użytkownik
Posty: 281
Rejestracja: 2 wrz 2009, o 21:10
Płeć: Mężczyzna
Podziękował: 9 razy
Pomógł: 2 razy

Liczba rozwiązań.

Post autor: choko »

Dobrze tylko jak liczysz sumy tych szeregów bo ja biorę wyraz pierwszy + ostani na dwa razy różnica i nie wychodzi to co napisane.
I skąd się bierze że:
JakimPL pisze: No tak, ale gdzie symbol Newtona? Zauważmy, że:

\(\displaystyle{ \frac{1}{6}\left(n+1\right)\left(n+2\right)\left(n+3\right)= {n+3 \choose n}}\)

Dlaczego akurat \(\displaystyle{ n+3}\) i \(\displaystyle{ n}\)?

Napisałeś: \(\displaystyle{ {n+k-1\choose k}}\) - \(\displaystyle{ n}\) tutaj to liczba zmiennych, natomiast \(\displaystyle{ k}\) to "nasze" \(\displaystyle{ n}\). I się zgadza.

Pozdrawiam.
Awatar użytkownika
JakimPL
Użytkownik
Użytkownik
Posty: 2401
Rejestracja: 25 mar 2010, o 12:15
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 43 razy
Pomógł: 459 razy

Liczba rozwiązań.

Post autor: JakimPL »

Rozpisz sobie symbol Newtona po prawej stronie jako iloraz odpowiednich silni oraz poskracaj. Analogiczny proces można przeprowadzić w drugą stronę. Nie jest ten proces konieczny, iloczyn może zostać.

Pierwsze sumy to po prostu ciągi arytmetyczny o różnicy \(\displaystyle{ 1}\). Z tym raczej nie powinno być problemów.

Ostatnia suma może być problematyczna, jednak:

\(\displaystyle{ \sum_{i=0}^{n} \frac{1}{2}\left(i+1\right)\left(i+2\right) =\frac{1}{2} \sum_{i=0}^{n} \left(i+1\right)\left(i+2\right) = 1\cdot 2 + 2\cdot 3 + \ldots n(n+1) + (n+1)(n+2)}\)

Dalsze wyjaśnienie może będzie pomocne, zawiera metodę postępowania:

187819.htm
ODPOWIEDZ