Mam za zadanie policzyć liczbę inwolucji m elementów. Próbowałem to zrobić tak:
Na razie przyjmuję \(\displaystyle{ m=2n}\). Zliczamy permutacje w zależności od liczby cykli. Cykle mogą być jedno lub dwu elementowe. Jeśli cykli 2-elementowych jest \(\displaystyle{ i}\) (\(\displaystyle{ i=0 \dots n}\)), to cykli ogółem jest \(\displaystyle{ 2n-i}\). Ustalamy \(\displaystyle{ i}\).
Ustawiamy liczby w dowolnym porządku (\(\displaystyle{ (2n)!}\) opcji), niech na początku będą cykle dwuelementowe, a potem jednoelementowe. Kolejność w cyklach dwuelementowych się nie liczy (\(\displaystyle{ 1/2^i}\)), kolejność cykli dwuelementowych (\(\displaystyle{ 1/i!}\)) ani jednoelementowych (\(\displaystyle{ 1/(2n-2i)!}\)) też nie.
Dostajemy \(\displaystyle{ \frac{(2n)!}{(2n-2i)!2^{i}i!} = {2n \choose 2i} \frac{1}{2^i} \frac{(2i)!}{i!}}\)
Stąd liczba inwolucji to \(\displaystyle{ \sum_{i=0}^{n} {2n \choose 2i} \frac{1}{2^i} \frac{(2i)!}{i!}}\)
Próbowałem uprościć tę sumę przez zaburzanie, ale nie dostaję żadnego sensownego wyniku i zaczynam podejrzewać, że gdzieś popełniłem błąd.
1. Czy moje rozumowanie jest poprawne?
2. Czy istnieje jakaś prostsza interpretacja kombinatoryczna tego zadania?
Liczba inwolucji m-elementowych
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Liczba inwolucji m-elementowych
Ten wzór ma dobre zadatki ale jest bardzo niestrawny i może się sypnąć...
Ja bym proponował nie zakładać, że muszą być parzyste, zapisałbym to tak:
\(\displaystyle{ \sum_{i+2j=n}^{} \frac{n!}{1^i \cdot 2^j \cdot i! \cdot j!}}\)
Teraz można próbować zwijać...
Ja bym proponował nie zakładać, że muszą być parzyste, zapisałbym to tak:
\(\displaystyle{ \sum_{i+2j=n}^{} \frac{n!}{1^i \cdot 2^j \cdot i! \cdot j!}}\)
Teraz można próbować zwijać...