Kod: Zaznacz cały
http://smurf.mimuw.edu.pl/node/1016Zadanie 4. Pokaż, że wykładniczą funkcją tworzącą dla liczby inwolucji jest \(\displaystyle{ e^{z+\frac{z^2}{2}}}\).
Próbowałem zrobić to na dwa sposoby.
Po pierwsze - zależność rekurencyjna.
A więc zdefiniujmy sobie "liczby kmph" - \(\displaystyle{ \left\backslash n\atop k\right\backslash}\) - liczba n-inwolucji o k cyklach o dwóch elementach (reszta cykli to cykle jednoelementowe, bo to inwolucja).
Mamy zależność rekurencyjną: \(\displaystyle{ \left\backslash n \atop k \right\backslash = \left\backslash {n-1} \atop k\right\backslash+\left( n-1-2k\right) \left\backslash {n-1}\atop {k-1}\right\backslash}\). Już się z tego tłumaczę, n-inwolucję o k dwuelementowych cyklach można uzyskać albo dodając nowy element jako osobny cykl do n-1-inwolucji nie zmieniając liczby dwuelementowych cykli, albo dodać nowy element do któregokolwiek z jednoelementowych cykli n-1-inwolucji o k-1 dwuelementowych cyklach (k-1 bo tworzymy w ten sposób nowy dwuelementowy cykl). Jednoelementowych cykli będzie w takiej permutacji \(\displaystyle{ n-1-2\left(k-1\right)=n+1-2k}\).
Zatem, poszukujemy wzoru na \(\displaystyle{ i_n=\sum^{\lfloor\frac n2\rfloor}_{k=0}\left\backslash n\atop k\right\backslash}\).
No i nie wiem, co dalej.
Po drugie - wzór jawny, niestety nie zwarty.
A więc \(\displaystyle{ i_n=\frac12\sum_{k=0}^n {n\choose 2k} {2k \choose k} k!}\). Już się tłumaczę, najpierw trzeba wybrać parzystą ilość elementów, które będą tworzyć cykle podwójne (pozostałe elementy będą swoimi własnymi cyklami) - to jest \(\displaystyle{ n\choose 2k}\) - następnie spośród tych elementów połowa może zaczynać cykl, trzeba wybrać elementy na początku cyklu - to jest \(\displaystyle{ 2k\choose k}\) - pozostałe k elementów trzeba porozdzielać do k cykli, zatem \(\displaystyle{ k!}\). Ponieważ w ten sposób każdy cykl liczymy podwójnie (bo uwzględniamy kolejność elementów w cyklu), no to trzeba podzielić wynik przez dwa
I co dalej z tym wzorem? Udało mi się go przekształcić do \(\displaystyle{ i_n=\frac12\sum_{k=0}^n {n \choose 2k}{2k}^{\underline k}}\). I niestety nie wiem co dalej. To jest prawie splot dwumianowy - niestety, "prawie" robi wielką różnicę...
Jakieś naprowadzenie? Byłbym wdzięczny.
