Zadanka z kombinatoryki

[Cinoq]

Zad 1. Mikołaj przygotował paczki świąteczne typu A, B, C. Na ile sposobów Mikołaj może skomponować worek z 30 prezentami, tak aby w worku znalazła się paczka każdego rodzaju? Czy to bedzie \(\displaystyle{ 3! * 3 ^{27}}\) ?

Zad 2.
Mikołaj przygotował 10 identycznych paczek, w rozwożeniu których pomagają mu trzy renifery zaprzężone w sanie. Na ile sposobów Mikołaj może rozłożyć paczki do sań jeśli na każdych saniach musi znaleźć się co najmniej jedna paczka?
Na to zadanie nie mam pomysłu, myślałem o liczbach Sterlinga 2 rodzaju, ale do identycznych paczek to raczej nie pasuje.. Prosze o pomoc, bo potrzebuje tego jak najszybciej.

[loitzl9006]

Zad.1
Kolejność nie ma znaczenia, elementy mogą (nawet muszą) się powtarzać -> kombinacje z powtórzeniami
Policz ilość wszystkich możliwości skomponowania worka, a następnie policz ilość zdarzeń niesprzyjających (worek tylko z dwoma rodzajami paczek: AB, AC, BC; i tylko z jednym rodzajem paczki - 3 możliwości). Od wszystkich odejmujesz niesprzyjające i masz wynik.

Zad.2
Pewnie można prościej, ale ja bym wypisał po kolei możliwe kombinacje, np.
\(\displaystyle{ 8,1,1 \\ 7,2,1 \\ 6,3,1 \\ 6,2,2 \\ 5,4,1 \\ 5,3,2 \\ 4,4,2 \\ 4,3,3}\)

Uwzględnić permutacje (przestawienie cyfr) dla każdego z przypadków: dla przypadków jak np. \(\displaystyle{ 8,1,1}\) ; \(\displaystyle{ 4,3,3}\) będzie \(\displaystyle{ \frac{3!}{2!} = 3}\) możliwości, zaś dla przypadków np. \(\displaystyle{ 5,3,2}\) (na każdych sankach inna liczba paczek) - będzie \(\displaystyle{ 3!}\) możliwości. Potem zsumować wszystko i masz wynik.

[Cinoq]

hm, jeśli chodzi o zadanie pierwsze to będzie\(\displaystyle{ 3 ^{30} - 2 ^{30} - 3 ?}\) ?
Dobrze myśle?

[loitzl9006]

Ale ty liczysz to wariacjami z powtórzeniami (wtedy istotna kolejność). Załóżmy, że Mikołaj spakował do worka najpierw jedną paczkę A, potem jedną B, a potem już tylko same A. A następny worek przygotował, pakując najpierw jedną B, potem jedną A, a potem już tylko same A. W pierwszej sytuacji i w drugiej zawartość worka będzie taka sama, a te dwie sytuacje różnią się tylko kolejnością pakowania. Wariacja to uwzględnia, a kombinacja - nie. Dlatego trzeba skorzystać z kombinacji z powtórzeniami:

... B3rzeniami

\(\displaystyle{ n=3 \\ k=30}\)
wszystkie możliwości

Niesprzyjające podobnie:
\(\displaystyle{ n=2 \\ k=30}\)
czyli tylko dwa elementy do dyspozycji, itd.

[Cinoq]

Jasne, jesteś wielki, w końcu zrozumiałem na chłopski rozum jak odróżnić wariacje od kombinacji. Dzięki!

[mat_61]

...następnie policz ilość zdarzeń niesprzyjających (worek tylko z dwoma rodzajami paczek: AB, AC, BC; i tylko z jednym rodzajem paczki - 3 możliwości). Od wszystkich odejmujesz niesprzyjające i masz wynik.

Zauważ, że jak odejmiesz od wszystkich możliwości, te obliczone jako kombinacje z powtórzeniami dla dwóch rodzajów paczek, czyli AB, AC, BC to w każdym z przypadków odejmiesz także po dwa warianty z jednym rodzajem paczek.

