Rätt parentessekvens

Den korrekta parentessekvensen ( PRS ) är en teckensekvens sammansatt i ett alfabet som består av tecken grupperade i ordnade par (typer av parenteser, grafiskt betecknade med "(" och ")", "[" och "]", "/*" och " */", etc.) som uppfyller vissa regler som säkerställer sekventiell kapsling av subsekvenser omgivna av öppna och slutna parenteser av samma typ.

Regelbundna parentessekvenser bildar Dyck-språket och definieras formellt enligt följande:

den tomma strängen är en giltig parentessekvens;
en vanlig parentessekvens tagen inom parentes av samma typ är en vanlig parentessekvens;
en vanlig parentessekvens till vilken en vanlig parentessekvens läggs till till vänster eller höger är också en vanlig parentessekvens.

Antal korrekta parentessekvenser

Antalet korrekta parentessekvenser från parenteser ( öppning och stängning) av samma typ är lika med det katalanska talet , som kan härledas på flera sätt: $2n$ $n$ $n$ $C_{n}$

Återkommande relation :

C_{0}=1

och för

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

n\geq 1.

Denna relation kan enkelt erhållas genom att notera att alla icke-tomma regelbundna hakparentessekvenser är unikt representerade i formen , där är vanliga hakparentessekvenser. $\omega$ $\omega =(\omega _{{1}})\omega _{{2}}$ $\omega _{{1,2}}$

Uttryck i termer av binomialkoefficienter :

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{n!(n+1)!}}={2n \choose n }-{2n\välj n-1}.

En annan rekursiv relation:

R(o,n)={\begin{fall}1,&o=0\,\,{\mbox{och))\,\,n=0;\\0,&n=0\,\,{\ mbox{eller}}\,\,o>n\,\,{\mbox{eller}}\,\,o<0;\\R(o+1,n-1)+R(o-1, n-1),&{\mbox{annars}}.\\\end{cases}}

Vart i $C_{n}=R(0,2n).$

Det är lätt att visa att om det finns typer av parenteser i en parentessekvens, så är antalet möjliga korrekta parentessekvenser med öppnande parentes lika med produkten av . För varje öppningsfäste finns det faktiskt olika alternativ för att välja det. Valet av ett stängningsfäste bestäms unikt av det redan valda paret av öppningsfästen och tas inte med i beräkningen. $k$ $n$ $C_{n}$ $k^{n}$ $n$ $k$

Generering av korrekta parentessekvenser

Låt oss nu introducera den lexikografiska ordningen på parentessekvenser. Först av allt, notera att öppningsstaget kommer före stängningsstaget; eftersom parentessekvensen som börjar med den avslutande parentesen inte är korrekt. Nu kommer var och en av typerna av parenteser att tilldelas sin egen lexikografiska prioritet. Valet av denna prioritet är inte grundläggande och kommer inte att påverka någonting i samband med ytterligare resonemang. Därför kommer vi att anta att den i - e typen av parenteser är i den i - e positionen i den lexikografiska ordningen. Uppenbarligen kommer den första sekvensen med öppnande parenteser att vara en sekvens av formen . $k$ $n$ $(_{1}(_{1}...(_{1})_{1})_{1}...)_{1}$