Kombinatoryka - różnokolorowe kule i różniące się pudełka

[karpiuch]

Na ile sposobów można rozmieścić \(\displaystyle{ 14}\) różnokolorowych kul w \(\displaystyle{ 3}\) ponumerowanych pudełkach tak, aby w jednym z pudełek znalazło się co najmniej \(\displaystyle{ 8}\) kul?

Pierw wybiorę \(\displaystyle{ 8}\) kul z \(\displaystyle{ 14}\):
\(\displaystyle{ {14 \choose 8} = 3003}\)
Potem do którego z trzech pudełek włożę te \(\displaystyle{ 8}\) kul:
\(\displaystyle{ {3 \choose 1} = 3}\)

No i teraz jak wybrać te 6 pozostałych kul? Myślałem o wariacjach z powtórzeniami, ale to chyba zły pomysł..


Drugie zadanie:

Rozmieszczamy \(\displaystyle{ n}\)przedmiotów w \(\displaystyle{ k}\)pudełkach w taki sposób, że w każdym pudełku może znaleźć się co najwyżej jeden przedmiot. Na ile sposobów można dokonać takiego rozmieszczenia jeśli
a) pudełka i przedmioty są rozróżnialne;
b) pudełka i przedmioty są nierozróżnialne;
c) pudełka są nierozróżnialne, a przedmioty są rozróżnialne;
d) pudełka są rozróżnialne, a przedmioty są nierozróżnialne?

No i muszę przyznać, że tutaj wydaje mi się tylko, że w d) będzie \(\displaystyle{ C^{k}_{n}}\) jeśli \(\displaystyle{ n \ge k}\), a reszty nie wiem może jeszcze, że w b) będzie tylko jedno takie rozmieszczenie? Bo nie ma znaczenia które pudełko i które przedmioty.

[kerajs]

1.
\(\displaystyle{ {14 \choose 8} {3 \choose 1} 2^6 +{14 \choose 9} {3 \choose 1} 2^5+{14 \choose 10} {3 \choose 1} 2^4+{14 \choose 11} {3 \choose 1} 2^3+\\+{14 \choose 12} {3 \choose 1} 2^2+{14 \choose 13} {3 \choose 1} 2+{14 \choose 14} {3 \choose 1}}\)

2.
Moim zdaniem treść zadania narzuca założenie \(\displaystyle{ n \le k}\). Wtedy:
a.
\(\displaystyle{ {k \choose n} \cdot n!}\)
b.
\(\displaystyle{ 1}\)
c.
\(\displaystyle{ 1}\)
d.
\(\displaystyle{ {k \choose n}}\)

[karpiuch]

Mógłbyś mi opisać oba zadania tak mniej więcej chociaż?

[kerajs]

1.
\(\displaystyle{ {14 \choose 8} {3 \choose 1} 2^6 +{14 \choose 9} {3 \choose 1} 2^5+{14 \choose 10} {3 \choose 1} 2^4+{14 \choose 11} {3 \choose 1} 2^3+\\+{14 \choose 12} {3 \choose 1} 2^2+{14 \choose 13} {3 \choose 1} 2+{14 \choose 14} {3 \choose 1}}\)

Zdarzenie rozbiłem na sumę zdarzeń:
jedno pudełko zawiera 8 kul, a pozostałe 6 kul rozdzielam miedzy pozostałe 2 pudełka
jedno pudełko zawiera 9 kul, a pozostałe 5 kul rozdzielam miedzy pozostałe 2 pudełka
jedno pudełko zawiera 10 kul, a pozostałe 4 kul rozdzielam miedzy pozostałe 2 pudełka
....
jedno pudełko zawiera 14 kul, a pozostałe 0 kul rozdzielam miedzy pozostałe 2 pudełka

2.
Moim zdaniem treść zadania narzuca założenie \(\displaystyle{ n \le k}\). Wtedy:
a.
\(\displaystyle{ {k \choose n} \cdot n!}\)
b.
\(\displaystyle{ 1}\)
c.
\(\displaystyle{ 1}\)
d.
\(\displaystyle{ {k \choose n}}\)

A tu nie mam pojęcia co mam więcej rozpisywać bo ... nic więcej nie ma.

[karpiuch]

Czemu w c. \(\displaystyle{ 1}\) skoro przedmioty są rozróżnialne? To nic nie znaczy gdy pudełka są nierozróżnialne?

PS. w 1 zadaniu w odpowiedziach mam: \(\displaystyle{ 6 567 561}\), a tutaj wychodzi co innego

[kerajs]

Ad 1.
Nawet do głowy mi nie przyszło aby to liczyć. I nie zamierzam tego robić gdyż nie to jest meritum zadania. Może lepiej wskaż mi błąd w moim rozwiązaniu lub zaproponuj inne z którego uzyskujesz książkowy wynik, a ja się wtedy do niego odniosę.


Ad 2.
Najlepszy będzie konkretny przykład:

Rozmieszczamy 10 czekolad w 15 reklamówkach w taki sposób, że w każdej reklamówce może znaleźć się co najwyżej jedna czekolada. Na ile sposobów można dokonać takiego rozmieszczenia jeśli

b) do 10 z 15 identycznych reklamówek z Biedronki wsadzamy 10 identycznych czekolad Wedla (mlecznych z nadzieniem truskawkowym). Wszystkie reklamówki wrzucamy byle jak do bagażnika.

