Święty mikołaj i prezenty

[Gwynnbleid1]

Witam

Mam następujące zadanie:
Roztargniony Mikołaj przygotował 100 różnych paczek, w rozwożeniu których pomagają mu 3 identyczne renifery zaprzężone w sanie. Na ile sposobów Mikołaj może rozłożyć paczki do sań jeśli nie wszystkie sanie muszą wyruszyć w podróż z Mikołajem?

Moja pierwsza myśl to \(\displaystyle{ 3^{100}}\)
Każdą paczkę możemy spakować na trzy sposoby, bo mamy trzy sanie do wyboru.
Sprawdziłem to dla dwóch paczek i po rozpisaniu wyszło mi 6 sposobów zamiast 9.

Prosiłbym o weryfikację mojego rozumowania i nakierowanie na właściwe tory z wytłumaczeniem czemu rozumowanie jest nieprawidłowe. Zależy mi równie mocno na zrozumieniu co na dobrej odpowiedzi.

[Kacperdev]

Problem z metodą wariacji polega, że bierze ona także pod uwagę "sposoby" kolejności ułożenia prezentów na saniach tzn. sanie 1 {prezent1, prezent2} metoda ta dolicza takze {prezent2, prezent1}

[norwimaj]

Problem z metodą wariacji polega, że bierze ona także pod uwagę "sposoby" kolejności ułożenia prezentów na saniach tzn. sanie 1 {prezent1, prezent2} metoda ta dolicza takze {prezent2, prezent1}

Nieprawda.

Sprawdziłem to dla dwóch paczek i po rozpisaniu wyszło mi 6 sposobów zamiast 9.

Dla dwóch paczek prawidłowym wynikiem jest \(\displaystyle{ 2}\): obie paczki na jednych saniach albo na różnych saniach. Na pewno bierzesz pod uwagę, że renifery z saniami są nierozróżnialne?

[Gwynnbleid1]

Wiec muszą zatem to być kombinacje z powtórzeniami.
k = 100
n = 3
\(\displaystyle{ {k + n -1 \choose k} = \frac{(k + n - 1)!}{(k!(n - 1)!)!} = \frac{(100 + 3 - 1)!}{(100!(3 - 1)!)!} = \frac{(102)!}{100!2!} = \frac{101 \cdot 102}{2} = 51 \cdot 101 = 5151}\)

Po wysłaniu dopiero zobaczyłem post Kacperdev'a:

Problem z metodą wariacji polega, że bierze ona także pod uwagę "sposoby" kolejności ułożenia prezentów na saniach tzn. sanie 1 {prezent1, prezent2} metoda ta dolicza takze {prezent2, prezent1}

Nieprawda.

Co masz na myśli mówiąc nieprawda. To że nie ma tutaj zastosowania, czy że całe stwierdzenie jest nieprawidłowe ?

Sprawdziłem to dla dwóch paczek i po rozpisaniu wyszło mi 6 sposobów zamiast 9.

Dla dwóch paczek prawidłowym wynikiem jest \(\displaystyle{ 2}\): obie paczki na jednych saniach albo na różnych saniach. Na pewno bierzesz pod uwagę, że renifery z saniami są nierozróżnialne?

Rzeczywiście nie wziąłem tego zupełnie pod uwagę. Czyli dla trzech prezentów byłoby:
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.
Natomiast dla 100 paczek dalej będzie \(\displaystyle{ 3}\), ponieważ nie mamy już więcej możliwości. Czy tak ?

[norwimaj]

Wiec muszą zatem to być kombinacje z powtórzeniami.

Nie. Kombinacje z powtórzeniami są, gdy są nierozróżnialne kule i rozróżnialne pojemniki, a nie na odwrót.

Co masz na myśli mówiąc nieprawda.

Że zdanie napisane przez Kacperdev'a jest fałszywe. Pomylił się on i wskazał błąd tam, gdzie akurat tego błędu nie było.

Czyli dla trzech prezentów byłoby:
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.

Nie. Jeśli mamy prezenty \(\displaystyle{ p_1,p_2,p_3}\), to mamy następujące możliwości podziału bagażu na renifery:

1. \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\)
2. \(\displaystyle{ \{\{p_1,p_2\},\{p_3\},\{\}\}}\)
3. \(\displaystyle{ \{\{p_1,p_3\},\{p_2\},\{\}\}}\)
4. \(\displaystyle{ \{\{p_2,p_3\},\{p_1\},\{\}\}}\)
5. \(\displaystyle{ \{\{p_1\},\{p_2\},\{p_3\}\}}\)

[Gwynnbleid1]

Wiec muszą zatem to być kombinacje z powtórzeniami.

Nie. Kombinacje z powtórzeniami są, gdy są nierozróżnialne kule i rozróżnialne pojemniki, a nie na odwrót.

Trochę mi się to w głowie komplikuje. Czy znasz może jakąś rozpiskę, która podpowiada z czym mamy doczynienia ? Rozróżnialne to to, nierozróżnialne to to, kolejność ważna i nieważna itp? Wkułbym to na pamięć i ułatwiłoby mi to niezmiernie życie. Znalazłem wcześniej coś takiego: , ale jak widzę daleko temu do perfekcji...

Co masz na myśli mówiąc nieprawda.

Że zdanie napisane przez Kacperdev'a jest fałszywe. Pomylił się on i wskazał błąd tam, gdzie akurat tego błędu nie było.

Myślałem, że wariacje rzeczywiście uwzględniają kolejność i a,b to nie to samo co (b,a)

Czyli dla trzech prezentów byłoby:
każdy w jednej, dwie w jednej i jedna w drugiej i trzy w różnych, razem \(\displaystyle{ 3}\) sposoby.

Nie. Jeśli mamy prezenty \(\displaystyle{ p_1,p_2,p_3}\), to mamy następujące możliwości podziału bagażu na renifery:

1. \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\)
2. \(\displaystyle{ \{\{p_1,p_2\},\{p_3\},\{\}\}}\)
3. \(\displaystyle{ \{\{p_1,p_3\},\{p_2\},\{\}\}}\)
4. \(\displaystyle{ \{\{p_2,p_3\},\{p_1\},\{\}\}}\)
5. \(\displaystyle{ \{\{p_1\},\{p_2\},\{p_3\}\}}\)

Teraz dopiero spojrzałem, że prezenty są różne. Przyznam się szczerze, że teraz nie wiem jak ugryźć ten problem dla 100 prezentów. Jakaś wskazówka ?

[norwimaj]

Zacznij tak jak zacząłeś, czyli jeśli rozróżniamy renifery, to mamy \(\displaystyle{ 3^{100}}\) możliwości. Teraz trzeba się zastanowić, jak ten wynik się zmieni, gdy przestaniemy renifery rozróżniać. Rozróżniając renifery liczymy poszczególne ustawienia wielokrotnie, tak jak w poprzednim przykładzie ustawienie \(\displaystyle{ \{\{p_1,p_2\},\{p_3\},\{\}\}}\) by było liczone sześciokrotnie:
\(\displaystyle{ (\{p_1,p_2\},\{p_3\},\{\}),}\)
\(\displaystyle{ (\{p_1,p_2\},\{\},\{p_3\}),}\)
\(\displaystyle{ (\{p_3\},\{p_1,p_2\},\{\}),}\)
itd.

a ustawienie \(\displaystyle{ \{\{p_1,p_2,p_3\},\{\},\{\}\}}\) trzykrotnie.