h2(#lkperm). 'Lkperm':problema/lkperm

h2(#lkperm). 'Lkperm':problema/lkperm
 
Fie <tex>f(n)</tex> numărul total de permutări de $n$ elemente care respectă proprietatea din enunţ. În momentul în care dorim să calculăm <tex>f(n)</tex>, vom încerca să plasăm elementul maxim, adică pe $n$. Dacă el este plasat pe prima poziţie a permutării, atunci ea va arăta aşa:
$n x{~1~} x{~2~} x{~3~} ... x{~n-1~}$
Elementul $n$ va fi maximul doar pentru secvenţa $n x{~1~} x{~2~} ... x{~L-1~}$. Aşadar, în acest caz sunt <tex>f(n-1)</tex> posibilităţi.
 
Dacă plasăm elementul $n$ pe cea de-a doua poziţie, permutarea va arăta aşa:
$x{~1~} n x{~2~} x{~3~} ... x{~n-1~}$
Elementul $n$ va fi maximul pentru două secvenţe, iar x{~1~} poate lua orice valoare între $1$ şi $n-1$, deoarece el nu poate fi maximul în nicio secvenţa. Aşadar, există <tex>(n-1)*f(n-2)</tex> posibilităţi.
 
Dacă plasăm elementul $n$ pe cea de-a $p$-a poziţie, $1 &le; p &le; K$ permutarea va arăta astfel:
$x{~1~} x{~2~} x{~3~} ... x{~p-1~} n x{~p+1~} x{~p+2~} ... x{~n-1~}$
Elementul $n$ va fi maximul pentru $p$ secvenţe, iar primele $p-1$ elemente nu vor fi maxime în nicio secvenţă. Prin urmare vor fi <tex>(n-1)*(n-2)*(n-3)*...*(n-P-1)*f(n-P)</tex> posibilităţi
 
Aşadar, <tex>f(n)=f(n-1)+(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)</tex><tex>+...+(n-1)*(n-2)*...*(n-K+1)*f(n-K)</tex>, dacă <tex>n>L</tex>
<tex>f(n)=n!</tex>, altfel
Implementarea directă a acestei formule aduce $40$ de puncte, deoarece are complexitatea $O(N*K)$. Pentru $100$ de puncte vom încerca să restrângem egalitatea şi observăm că
<tex>f(n-1)=f(n-2)+(n-2)*f(n-3)+...+(n-2)*(n-3)*...*(n-K)*f(n-K-1)</tex>
Deci <tex>f(n)=f(n-2)+(n-2)*f(n-3)+...+(n-2)*(n-3)*...*(n-K)*f(n-K-1)+</tex><tex>+(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)+...+(n-1)*(n-2)*...*(n-K+1)*f(n-K)</tex>
<tex>f(n)=n*f(n-2)+n*(n-2)*f(n-3)+...+n*(n-2)*(n-3)*...*(n-K+1)*f(n-K)</tex><tex>+(n-2)*(n-3)*...*(n-K)*</tex><tex>f(n-K-1)</tex>
<tex>f(n)=n*f(n-1)-(n-1)*(n-2)*...*(n-K)*f(n-K-1)</tex>