c) do 10 z 15 identycznych reklamówek z Biedronki wsadzamy wsadzamy 10 różnych czekolad Wedla (mleczną z nadzieniem truskawkowym,. malinowym, wiśniowym, porzeczkowym, brzoskwiniowym, cytrynowym, pomarańczowym, gruszkowym, jabłkowym i maracujowym). Wszystkie reklamówki wrzucamy byle jak do bagażnika.

I ile masz układów w b) oraz c) ?

[karpiuch]

Drugie teraz jak najbardziej rozumiem.

Co do 1 to ja sam nie wiem... Taka jest po prostu odpowiedź w skrypcie, ja sam nie wiem jak do takiej odpowiedzi dojść.. Jedyne co zauważyłem, że \(\displaystyle{ \frac{6 567 561,}{9009}=729}\) gdzie \(\displaystyle{ 9009= {14 \choose 8} \cdot {3 \choose 1}}\), ale to raczej żadnego znaczenia nie ma.. Więc zgłosić to wykładowcy, że w odp. jest błąd?

[kerajs]

Inne podejście do zad. 1).
14 elementów dzielę na trzy zbiory, w tym jeden co najmniej 8-elementowy. Możliwe podziały to:
\(\displaystyle{ (8,6,0)\\
(8,4,2)\\
(8,3,3)\\
(9,5,0)\\
(9,4,1)\\
(9,3,2)\\
(10,4,0)\\
(10,3,1)\\
(10,2,2)\\
(11,3,0)\\
(11,2,1)\\
(12,2,0)\\
(12,1,1)\\
(13,1,0)\\
(14,0,0)}\)
Ilość możliwych podziałów dla układu \(\displaystyle{ (8,6,0)}\) to: \(\displaystyle{ {14 \choose 8} {6 \choose 6} \cdot 3!}\). Silnia na końcu do ilość przypisań numerów pudełek do zbiorów.
W układzie \(\displaystyle{ (8,3,3)}\) ilość możliwych podziałów to \(\displaystyle{ {14 \choose 8} {6 \choose 3} \cdot \frac{3!}{2!}}\).

Możesz to policzyć i sprawdzić wynik z książkowym. Przy okazji suma możliwych układów ze zbiorem 8-elementowym powinna dać pierwszy składnik sumy w poprzednim rozwiązaniu, ilość możliwych układów ze zbiorem 9-elementowym powinna dać drugi składnik sumy, itd.


Przyznaję, że zupełnie nie rozumiem dlaczego chcesz wykładowcy zgłaszać błąd w odpowiedziach.

[RCCK]

A tutaj nie będzie przypadkiem po prostu \(\displaystyle{ {14 \choose 8} {3 \choose 1}3^{6}}\) ? Wybieramy \(\displaystyle{ 8}\) kulek spośród \(\displaystyle{ 14}\), potem jedno pudełko spośród \(\displaystyle{ 3}\), w którym te kulki umieścimy, a na koniec każdą pozostałą kulkę umieszczamy w jednym z \(\displaystyle{ 3}\) pudełek czyli \(\displaystyle{ 3^{6}}\) co jest równe \(\displaystyle{ 729}\) więc nawet pasuje.

[kerajs]

Pokażę dlaczego tak upieram się przy jednoznacznym określeniu tego dużego zbioru. Zmodyfikuję zadanie do łatwiejszego przypadku:
Na ile sposobów można rozmieścić 14 różnokolorowych kul w 3 ponumerowanych pudełkach tak, aby w jednym z pudełek znalazło się co najmniej 12 kul?
Niech kule będą koloru A,B,C,D,...,Ł,M.
Stosując sugerowany przez RCCK wzór \(\displaystyle{ {14 \choose 12} {3 \choose 1}3^2}\) możemy mieć zdarzenie:
1) do zbioru 12-elementowego X trafiły kule C,D,.....Ł,M.
Rozkład niewybranych kul A, B jest taki:
a) (XAB)(-)(-)
b) (XB)(A)(-)
c) (XA)(B)(-)
d) (X)(AB)(-)
e) (X)(A)(B)
2) do zbioru 12-elementowego X trafiły kule B,D,.....Ł,M.
Rozkład kul A, C jest taki:
a') (XAC)(-)(-)
b') (XC)(A)(-)
c') (XA)(C)(-)
d') (X)(AC)(-)
e') (X)(A)(C)

Jak widać a) i b) byłyby ponownie liczone jako inne zdarzenia a') i b') choć to to samo zdarzenie.

Dlatego aby uniknąć wielokrotnego zliczania tych samych zdarzeń ( powyżej pokazałem tyko rozkład na podzbiory, bez przypisywania im numerów) rozbijałem zdarzenie na sumę rozłącznych zdarzeń :

Zdarzenie rozbiłem na sumę zdarzeń:
jedno pudełko zawiera 8 kul, a pozostałe 6 kul rozdzielam miedzy pozostałe 2 pudełka
jedno pudełko zawiera 9 kul, a pozostałe 5 kul rozdzielam miedzy pozostałe 2 pudełka
jedno pudełko zawiera 10 kul, a pozostałe 4 kul rozdzielam miedzy pozostałe 2 pudełka
....
jedno pudełko zawiera 14 kul, a pozostałe 0 kul rozdzielam miedzy pozostałe 2 pudełka

[RCCK]

Masz rację, nie przemyślałem tego. W takim razie trochę dziwna ta odpowiedź no ale nie ma się co tym sugerować jak ja to zrobiłem.

[karpiuch]

Napisałem e-maila do wykładowcy i upiera się przy swoim wyniku, zaraz przedstawię jej to dokładniej rozpiszę i zobaczymy.


PS. wysyłam jej to, bo prosiła aby jakieś ewentualne błędy zgłaszać (to jej skrypt)