Św. Mikołaj miał lekką sklerozę i nie pamiętał, które z domów już odwiedził,
a które nie. Przy pewnej ulicy było 12 różnych domów, które
odwiedzić powinien i w każdym z nich był, ale w niektórych wielokrotnie.
Jak policzyły zdziwione renifery razem zanotował aż 25 odwiedzin.
Na ile różnych sposobów (kolejność odwiedzin jest istotna) mogła przebiegać
wizyta św. Mikołaja przy tej ulicy?
Mam do tego zadania dwa rozwiązania i nie mam pojęcia dlaczego się od siebie różnią.
Jedno opiera się na liczbach Stirlinga drugiego rodzaju.
\(\displaystyle{ S(25,12) \cdot 12!}\) - tworzymy wszystkie możliwe 12 podzbiorów z 25 elementów i permutujemy je, aby uwzględnić kolejność.
Drugie rozwiązanie to multipodzbiór:
\(\displaystyle{ x_{1}+x_{2}+x_{3}+...+x_{12}=25}\) , gdzie \(\displaystyle{ x_{i}}\) to kolejne domki a \(\displaystyle{ 25}\) to ilość odwiedzin.
Ponieważ jednak każdy musi zostać odwiedzony co najmniej raz podstawiamy:
\(\displaystyle{ y_{i}=x_{i}-1}\)
Więc równanie wygląda tak:
\(\displaystyle{ y_{1}+y_{2}+y_{3}+...+y_{12}=13}\)
Rozwiązanie to:
\(\displaystyle{ \binom{12+13-1}{13}}\)
Teraz jeszcze kolejność:
\(\displaystyle{ \binom{24}{13}\cdot 12!}\)
Nie rozumiem dlaczego te wyniki się różnią. Stawiam na błędne załatwienie kolejności w rozwiązaniu drugim. Wie ktoś może coś na ten temat?
Liczby Stirlinga vs Multipodzbiory
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Liczby Stirlinga vs Multipodzbiory
Jasne że się różnią i powinny się różnić bo liczby Stirlinga rozróżniają kuleczki, które wrzucamy do pudełek a w tym twoim równaniu kuleczki są nierozróżnialne liczy się tylko ilość upakowanie w pudełkach czyli w \(\displaystyle{ x_{i}}\)