Funkcja i nieporządki

[mol_ksiazkowy]

Wyznaczyć funkcję tworzącą ciągu \(\displaystyle{ D_n}\)

Ukryta treść:    

\(\displaystyle{ D_n}\) to ilość nieporządków na zbiorze \(\displaystyle{ n}\) elementowym
(\(\displaystyle{ D_n= n D_{n-1}+ (-1)^n}\); \(\displaystyle{ D_2=1}\))

[Premislav]

Funkcja tworząca tego ciągu nie wyraża się przez funkcje elementarne (trzeba użyć co najmniej funkcji całkowo-wykładniczej, jak wynika z moich obliczeń), natomiast na stackexchange podano kilka ładnych sposobów na znalezienie wykładniczej funkcji tworzącej.

[mol_ksiazkowy]

na stackexchange podano kilka ładnych sposobów na znalezienie wykładniczej funkcji tworzącej.

ale wystarczy jeden...

[Premislav]

Taki mi się wyjątkowo spodobał (uprzedzam, że ja nie wymyślam takich rzeczy, ode mnie w zasadzie jest tylko dowód lemaciku):
przyjmujemy \(\displaystyle{ D_0=1}\) (permutacja zbioru pustego formalnie spełnia definicję nieporządku), ponadto oczywiście \(\displaystyle{ D_1=0}\). Udowodnimy następującą uroczą, a prostą zależność:
\(\displaystyle{ \sum_{k=0}^{n}{n \choose k}D_{n-k}=n! \ (*)}\)
Dowód to prosta kombinatoryka: zliczamy na dwa sposoby permutacje zbioru \(\displaystyle{ n}\)-elementowego. Z jednej strony jest ich oczywiście \(\displaystyle{ n!}\), z drugiej strony możemy policzyć oddzielnie permutacje o \(\displaystyle{ k}\) punktach stałych dla \(\displaystyle{ k=0,1,\ldots n}\) i zsumować.
Dla ustalonego \(\displaystyle{ k}\) z powyższej listy permutacji zbioru n-elementowego o dokładnie \(\displaystyle{ k}\) punktach stałych jest właśnie \(\displaystyle{ {n \choose k}D_{n-k}}\):
na \(\displaystyle{ {n \choose k}}\) sposobów wybieramy \(\displaystyle{ k}\) elementów zbioru \(\displaystyle{ n}\)-elementowego, które będą punktami stałymi permutacji, a na \(\displaystyle{ D_{n-k}}\) sposobów „mieszamy" pozostałych \(\displaystyle{ n-k}\) elementów rzeczonego zbioru (tj. tyle jest oczywiście permutacji podzbioru \(\displaystyle{ n-k}\)-elementowego, które nie mają punktu stałego). Sumując to dostajemy właśnie \(\displaystyle{ (*)}\).
Teraz dzielimy stronami przez \(\displaystyle{ n!}\)
otrzymując po rozpisaniu symbolu Newtona z definicji i skróceniu
\(\displaystyle{ \sum_{k=0}^{n} \frac{1}{k!}\cdot \frac{1}{(n-k)!}D_{n-k}=1}\)
i zauważamy, że suma
\(\displaystyle{ \sum_{k=0}^{n}\frac{1}{k!}\cdot \frac{1}{(n-k)!}D_{n-k}}\)
odpowiada splotowi ciągów \(\displaystyle{ a_n=\frac{1}{n!}}\) oraz \(\displaystyle{ b_n=\frac{1}{n!}D_n}\),
a funkcja tworząca splotu to iloczyn funkcji tworzących, w związku z tym:
\(\displaystyle{ \left( \sum_{n=0}^{ \infty }\frac{1}{n!}x^n \right)\left( \sum_{n=0}^{ \infty }\frac{1}{n!}D_nx^n \right) = \sum_{n=0}^{ \infty } x^n\\ e^x}\),
i tu dostrzegamy rozwinięcia w szereg potęgowy znanych funkcji, zatem jeśli przez \(\displaystyle{ G(x)}\) oznaczymy wykładniczą funkcję tworzącą ciągu \(\displaystyle{ (D_n)_{n\ge 0}}\), to
\(\displaystyle{ e^xG(x)=\frac{1}{1-x}\\ G(x)=\frac{e^{-x}}{1-x}}\)

Link: ... rangements