Problema permutare
autor prof. Szabo Zoltan, Liceul Tehnologic "Petru Maior" Reghin

Pentru simplitate "permutarea dubla de trei ori n crestere" o vom numi "permutare".
Prin definitia permutarii observam ca pentru fiecare element din a doua secventa, exista un element corespunzator din prima secventa cu valoare mai mica. 
Astfel daca pentru fiecare permutare construim un sir de caractere in care pe pozitiile indicate de elementele primei secvente punem caracterul '(' iar pentru pozitiile indicate de elementele celei de a doua secvente punem caracterul ')', obtinem o parantezare formata din n perechi de paranteze.

Ordinea lexicografica a tuturor parantezarilor coincide cu cea a permutarilor.

Problema se poate rezolva cu programare dinamica bazata pe formula de recurenta 
     P(i,j)=P(i-1,j)+P(i,j-1)

Reconstruirea solutiei porneste de la linia n catre linia 1 in matricea triunghiulara P.

Complexitatea unei cautari este O(n^2).