Vom calcula $P[i][j]$ = numarul de permutari ale multimii {$1$,$2$,..,$i$} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N][1]$ + $P[N][2]$ + .. + $P[N][N]$.
	Pentru calculul lui $P[i][j]$ vom observa ca, eliminand numarul $j$ din permutare, obtinem $i-1$ numere distincte care pot fi renumerotate pentru a forma o permutare a multimii {$1$,$2$,..,$i-1$}. Mai exact, orice numar $x$ mai mare decat $j$ este renumerotat cu valoarea $x-1$. In conditiile acestei renumerotari, avem urmatoarele $2$ cazuri:

* daca relatia $i-1$ este "$<$", atunci $P[i][j]$ = $P[i-1]{[1]}$ + $P[i-1][2]$ + .. + $P[i-1][j-1]$
* daca relatia $i-1$ este "$>$", atunci $P[i][j]$ = $P[i-1][j]$ + $P[i-1][j+1]$ + .. + $P[i-1][i-1]$

* daca relatia $i-1$ este "$<$", atunci $P[i, j]$ = $P[i-1, 1]$ + $P[i-1, 2]$ + .. + $P[i-1, j-1]$
* daca relatia $i-1$ este "$>$", atunci $P[i, j]$ = $P[i-1, j]$ + $P[i-1, j+1]$ + .. + $P[i-1, i-1]$

Cazul "de baza" este $P[1][1]$ = $1$. Relatiile date sunt corecte, deoarece pentru orice permutare ce corespunde lui $P[i-1][x]$ se poate aplica operatia de renumerotare inversa (relativ la $j$), obtinand un sir de $i-1$ numere distincte din multimea {$1$,$2$,..,$i$}\{$j$} care respecta primele $i-2$ relatii. La sfarsitul acestui sir se poate adauga numarul $j$, obtinand o permutare cu $i$ elemente care respecta primele $i-1$ relatii.
	Implementarea imediata a relatiilor de recurenta mentionate se poate realiza foarte usor in complexitate O($N^3^$). Memorand sumele partiale $SP[x]$ = $P[i-1][1]$ + $P[i-1][2]$ + .. + $P[i-1][x]$ putem calcula $P[i][j]$ in timp O($1$), reducand complexitatea la O($N^2^$).