ile jest sposobów rozmieszczenia n kul w n-3 pudełkach

[adamigo10000]

ile jest sposobów rozmieszczenia \(\displaystyle{ n}\) kul w \(\displaystyle{ n-3}\) pudełkach, tak, aby w każdym pudełku była przynajmniej jedna kula, kule i pudełka są między sobą rozróżnialne

[oldj]

Nie mam lepszego pomysłu niż ten oto przydługi : wiemy, że w każdym pudełku ma być jedna kula. Mamy zatem 3 możliwości:
1) w 1 pudełku są 4 kule, a w innych pudełkach po 1 kuli
2) w 1 pudełku są 3 kule, w 1 (innym!) pudełku są 2 kule, a w innych pudełkach po 1 kuli
3) są 3 pudełka z dwoma kulami w każdym, a w innych pudełkach po 1 kuli

1) najpierw wybieramy miejsce, gdzie będą 4 kule ( \(\displaystyle{ n-3}\) możliwości), następnie wybieramy te 4 kule ( \(\displaystyle{ {n \choose 4}}\) sposobów), a potem pozostałe kule rozlokowujemy w pozostałych n-4 miejscach na \(\displaystyle{ (n-4)!}\) możliwości. czyli \(\displaystyle{ (n-3) \cdot {n \choose 4} \cdot (n-4)!= \frac{(n-3) \cdot n!}{4!}}\)

2) najpierw wybieramy te 2 miejsca (\(\displaystyle{ {n-3 \choose 2}}\) sposobów), potem wybieramy 5 kul na \(\displaystyle{ {n \choose 5}}\) sposobów, wsadzamy je do tych 2 urn (3 w jednej, 2 w drugiej) na \(\displaystyle{ {5 \choose 2} \cdot 2}\) możliwości i reszte (\(\displaystyle{ n-5}\) kul) rozlokowujemy w pozostałych miejscach na \(\displaystyle{ (n-5)!}\) sposobów, czyli \(\displaystyle{ {n-3 \choose 2} \cdot {n\choose 5} \cdot {5 \choose 2} \cdot 2 \cdot (n-5)!}\), po uproszczeniu otrzymując \(\displaystyle{ \frac{n! \cdot (n-3)(n-4)}{12}}\)

