==Include(page="template/taskheader" task_id="stirling")==

Se definesc numerele lui Stirling de speţa $I$, $s(n,m)$, ca fiind numărul de permutări de ordin $n$ cu exact $m$ cicluri. Similar, se definesc numerele lui Stirling de speţa a $II$-a, $S(n,m)$, ca fiind numărul de partiţionări ale unei mulţimi de $n$ elemente în $m$ submulţimi nevide.

Se definesc numerele lui Stirling de speţa $I$, $s(n,m)$, ca fiind coeficienţii dezvoltării <tex> x(x-1)...(x-n+1) = \displaystyle\sum_{m = 0}^n s(n,m)*x^k </tex>. Similar, se definesc numerele lui Stirling de speţa a $II$-a, $S(n,m)$, ca fiind numărul de partiţionări ale unei mulţimi de $n$ elemente în $m$ submulţimi nevide.

h2. Cerinţă

h2. Restrictii
* $1 ≤ T ≤ 1000$

* $0 ≤ N, M ≤ 200$

* $0 ≤ n, m ≤ 200$

h2. Exemplu

h2. Indicaţii de rezolvare

Ideea "naivă" de rezolvare a acestei probleme este determinarea răspunsului generând efectiv, prin metoda backtracking, fie toate permutările de ordin $n$ şi determinarea celor care au $m$ cicluri, fie toate partiţionările unei mulţimi de $n$ elemente în $m$ submulţimi nevide. Această rezolvare are complexitate exponenţială şi va obţine $10$ puncte.

Ideea naivă de rezolvare a acestei probleme este determinarea răspunsului problemei prin metoda backtracking. Această rezolvare are complexitate exponenţială şi va obţine $10$ puncte.

În urma unor demonstraţii matematice (explicate pe larg în link-urile de mai jos), pentru funcţiile lui Stirling se pot obţine recurenţele:
<tex> s(n,m) = s(n-1,m-1) - (n-1)*s(n-1,m) </tex> şi <tex> S(n,m) = S(n-1,m-1) + m*S(n-1,m) </tex>.

4864