Na ile sposobów można rozdzielić 5 kwiatków wśród 3 (różnych) panien jeśli każda panna może dostać dowolną liczbę kwiatków (włącznie z zerem) oraz kwiatki są jednakowe.
Mam odpowiedź i jest napisane, że jest to kombinacja z powtórzeniami (analogicznie do zadań, które robiłem wcześniej).
Natomiast rozpisane jest tak:
\(\displaystyle{ {n+k-1\choose n}= {5+3-1 \choose 5}= {7 \choose 5} = \frac{n!}{k!(n-k)!} = \frac{7!}{5! \cdot 2!} = 21}\) i odpowiedź się zgadza.
Wzór jaki znam na kombinacje z powtórzeniami wygląda następująco:
\(\displaystyle{ {n+k-1 \choose k}= \frac{\left( n+k-1\right)! }{k!\left( n-1!\right) }}\) i z tego nie wychodzi.
Czy mógłby ktoś powiedzieć, dlaczego w ten sposób i skąd wzór \(\displaystyle{ {n+k-1\choose n}}\)
Na ile sposobów, komentarz
-
Jajecznica
- Użytkownik
- Posty: 89
- Rejestracja: 30 wrz 2010, o 11:31
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 30 razy
- Pomógł: 1 raz
-
janusz47
- Użytkownik
- Posty: 7918
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Na ile sposobów, komentarz
Pierwszy sposób (szkolny)
\(\displaystyle{ (p_{1}, p_{2}, p_{3})}\) - układ trzech panien
Z reguły mnożenia
\(\displaystyle{ (5, 0,0) \rightarrow 3\cdot 1= 3}\) sposoby
\(\displaystyle{ (4, 1, 0) \rightarrow 3\cdot 2 = 6}\) sposobów
\(\displaystyle{ (3,2, 0) \rightarrow 3\cdot 2 = 6}\) sposobów
\(\displaystyle{ (3, 1, 1)\rightarrow 3\cdot 1 = 3}\) sposoby
\(\displaystyle{ (2, 2 , 1)\rightarrow 3\cdot 1 = 3}\) sposoby
Razem : \(\displaystyle{ 21}\) sposobów.
Drugi sposób (kombinacje z powtórzeniami)
Niech \(\displaystyle{ k_{i}}\) oznacza ilość kwiatków, które otrzymała \(\displaystyle{ i}\) - ta panna, \(\displaystyle{ i =1,2,...,n.}\)
\(\displaystyle{ k_{1}+k_{2}+...+k_{n} = k}\) (1)
Szukamy \(\displaystyle{ f(n, k)}\)- liczbę wszystkich nieujemnych i całkowitych rozwiązań równania (1).
W tym celu uwzględniamy funkcję tworzącą
\(\displaystyle{ g(x)= (1+ x + x^2+...)(1+x+x^2+...)...(1+x+x^2+...)}\)
Szukamy współczynnika przy \(\displaystyle{ x^{k},\ \ wsp_{g(x)}(x^{k})= f(n, k)}\) w rozwinięciu funkcji \(\displaystyle{ g}\).
Ze wzoru na sumę nieskończonego szeregu geometrycznego
\(\displaystyle{ g(x) = \frac{1}{(1- x)^{n}}}\) (2)
Rozwijając (2) w szereg Taylora- Maclaurina, otrzymujemy
\(\displaystyle{ g(x)= (1-x)^{-n} = \sum_{k=0}^{\infty}\frac{[-n]_{k}}{k!}(-x)^{k}}\) (3)
gdzie
\(\displaystyle{ [-n]_{k} = (-n)(-n-1)...(-n-k+1)= (-1)^{k}n(n+1)...(n+k-1)}\) (4)
Na podstawie (3), (4)
\(\displaystyle{ g(x) = \sum_{k=0}^{n}\frac{(n+k - 1)!}{(n-1)!k!}x^{k}}\)
Stąd
\(\displaystyle{ f(n, k) = \frac{(n+k -1)!}{(n-1)!k!} = {n+k-1\choose k}}\)
Dla \(\displaystyle{ n=3, \ \ k = 5, \ \ f(3,5) = {3+5-1\choose 5}= {7\choose 5}= 21.}\)
Sposób 3
Twierdzenie
Istnieje dokładnie \(\displaystyle{ {n+k-1\choose k}}\) funkcji niemalejących \(\displaystyle{ f:\left\{ 1,2,...,k \right\}\rightarrow \left\{1,2,..,n \right\}.}\)
Dowód patrz na przykład W. Lipski, W. Marek Analiza kombinatoryczna,str. 39-40. PWN Warszawa 1986.
\(\displaystyle{ (p_{1}, p_{2}, p_{3})}\) - układ trzech panien
Z reguły mnożenia
\(\displaystyle{ (5, 0,0) \rightarrow 3\cdot 1= 3}\) sposoby
\(\displaystyle{ (4, 1, 0) \rightarrow 3\cdot 2 = 6}\) sposobów
\(\displaystyle{ (3,2, 0) \rightarrow 3\cdot 2 = 6}\) sposobów
\(\displaystyle{ (3, 1, 1)\rightarrow 3\cdot 1 = 3}\) sposoby
\(\displaystyle{ (2, 2 , 1)\rightarrow 3\cdot 1 = 3}\) sposoby
Razem : \(\displaystyle{ 21}\) sposobów.
Drugi sposób (kombinacje z powtórzeniami)
Niech \(\displaystyle{ k_{i}}\) oznacza ilość kwiatków, które otrzymała \(\displaystyle{ i}\) - ta panna, \(\displaystyle{ i =1,2,...,n.}\)
\(\displaystyle{ k_{1}+k_{2}+...+k_{n} = k}\) (1)
Szukamy \(\displaystyle{ f(n, k)}\)- liczbę wszystkich nieujemnych i całkowitych rozwiązań równania (1).
W tym celu uwzględniamy funkcję tworzącą
\(\displaystyle{ g(x)= (1+ x + x^2+...)(1+x+x^2+...)...(1+x+x^2+...)}\)
Szukamy współczynnika przy \(\displaystyle{ x^{k},\ \ wsp_{g(x)}(x^{k})= f(n, k)}\) w rozwinięciu funkcji \(\displaystyle{ g}\).
Ze wzoru na sumę nieskończonego szeregu geometrycznego
\(\displaystyle{ g(x) = \frac{1}{(1- x)^{n}}}\) (2)
Rozwijając (2) w szereg Taylora- Maclaurina, otrzymujemy
\(\displaystyle{ g(x)= (1-x)^{-n} = \sum_{k=0}^{\infty}\frac{[-n]_{k}}{k!}(-x)^{k}}\) (3)
gdzie
\(\displaystyle{ [-n]_{k} = (-n)(-n-1)...(-n-k+1)= (-1)^{k}n(n+1)...(n+k-1)}\) (4)
Na podstawie (3), (4)
\(\displaystyle{ g(x) = \sum_{k=0}^{n}\frac{(n+k - 1)!}{(n-1)!k!}x^{k}}\)
Stąd
\(\displaystyle{ f(n, k) = \frac{(n+k -1)!}{(n-1)!k!} = {n+k-1\choose k}}\)
Dla \(\displaystyle{ n=3, \ \ k = 5, \ \ f(3,5) = {3+5-1\choose 5}= {7\choose 5}= 21.}\)
Sposób 3
Twierdzenie
Istnieje dokładnie \(\displaystyle{ {n+k-1\choose k}}\) funkcji niemalejących \(\displaystyle{ f:\left\{ 1,2,...,k \right\}\rightarrow \left\{1,2,..,n \right\}.}\)
Dowód patrz na przykład W. Lipski, W. Marek Analiza kombinatoryczna,str. 39-40. PWN Warszawa 1986.
Ostatnio zmieniony 27 sie 2017, o 12:42 przez janusz47, łącznie zmieniany 1 raz.
-
a4karo
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Na ile sposobów, komentarz
W każdym wzorze symbole coś oznaczają. Przeczytaj czym we wzorze jest \(\displaystyle{ n}\) i czym jest \(\displaystyle{ k}\) i zastosuj wzór odpowiednio.
-
janusz47
- Użytkownik
- Posty: 7918
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Na ile sposobów, komentarz
Sposób czwarty
Znajdujemy rozwiązanie równania
\(\displaystyle{ k+ l+ m = 5 , \ \ k,l, m \in N \cup \left\{ 0\right\}}\) (1)
na przykład w programie Mathematica.
Zastępujemy sumę (1) sumą
\(\displaystyle{ S(x) =\sum_{k,l,m\in N \cup \{0\}} x^{k+l+m} =\sum_{k\in N \cup \{0\}}x^{k}\cdot\sum_{l\in N \cup \{0\}}x^{l}\cdot\sum_{m\in N \cup \{0\}}x^{m} = \frac{1}{1-x}\cdot \frac{1}{1-x}\cdot \frac{1}{1-x} = \frac{1}{1- x)^3}.}\)
Czynniki w powyższym iloczynie to szeregi geometryczne zbieżne jednostajnie w kole \(\displaystyle{ x<1,}\) a więc \(\displaystyle{ S(x)}\) jako iloczyn Cauchy'ego jest zbieżny jednostajnie dla \(\displaystyle{ |x|<1.}\)
Zauważmy, że wyraz stopnia piątego to
\(\displaystyle{ \sum_{k,l,m \in N \cup \{0\}} x^{k+l+m}= ... a_{5}x^5,}\) gdzie \(\displaystyle{ a_{5}}\) jest liczbą wszystkich trójek \(\displaystyle{ (k,l,m)}\) spełniających (1), a więc interesujących nas wielkością.
Mathematica 9
\(\displaystyle{ f[x_{-}] =: 1/(1 -x)^3}\)
\(\displaystyle{ s = Series[f[x], \{x,0,5\}]}\)
\(\displaystyle{ SeriesCoefficient[s, 5]}\)
\(\displaystyle{ 1 +3x +6x^2 +10x^3 +15x^4 +21x^5 + o[x]^6}\)
\(\displaystyle{ 21}\)
Znajdujemy rozwiązanie równania
\(\displaystyle{ k+ l+ m = 5 , \ \ k,l, m \in N \cup \left\{ 0\right\}}\) (1)
na przykład w programie Mathematica.
Zastępujemy sumę (1) sumą
\(\displaystyle{ S(x) =\sum_{k,l,m\in N \cup \{0\}} x^{k+l+m} =\sum_{k\in N \cup \{0\}}x^{k}\cdot\sum_{l\in N \cup \{0\}}x^{l}\cdot\sum_{m\in N \cup \{0\}}x^{m} = \frac{1}{1-x}\cdot \frac{1}{1-x}\cdot \frac{1}{1-x} = \frac{1}{1- x)^3}.}\)
Czynniki w powyższym iloczynie to szeregi geometryczne zbieżne jednostajnie w kole \(\displaystyle{ x<1,}\) a więc \(\displaystyle{ S(x)}\) jako iloczyn Cauchy'ego jest zbieżny jednostajnie dla \(\displaystyle{ |x|<1.}\)
Zauważmy, że wyraz stopnia piątego to
\(\displaystyle{ \sum_{k,l,m \in N \cup \{0\}} x^{k+l+m}= ... a_{5}x^5,}\) gdzie \(\displaystyle{ a_{5}}\) jest liczbą wszystkich trójek \(\displaystyle{ (k,l,m)}\) spełniających (1), a więc interesujących nas wielkością.
Mathematica 9
\(\displaystyle{ f[x_{-}] =: 1/(1 -x)^3}\)
\(\displaystyle{ s = Series[f[x], \{x,0,5\}]}\)
\(\displaystyle{ SeriesCoefficient[s, 5]}\)
\(\displaystyle{ 1 +3x +6x^2 +10x^3 +15x^4 +21x^5 + o[x]^6}\)
\(\displaystyle{ 21}\)