3) znów - wybieramy 3 miejsca na \(\displaystyle{ {n-3 \choose 3}}\) sposobów, potem 6 kul (\(\displaystyle{ {n \choose 6}\)), wsadzamy po dwie do każdej z tych 3 urn (na \(\displaystyle{ {6 \choose 2} \cdot {4 \choose 2} \cdot 3!}\) sposobów), reszte wsadzamy do pozostałych \(\displaystyle{ n-6}\) urn na \(\displaystyle{ (n-6)!}\) sposobów. Wymnażając dostajemy \(\displaystyle{ \frac{(n-3)(n-4)(n-5) \cdot n!}{8}}\)

ostateczny wynik to suma tych 3 wielkości.

[Gouranga]

a ja bym do tego podszedł inaczej
do 1. pudełka wkładamy jedną z n kul, do drugiego jedną z n-1 itd.
co daje nam \(\displaystyle{ n(n-1)(n-2)\ldots \cdot 4}\) czyli \(\displaystyle{ \frac{n!}{3!}}\) natomiast każdą z pozostałych 3 kul możemy wrzucić do dowolnego pudła co daje nam \(\displaystyle{ (n-3)^3}\) bo teraz w drugą stronę, zamiast przypisywać kulę do pudła przypisujemy pudło do kuli
co ostatecznie daje nam
\(\displaystyle{ \frac{n!}{3!} \cdot (n-3)^3}\)

[mat_61]

Gouranga, to nie jest poprawne rozwiązanie ponieważ w ten sposób takie same rozmieszczenia liczysz wielokrotnie.
Przykładowo przy rozdzielaniu kul do pudełek kulę nr 5 włożysz do pudełka nr 8. Następnie przy przypisaniu pudełka do jednej z czterech pozostałych kul przypiszesz pudełko nr 8 do kuli nr 3.

Ale możesz także przy rozdzielaniu kul do pudełek kulę nr 3 włożyć do pudełka nr 8. Następnie przy przypisaniu pudełka do jednej z czterech pozostałych kul przypiszesz pudełko nr 8 do kuli nr 5.

Zakładając, że w pozostałych pudełkach są takie same kule jak przy pierwszym podziale, to mamy taki sam rozkład wszystkich kul w pudełkach (w pudełku nr 8 są kule nr 3 i 5, bo przecież nie ma znaczenia, że trafiły one tam "w różnej kolejności") choć - stosując proponowany przez Ciebie sposób - został on policzony jako inny.

[Gouranga]

to można by zmodyfikować mój sposób tak, żeby był właściwy?

[adamigo10000]

wielkie dzięki oldj, wszystko jasne, tylko chyba jest jeden błąd, wyrażenie \(\displaystyle{ {6 \choose 2}}\)*\(\displaystyle{ {4 \choose 2}}\)*3! prowadzi do powtarzania się tych samych wyników, bo tym razem mamy do czynienia z pudełkami o takiej samej ilości kul, zatem powinno być \(\displaystyle{ {6 \choose 2}}\)*\(\displaystyle{ {4 \choose 2}}\)

[oldj]

Nie widzę błędu. Gdyby było tylko \(\displaystyle{ {6 \choose 2}*{4 \choose 2}}\), to zauważ co zrobiliśmy - (wcześniej) wybraliśmy 6 kul i poparowaliśmy je, ale nie włożyliśmy ich do żadnego z pudełek. A możemy te pary powkładać różnie - i to istotnie są różne przypadki. Mamy 3 różne pary i 3 różne pudełka - możemy je rozlokować na \(\displaystyle{ 3!}\) sposobów.

[mat_61]

Oldj, adamigo10000 ma rację w swoim spostrzeżeniu.
Jeżeli mamy trzy pary kul to oczywiście jest \(\displaystyle{ 3!}\) możliwości ich rozmieszczenia w pudełkach.

Zauważ jednak ile jest podziałów sześciu kul na te trzy nierozróżnialne pary. Powiedzmy, że najpierw wybierzemy - spośród sześciu - kule nr 3 i 5, następnie nr 1 i 2 i zostaną nam w trzeciej parze kule nr 4 i 6. Możemy jednak wybrać te pary kul np. w takiej kolejności: najpierw nr 1 i 2, następnie nr 4 i 6 i zostaną nam w trzeciej parze kule nr 3 i 5. Widzisz więc, że w obydwu przypadkach podział sześciu kul na trzy pary jest identyczny, choć został wg Twojego pomysłu policzony jako różny.

Jeżeli więc pary kul są nierozróżnialne (tak jak proponujesz), to ilość możliwych podziałów sześciu kul na trzy pary jest równa:

\(\displaystyle{ \frac{ {6 \choose 2} \cdot {4 \choose 2} }{3!}}\)

I teraz te nierozróżnialne pary dzielimy pomiędzy trzy pudełka na \(\displaystyle{ 3!}\) sposobów, co daje nam:

\(\displaystyle{ \frac{ {6 \choose 2} \cdot {4 \choose 2} }{3!} \cdot 3!={6 \choose 2} \cdot {4 \choose 2}}\)

możliwości.

Jeżeli pary kul byłyby rozróżnialne (np. miały przypisane numery pudełek), to wówczas wszystkich możliwości podziału kul na pary przypisane do konkretnych pudełek mamy:

\(\displaystyle{ {6 \choose 2} \cdot {4 \choose 2}}\)

-- 17 wrz 2013, o 23:19 --

Jeżeli ktoś ma ochotę, to więcej o podziale elementów zbioru na rozróżnialne lub nierozróżnialne, równoliczne lub nierównoliczne podzbiory może poczytać np. tutaj: https://www.matematyka.pl/230511.htm#p858509-- 17 wrz 2013, o 23:31 --

to można by zmodyfikować mój sposób tak, żeby był właściwy?

Raczej nie, przynajmniej ja takiego sposobu nie widzę zakładając, że modyfikacja miałaby polegać na "zredukowaniu" otrzymanego wyniku poprzez jakieś dzielniki.

[oldj]

rzeczywiście - nie rozróżniam par. zwracam honor!

[ucwmiu]

A może tak - moim zdaniem ciekawiej
Sprowadźmy zadanie do takiego problemu: Ile rozwiązań w liczbach całkowitych dodatnich ma równanie:

\(\displaystyle{ x_{1} + x_{2} + x_{3} + ... + x_{n-3} = n}\) wówczas każda jedynka przydzielona do konkretnego "iksa" reprezentuje kulkę, a każdy "iks" reprezentuje pudełko.

Teraz tak: mamy sobie \(\displaystyle{ n}\) jedynek zapisanych jedna po drugiej:

\(\displaystyle{ 111111111111111111.....1}\).

Między tymi jedynkami jest (n-1) przerw. W te "przerwy" wtykamy patyki, np:

\(\displaystyle{ 1|1|1|1|...|1111}\) dzieląc w sumie \(\displaystyle{ n}\) jedynek na \(\displaystyle{ n-3}\) grupki. Możemy wybierać miejsca na "patyki" spośród tych miejsc, w które te patyki możemy włożyć. Ilość takich wariantów wynosi:

\(\displaystyle{ {n-1 \choose (n-3)-1} = {n-1 \choose n-4}}\)

Uwaga: długość kombinacji bierze się stąd, że jeżeli dzielimy płaszczyznę prostymi równoległymi na \(\displaystyle{ m}\) części, to w tym celu należy użyć \(\displaystyle{ m-1}\) prostych.

Pozdrawiam

PS Jeżeli Cię interesują głębsze rozważania w tym kierunku, poczytaj o zasadzie szufladkowej.

[mat_61]

...wówczas każda jedynka przydzielona do konkretnego "iksa" reprezentuje kulkę, a każdy "iks" reprezentuje pudełko.

Pozostaje pytanie którą kulkę reprezentuje każda z jedynek?

Niestety nie można tutaj zastosować podanego sposobu (czyli analogii do rozwiązania w liczbach całkowitych dodatnich podanego równania), a powodem jest rozróżnialność kul.

Zauważ, że takie rozwiązanie mówi nam tylko o tym ile kul jest w każdym z kolejnych pudełek, a nic nie mówi o tym które to są kule. Podany sposób jak najbardziej pasuje do rozróżnialnych pudełek i nierozróżnialnych kul.

[ucwmiu]

A, ok - nie wczytałem się w zadanie, masz rację - przepraszam.

[ghostt]

chce zwarcic uwagę na to ze to zadanie jest dość podobne do obecnego zadania nr 3 z olimpiady o diamentowy indeks wiec nie wiem czy przepadkiem ktoś nie zmodyfikował tego zadania specjalnie i nie próbuje sobie nie co ułatwić . Bo po usunięciu 2 pudelek z zadania zostaje niemal identyczne zadanie
... 2014_I.pdf