Treść zadania: Na ile sposobów można ułożyć n książek, na k półkach? Oczywiście kolejność książek na półkach jest istotna.
Wiem ,że odpowiedź ma być następująca: \(\displaystyle{ {n+(k-1) \choose (k-1)} \cdot n!}\)
Lecz ja bym po prostu dał: \(\displaystyle{ {n \choose k} \cdot n!}\)
Będę wdzięczny jak ktoś wytłumaczy mi dlaczego ma być taka odp.Pozdrawiam
Układanie n książek na k półkach
Układanie n książek na k półkach
No ok. Rozpisałem sobie i wyszły mi 24 możliwości podstawiając do wzoru również tak wychodzi. Ale równie dobrze mogę na kilka naście innych sposobów zapisać ten wzór ,a żeby wyszło również dobrze. Powinienem zrobić parę kolejnych przykładów żeby sprawdzić czy będzie to dalej działać, ale czy wpadnę na to że to właśnie ma być tak a nie inaczej. Wątpię bo po zrobieniu pierwszego przykładu nic jasno jeszcze przynajmniej dla mnie nie widać. A przede wszystkim tej zależności. Teraz znam ten wzór to mogę sobie podstawić i wiem , że jest dobrze. Ale jak trafie jakieś inne zadanie o podobnym sposobie rozwiązania ,ale innym wzorze końcowym to pytanie czy będę wstanie do niego dojść skoro tutaj tej zależności zupełnie nie widzę choć wiem ,że jest poprawna. Jak do tego podejść, a żeby zrozumieć?
-
pyzol
- Użytkownik
- Posty: 4346
- Rejestracja: 26 kwie 2010, o 11:39
- Płeć: Mężczyzna
- Lokalizacja: Nowa Ruda
- Podziękował: 5 razy
- Pomógł: 929 razy
Układanie n książek na k półkach
No to spróbuję się podjąć. Zacznijmy od łatwiejsze modelu. Załóżmy że na każdej półce jest przynajmniej jedna książka. Załóżmy też, że książki nie są rozróżnialne.
Niech \(\displaystyle{ x_i}\) oznacza ilość książek na i-tej półce. Natomiast na wszystkich półkach jest \(\displaystyle{ n}\) - książek.
Można więc zapisać równanie:
\(\displaystyle{ x_1+x_2+\ldots+x_k=n,x_i \ge 1*}\)
Teraz jak to rozwiązać. Układamy n książek w szeregu robiąc pomiędzy nimi przerwy:
\(\displaystyle{ k_1 \sim,k_2 \sim k_3 \sim k_4 \sim ...\sim k_{n-1} \sim k_{n}\\}\)
Mamy \(\displaystyle{ n-1}\) przerw, w te przerwy możemy dawać przegródki, tak żeby otrzymać schemat rozmieszczenia książek na półkach.
Zauważmy, że tych przegródek będzie \(\displaystyle{ k-1}\). Dla przykładu może \(\displaystyle{ n=5,k=3}\), oto przykładowe rozmieszenie:
\(\displaystyle{ k_1|k_2\sim k_3|k_4\sim k_5}\)
\(\displaystyle{ \sim}\) oznacza przerwę, \(\displaystyle{ |}\) oznacza przerwę, w którą daliśmy przegrodę.
Jak widać na pierwszej półce będzie jedna książka na drugiej i na trzeciej dwie. Widać też, że przegród było \(\displaystyle{ 2=3-1}\) a przerw, w które mogliśmy dać te przegrody \(\displaystyle{ 4=5-1}\)
Ogólnie wybieramy więc \(\displaystyle{ k-1}\) z \(\displaystyle{ n-1}\) przerw, w które włożymy przegrody.
Możliwości jest więc: \(\displaystyle{ {n-1\choose k-1}}\). Jeśli książki są rozróżnialne to dla każdej możliwości dochodzi \(\displaystyle{ n!}\) permutacji.
Twoje zadanie jest nieco trudniejsze, bo półki mogą być puste i tu wykorzystuje się równanie.
Tym razem jest to:
\(\displaystyle{ y_1+y_2+\ldots+y_k=n,y_i \ge 0}\).
Chcemy doprowadzi do równania \(\displaystyle{ *}\),(tzn, chcemy, żeby każda zmienna była dodatnia) wtedy będziemy mogli skorzystać ze schematu już znanego. W tym celu do każdej zmiennej \(\displaystyle{ y_i}\) dodamy \(\displaystyle{ 1}\), w sumie dodamy \(\displaystyle{ k}\) jedynek z lewej strony równania, więc z prawej trzeba dodać \(\displaystyle{ k}\).
\(\displaystyle{ (y_1+1)+(y_2+1)\ldots+(y_k+1)=n+k,y \ge 0}\)
Teraz podstawmy:
\(\displaystyle{ x_i=y_i+1\\
x_1+\ldots+x_k=n+k,x_i \ge 1}\).
I stąd oto bierze się ten wzór. To tyle, teraz co ty musisz umieć, ty musisz umieć rozpoznać taki model, a raczej odróżnić go od kombinacji bez powtórzeń. Nie jest to łatwe, jak cała kombinatoryka...
Niech \(\displaystyle{ x_i}\) oznacza ilość książek na i-tej półce. Natomiast na wszystkich półkach jest \(\displaystyle{ n}\) - książek.
Można więc zapisać równanie:
\(\displaystyle{ x_1+x_2+\ldots+x_k=n,x_i \ge 1*}\)
Teraz jak to rozwiązać. Układamy n książek w szeregu robiąc pomiędzy nimi przerwy:
\(\displaystyle{ k_1 \sim,k_2 \sim k_3 \sim k_4 \sim ...\sim k_{n-1} \sim k_{n}\\}\)
Mamy \(\displaystyle{ n-1}\) przerw, w te przerwy możemy dawać przegródki, tak żeby otrzymać schemat rozmieszczenia książek na półkach.
Zauważmy, że tych przegródek będzie \(\displaystyle{ k-1}\). Dla przykładu może \(\displaystyle{ n=5,k=3}\), oto przykładowe rozmieszenie:
\(\displaystyle{ k_1|k_2\sim k_3|k_4\sim k_5}\)
\(\displaystyle{ \sim}\) oznacza przerwę, \(\displaystyle{ |}\) oznacza przerwę, w którą daliśmy przegrodę.
Jak widać na pierwszej półce będzie jedna książka na drugiej i na trzeciej dwie. Widać też, że przegród było \(\displaystyle{ 2=3-1}\) a przerw, w które mogliśmy dać te przegrody \(\displaystyle{ 4=5-1}\)
Ogólnie wybieramy więc \(\displaystyle{ k-1}\) z \(\displaystyle{ n-1}\) przerw, w które włożymy przegrody.
Możliwości jest więc: \(\displaystyle{ {n-1\choose k-1}}\). Jeśli książki są rozróżnialne to dla każdej możliwości dochodzi \(\displaystyle{ n!}\) permutacji.
Twoje zadanie jest nieco trudniejsze, bo półki mogą być puste i tu wykorzystuje się równanie.
Tym razem jest to:
\(\displaystyle{ y_1+y_2+\ldots+y_k=n,y_i \ge 0}\).
Chcemy doprowadzi do równania \(\displaystyle{ *}\),(tzn, chcemy, żeby każda zmienna była dodatnia) wtedy będziemy mogli skorzystać ze schematu już znanego. W tym celu do każdej zmiennej \(\displaystyle{ y_i}\) dodamy \(\displaystyle{ 1}\), w sumie dodamy \(\displaystyle{ k}\) jedynek z lewej strony równania, więc z prawej trzeba dodać \(\displaystyle{ k}\).
\(\displaystyle{ (y_1+1)+(y_2+1)\ldots+(y_k+1)=n+k,y \ge 0}\)
Teraz podstawmy:
\(\displaystyle{ x_i=y_i+1\\
x_1+\ldots+x_k=n+k,x_i \ge 1}\).
I stąd oto bierze się ten wzór. To tyle, teraz co ty musisz umieć, ty musisz umieć rozpoznać taki model, a raczej odróżnić go od kombinacji bez powtórzeń. Nie jest to łatwe, jak cała kombinatoryka...