szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 sie 2017, o 13:28 
Użytkownik

Posty: 89
Lokalizacja: Polska
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:

{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:

{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 {n+k-1\choose n}
Góra
Mężczyzna Offline
PostNapisane: 27 sie 2017, o 12:26 
Użytkownik

Posty: 3456
Pierwszy sposób (szkolny)

(p_{1}, p_{2}, p_{3}) - układ trzech panien

Z reguły mnożenia

(5, 0,0) \rightarrow 3\cdot 1= 3 sposoby

(4, 1, 0) \rightarrow 3\cdot 2 = 6 sposobów

(3,2, 0) \rightarrow 3\cdot 2 = 6 sposobów

(3, 1, 1)\rightarrow 3\cdot 1 = 3 sposoby

(2, 2 , 1)\rightarrow 3\cdot 1 = 3 sposoby

Razem : 21 sposobów.

Drugi sposób (kombinacje z powtórzeniami)

Niech k_{i} oznacza ilość kwiatków, które otrzymała i - ta panna, i =1,2,...,n.

k_{1}+k_{2}+...+k_{n} = k (1)

Szukamy f(n, k)- liczbę wszystkich nieujemnych i całkowitych rozwiązań równania (1).

W tym celu uwzględniamy funkcję tworzącą

g(x)= (1+ x + x^2+...)(1+x+x^2+...)...(1+x+x^2+...)

Szukamy współczynnika przy x^{k},\ \  wsp_{g(x)}(x^{k})= f(n, k) w rozwinięciu funkcji g.

Ze wzoru na sumę nieskończonego szeregu geometrycznego

g(x) = \frac{1}{(1- x)^{n}} (2)

Rozwijając (2) w szereg Taylora- Maclaurina, otrzymujemy

g(x)= (1-x)^{-n} = \sum_{k=0}^{\infty}\frac{[-n]_{k}}{k!}(-x)^{k} (3)

gdzie

[-n]_{k} = (-n)(-n-1)...(-n-k+1)= (-1)^{k}n(n+1)...(n+k-1) (4)

Na podstawie (3), (4)

g(x) = \sum_{k=0}^{n}\frac{(n+k - 1)!}{(n-1)!k!}x^{k}

Stąd

f(n, k) = \frac{(n+k -1)!}{(n-1)!k!} = {n+k-1\choose k}

Dla n=3, \ \ k = 5, \ \ f(3,5) = {3+5-1\choose 5}= {7\choose 5}= 21.

Sposób 3

Twierdzenie

Istnieje dokładnie {n+k-1\choose k} funkcji niemalejących 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.
Góra
Mężczyzna Offline
PostNapisane: 27 sie 2017, o 12:34 
Użytkownik

Posty: 15237
Lokalizacja: Bydgoszcz
W każdym wzorze symbole coś oznaczają. Przeczytaj czym we wzorze jest n i czym jest k i zastosuj wzór odpowiednio.
Góra
Mężczyzna Offline
PostNapisane: 27 sie 2017, o 15:07 
Użytkownik

Posty: 3456
Sposób czwarty

Znajdujemy rozwiązanie równania

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ą

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 x<1, a więc S(x) jako iloczyn Cauchy'ego jest zbieżny jednostajnie dla |x|<1.

Zauważmy, że wyraz stopnia piątego to

\sum_{k,l,m \in N \cup \{0\}} x^{k+l+m}= ... a_{5}x^5, gdzie a_{5} jest liczbą wszystkich trójek (k,l,m) spełniających (1), a więc interesujących nas wielkością.

Mathematica 9

f[x_{-}] =: 1/(1 -x)^3

s = Series[f[x], \{x,0,5\}]

SeriesCoefficient[s, 5]

1 +3x +6x^2 +10x^3 +15x^4 +21x^5 + o[x]^6

21
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 na ile sposobów może ustawić się...  irracjonalistka  1
 Liczba sposobów - zadanie 2  gutek927  4
 Na ile sposobów można przydzielić...  MrMarion  1
 Na ile sposobów można umieścić?  Anonymous  2
 na ile sposobow ...  jessica2007  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl