Podziały i nieporządki

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Quba1999
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 18 lis 2018, o 20:45
Płeć: Mężczyzna
Lokalizacja: Warszawa

Podziały i nieporządki

Post autor: Quba1999 »

Ile jest różnych permutacji n-elementowych rozkładalnych na 2 lub 3 cykle?
Trzeba skorzystać z liczb Stirlinga pierwszego rodzaju. Nie wiem, która odpowiedź jest poprawna:

\(\displaystyle{ s\left( n,\right2) + s\left( n,\right3)}\)

czy

\(\displaystyle{ s\left( n,\right2) + s\left( n,\right3) - s\left( n,\right6)}\)
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

Re: Podziały i nieporządki

Post autor: arek1357 »

Podejrzewam, że obie są złe...

\(\displaystyle{ s(n,k)}\) - oznacza ilość permutacji o k cyklach, ale nic w tym wzorze nie ma na temat długości tych cykli... tam się będą wcinały cykle różnych długości nie tylko dwa i trzy...

\(\displaystyle{ s}\)- ilość cykli o długości dwa...

\(\displaystyle{ t}\)- ilość cykli o długości trzy...

i teraz masz:

\(\displaystyle{ 2s+3t=n}\) ilość rozwiązań takiego równania... tyle będzie podziałów na cykle o strikte takich długościach...

a teraz ile jest permutacji o dokładnie takim podziale:

\(\displaystyle{ \frac{n!}{2^s \cdot s! \cdot 3^t \cdot t!}}\)

teraz to obkładasz znakiem sumy:

\(\displaystyle{ \sum_{2s+3t=n}^{}\frac{n!}{2^s \cdot s! \cdot 3^t \cdot t!}}\)

taki powinien być wynik...

Sprawdź sobie dla małych.: \(\displaystyle{ n=1,2,3,4,5}\) na piechotę, że działa ten wzór...

Nawiasem mówiąc jest to klasa elementów sprzężonych w grupie \(\displaystyle{ S_{n}}\)
ODPOWIEDZ