Zadania ze zliczania

[Downonmyluck]

Na balu jest 10 kawalerów i 12 panien (wszyscy rozróżnialni). Wszystkie panny potrafią tańczyć poloneza i walca oraz jedna potrafi również tańczyć tango. Kawalerowie podchodzą po kolei do panien i wybierają taniec. Na ile sposobów mogą odbyć się tańce, jeśli:
a) każda panna może tańczyć najwyżej z jednym kawalerem;
b) każda z panien może zostać poproszona do tańca kilka razy, w tym dziesięć.

Czy ktoś mógłby sprawdzić rozwiązanie? Wydaje mi się, że można zrobić to prościej albo się po prostu mylę i rozwiązanie jest błędne.

a) Każda panna może zatańczyć tylko raz. Oznaczmy pannę umiejącą zatańczyć trzy tańce jako X, mamy 3 przypadki:

1) X nie uczestniczy w tańcu:

wtedy do dyspozycji mamy 11 panien, ilość tańców to ilość funkcji różnowartościowych ze zbioru \(\displaystyle{ [10]}\) w zbiór \(\displaystyle{ [11]}\) pomnożona przez \(\displaystyle{ 2^{10}}\) (uwzględniamy to, że każda para, a będzie ich 10, wybiera 1 z 2 tańców.
Zatem sposobów jest \(\displaystyle{ 11 \cdot 10...\cdot 2 \cdot 2^{10}}\)

2)X tańczy:

Teraz postępujemy nieco inaczej - najpierw wybieramy partnera dla X (10 sposobów) i następnie taniec tej pary (3 sposoby). Następnie resztę par (będzie ich 9, bo tyle kawalerów zostało) na \(\displaystyle{ 10 \cdot 3 \cdot 11 \cdot 10... \cdot 3 \cdot 2^{9}}\)

Łączna ilość sposobów to suma tych 2 rozłącznych przypadków.

b) Tutaj się komplikuje, bo nie wiemy, w ilu tańcach bierze udział X. Znów przypadki:

1) X nie tańczy tango lub nie uczestniczy w tańcach - \(\displaystyle{ 12^{10} \cdot 2^{10}}\) sposobów

2) X tańczy tango. Musimy uwzględnić dowolną ilość tańców, w których bierze udział X (od 1 do 10)

Niech \(\displaystyle{ k}\) oznacza liczbę tańców, w których uczestniczy X.
Najpierw wybieramy partnerów dla X (od 1 do 10) na \(\displaystyle{ {10 \choose k}}\) sposobów, gdzie \(\displaystyle{ 1 \le k \le 10}\) i resztę tańców na \(\displaystyle{ 11^{10-k} \cdot 2^{10-k}}\).

Zatem wszystkich sposobów w 2 przypadku jest \(\displaystyle{ \sum_{k=1}^{10} {10 \choose k} \cdot 11^{10-k} \cdot 2^{10-k}}\).

Łącznie sposobów dla b) jest \(\displaystyle{ 12^{10} \cdot 2^{10} + \sum_{k=1}^{10} {10 \choose k} \cdot 11^{10-k} \cdot 2^{10-k}}\).

Wydaje mi się, że to nie jest poprawne rozwiązanie, ale nie mogę znaleźć luki, tj. chyba wszystkie możliwości zliczyłem i żadnej nie opuściłem.

[arek1357]

Najpierw wybór par a potem suriekcje par do tańców odpowiednich.

[Downonmyluck]

Najpierw wybór par a potem suriekcje par do tańców odpowiednich.

Suriekcje z jakiego zbioru? Dla każdego tańca (w zasadzie układu tańców) zliczamy liczbę ciągów długości 10, gdzie na i-tym (i-ty kawaler) miejscu jest liczba j (j-ta panna) dla \(\displaystyle{ 1 \le j \le 12}\) i każdej parze z ciągu przyporządkowujemy taniec. Jeśli chodzi o takie pary, to nie muszą być suriekcją. Co jeśli wszystkie pary z układu tańczą ten sam taniec? W dodatku i tak trzeba rozważyć przypadek, gdy X nie bierze udziału. Nie bardzo rozumiem, co miałeś na myśli.

[arek1357]

Suriekcje ze zbioru par w zbiór tańców. I wtedy nie przejmujesz się czy jest tylko jeden taniec trzy trzy...