Liczby Stirlinga vs Multipodzbiory

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Mrz355
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 4 lis 2015, o 20:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 6 razy

Liczby Stirlinga vs Multipodzbiory

Post autor: Mrz355 »

Ś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?
Awatar użytkownika
arek1357
Użytkownik
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

Post autor: arek1357 »

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}}\)
ODPOWIEDZ