Generatingfunctionology!
Definiamo la funzione (
formal power serie, visto che non converge sempre) $ \displaystyle S_n(x)=\sum_{k=0}^{\infty} k^nx^k $. Il problema consisterà allora nel calcolare $ S(1/2) $.
Vogliamo dimostrare che questa somma si può scrivere anche come $ \displaystyle S_n(x)=\sum_{k} k! \mathcal{S}_n^{(k)} \frac{x^k}{(1-x)^{k+1}} $, dove $ \mathcal{S}_n^{(k)} $ indica i
numeri di Stirling di seconda specie.
Chiaramente, una volta nota la formula, si potrà dare anche una dimostrazione diretta basata sull'induzione, ma io preferisco farvi vedere come l'ho ricavata perché lo ritengo un istruttivo esempio di come utilizzare le funzioni generatrici.
Iniziamo con calcolare $ S_0(x) $, che, noncuranti delle perplessità sollevate dal porre $ 0^0=1 $, definiamo essere $ \displaystyle S_0(x)=1+x+x^2+\dots+x^k+\dots=\frac1{1-x} $.
A questo punto, vorremmo passare a $ S_1(x) $. Per farlo, dobbiamo moltiplicare ogni coefficiente per il relativo esponente di $ x $. Questa operazione ci fa venire il sospetto che si possa sfruttare la derivazione. In effetti, si nota (e si dimostra, facilmente) che $ \displaystyle S_k(x)=x\frac{d}{dx}S_{k-1}(x) $.
Indichiamo per comodità con $ \vartheta $ l'operatore $ \displaystyle x\frac{d}{dx} $ e con $ \vartheta^{(m)} $ la composizione di $ \vartheta $ con se stesso $ m $ volte. A questo punto, possiamo dire che $ \displaystyle S_n(x)=\vartheta^{(k)}\left( \frac{1}{1-x} \right) $.
Cerchiamo ora un modo conveniente per calcolare questa espressione. Per farci un po' le idee, calcoliamo con questo metodo le prime tre funzioni:
$ \displaystyle S_1(x)=\frac{x}{(1-x)^2} $,
$ \displaystyle S_2(x)=\frac{x}{(1-x)^2}+2\frac{x^2}{(1-x)^3} $,
$ \displaystyle S_3(x)=\frac{x}{(1-x)^2}+6\frac{x^2}{(1-x)^3}+6\frac{x^3}{(1-x)^4} $.
Notiamo facilmente che contengono espressioni del tipo $ \displaystyle \frac{x^k}{(1-x)^{k+1}} $ con un opportuno coefficiente. Chiamiamo $ N^n_k $ il coefficiente di $ \displaystyle \frac{x^k}{(1-x)^{k+1}} $ in $ S_n(x) $. Dimostriamo ora questo fatto e ricaviamo una formula ricorsiva per $ N^n_k $.
Applicando $ \vartheta $ a ogni termine si ha che $ \displaystyle \vartheta\left( \frac{x^k}{(1-x)^{k+1}} \right) = k \frac{x^k}{(1-x)^{k+1}} + (k+1) \frac{x^{k+1}}{(1-x)^{k+2}} $, come è facile verificare (lasciato al lettore). Questo significa che $ S_n(x) $ stesso ha la forma richiesta.
Inoltre, ricaviamo la relazione ricorsiva $ N^n_k=kN^{n-1}_k+kN^{n-1}_{k-1} $. Sappiamo anche che $ N^n_k=0 $ per $ k<1 \lor k>n $ e $ N^0_0=1 $. Queste condizioni determinano completamente i coefficienti.
Definiamo le funzioni generatrici $ \displaystyle G_k(x)=\sum_{n} N^n_k x^n $. Dalla relazione tra i coefficienti appena ricavata, deduciamo che $ N^n_k x^n = k x N^{n-1}_k x^{n-1}+k x N^{n-1}_{k-1} x^{n-1} $, da cui segue la relazione tra le funzioni $ G_k(x)=kxG_k(x)+kxG_{k-1}(x) $, ovvero $ \displaystyle G_k(x)=\frac{kx}{1-kx}G_{k-1}(x) $.
Del resto, sappiamo che $ G_0(x)=1 $, quindi per induzione $ \displaystyle G_k(x)=\prod_{j=1}^{k} \frac{jx}{1-jx}=k!\prod_{j=1}^{k} \frac{x}{1-jx} $.
Ma $ \displaystyle \prod_{j=1}^{k} \frac{x}{1-jx} $ è la funzione generatrice dei
numeri di Stirling di seconda specie, quindi si ha che $ N^n_k=k!\mathcal{S}_n^{(k)} $.
Ora, $ \displaystyle S_n(x) = \sum_{k} N^n_k \frac{x^k}{(1-x)^{k+1}} = \sum_{k} k! \mathcal{S}_n^{(k)} \frac{x^k}{(1-x)^{k+1}} $.
Il problema originario consisteva nel calcolare $ S_n(1/2) $, il quale è $ \displaystyle 2\sum_{k}k!\mathcal{S}_n^{(k)} $.
I primi valori, per $ n $ che va da $ 1 $ a $ 10 $, sono $ 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126,\dots $
Ti posso assicurare che io l´ho risolto solo con i miei mezzi (che sono prettamente olimpici... per assicurartelo ti dico che sono di primo liceo 