Na przykład licząc jako kombinacje z powtórzeniami worek z paczkami zawierającymi elementy \(\displaystyle{ \left\{ A;B\right\}}\) liczysz także warianty tylko z elementem \(\displaystyle{ A}\) i warianty tylko z elementem \(\displaystyle{ B}\).

Oznacza to, że korzystając z zasady włączeń i wyłączeń należy dodać (a nie odjąć) te 3 warianty z jednym rodzajem paczki, bo wcześniej odjąłeś już każdy z jednopaczkowych wariantów dwukrotnie.

Oczywiście można zadanie zrobić znacznie prościej umieszczając w worku po jednej paczce A, B i C a następnie dokładając dowolny zestaw 27 paczek (kombinacja 27-elementowa z powtórzeniami ze zbioru 3-elementowego).

-- 30 sty 2012, o 18:33 --

Co do zadania 2) to jest pytanie czy te sanie są rozróżnialne (moim zdaniem powinny być, bo nie ma dwóch jednakowych reniferów ). Jeżeli są rozróżnialne np. sanie A, B, C, to zadanie jest analogiczne jak w zadaniu 1).

Na każde sanie dajemy po jednej paczce a pozostałe siedem rozmieszczamy dowolnie na saniach (kombinacja 7-elementowa z powtórzeniami ze zbioru 3-elementowego).

[Cinoq]

Ok, jeśli chodzi o zad 1 to wyszło mi 496 możliwości dla komponacji worka z wszystkich paczek, dla komponacji tylko z dwoch paczek 31 mozliwosci, czyli 496-31=465. Dobrze? Jeśli tak to co teraz z tą trójką? Wg mnie powinienem odjąć..

[loitzl9006]

Rozumowanie mat_61 mnie przekonuje, że trzeba dodać te trzy możliwości, a nie odjąć. Chociaż wychodziła mi okrągła liczba \(\displaystyle{ 400}\) która mnie (błędnie) upewniała o poprawności wyniku

***
Te \(\displaystyle{ 31}\), które odejmujesz, to wyszło Ci tylko dla paczek (załóżmy) AB. Trzeba jeszcze uwzględnić worki złożone z paczek tylko AC i tylko BC, zatem wyjdzie, że zamiast odjąć \(\displaystyle{ 31}\), będziesz odejmował \(\displaystyle{ 3 \cdot 31}\).

[mat_61]

1) Powinieneś odjąć nie \(\displaystyle{ 31}\) ale \(\displaystyle{ 3 \cdot 31}\), bo tak jak napisał Ci loitzl9006 masz 3 różne warianty dwupaczkowe tzn. AB, AC, BC.

2) Czy znasz pojęcie zasady włączeń i wyłączeń?
Oczywiście jak liczysz warianty trzypaczkowe, czyli ABC, to masz tam także warianty dwupaczkowe i warianty jednopaczkowe, czyli w worku są same paczki A lub same paczki B lub same paczki C (które należy odjąć).

Pamiętaj jednak, że:

a - jak liczysz warianty dwupaczkowe AB, to wśród nich są także warianty jednopaczkowe, czyli same paczki A i same paczki B

b - jak liczysz warianty dwupaczkowe AC, to wśród nich są także warianty jednopaczkowe, czyli same paczki A i same paczki C

c - jak liczysz warianty dwupaczkowe BC, to wśród nich są także warianty jednopaczkowe, czyli same paczki B i same paczki C

Odejmując więc ilości obliczone wg punktów a, b i c odejmujesz dwukrotnie wszystkie warianty jednopaczkowe.

Jaki z tego wniosek?

[Cinoq]

że musze jednokrotnie dodać!:)-- 30 sty 2012, o 19:12 --czyli definitywny wynik to 406, zgadza sie?:)

[mat_61]

Tak.

Podobnie jak obliczysz wg mojej drugiej propozycji:

\(\displaystyle{ {27+3-1 \choose 27} =406}\)