Lkperm
Fie numărul total de permutări de n elemente care respectă proprietatea din enunţ. În momentul în care dorim să calculăm , 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 x1 x2 x3 ... xn-1
Elementul n va fi maximul doar pentru secvenţa n x1 x2 ... xL-1. Aşadar, în acest caz sunt posibilităţi.
Dacă plasăm elementul n pe cea de-a doua poziţie, permutarea va arăta aşa:
x1 n x2 x3 ... xn-1
Elementul n va fi maximul pentru două secvenţe, iar x1 poate lua orice valoare între 1 şi n-1, deoarece el nu poate fi maximul în nicio secvenţa. Aşadar, există posibilităţi.
Dacă plasăm elementul n pe cea de-a p-a poziţie, 1 ≤ p ≤ K permutarea va arăta astfel:
x1 x2 x3 ... xp-1 n xp+1 xp+2 ... xn-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 posibilităţi
Aşadar, , dacă
, 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ă
Deci