Secvența corectă a parantezei

Secvența corectă de paranteze ( PRS ) este o secvență de caractere compusă într-un alfabet format din caractere grupate în perechi ordonate (tipuri de paranteze, notate grafic cu „(” și „)”, „[” și „]”, „/*” și „ */”, etc.) care îndeplinește anumite reguli care asigură imbricarea secvențială a subsecvențelor închise de paranteze deschise și închise de același tip.

Secvențele regulate de paranteze formează limbajul Dyck și sunt definite formal după cum urmează:

șirul gol este o secvență de paranteze validă;
o secvență de paranteze obișnuită luată între paranteze de același tip este o secvență de paranteze obișnuită;
o secvență de paranteze obișnuită la care se adaugă o secvență de paranteze obișnuită la stânga sau la dreapta este, de asemenea, o secvență de paranteze obișnuită.

Numărul de secvențe corecte de paranteze

Numărul de secvențe corecte de paranteze din paranteze ( deschidere și închidere) de același tip este egal cu numărul catalan , care poate fi derivat în mai multe moduri: $2n$ $n$ $n$ $C_{n}$

Relatie recurenta :

C_{0}=1

iar pentru

\qquad C_{n}=\sum _{{i=0}}^{{n-1}}C_{i}C_{{n-1-i}}

n\geq 1.

Această relație poate fi obținută cu ușurință notând că orice secvență de paranteze regulată nevidă este reprezentabilă în mod unic sub forma , unde sunt secvențe de paranteze regulate. $\omega$ $\omega =(\omega _{{1}})\omega _{{2}}$ $\omega _{{1,2}}$

Exprimarea în termeni de coeficienți binomi :

C_{n}={\frac {1}{n+1}}{2n \alege n}={\frac {(2n)!}{n!(n+1)!}}={2n \alege n }-{2n\alegeți n-1}.

O altă relație recursivă:

R(o,n)={\begin{cases}1,&o=0\,\,{\mbox{și))\,\,n=0;\\0,&n=0\,\,{\ mbox{or}}\,\,o>n\,\,{\mbox{or}}\,\,o<0;\\R(o+1,n-1)+R(o-1, n-1),&{\mbox{altfel}}.\\\end{cazuri}}

în care $C_{n}=R(0,2n).$

Este ușor de arătat că, dacă există tipuri de paranteze într-o secvență de paranteze, atunci numărul de secvențe de paranteze corecte posibile cu paranteze de deschidere este egal cu produsul lui . Într-adevăr, pentru fiecare suport de deschidere din există diferite opțiuni pentru a-l alege. Alegerea unei console de închidere este determinată în mod unic de perechea deja aleasă de paranteze de deschidere și nu este luată în considerare. $k$ $n$ $C_{n}$ $k^{n}$ $n$ $k$

Generarea de secvențe corecte de paranteze

Să introducem acum ordinea lexicografică pe secvențele paranteze. În primul rând, rețineți că bretele de deschidere vine înaintea bretele de închidere; deoarece succesiunea parantezei care începe cu paranteza de închidere nu este corectă. Acum fiecăruia dintre tipurile de paranteze i se va atribui propria sa prioritate lexicografică. Alegerea acestei priorități nu este fundamentală și nu va afecta nimic în cursul raționamentelor ulterioare. Prin urmare, vom presupune că tipul i - lea de paranteze se află în poziția i - a în ordinea lexicografică. Evident, prima secvență cu paranteze de deschidere va fi o secvență de forma . $k$ $n$ $(_{1}(_{1}...(_{1})_{1})_{1}...)_{1}$