Secuencia de paréntesis correcta

La secuencia correcta de corchetes ( PRS ) es una secuencia de caracteres compuesta en un alfabeto que consta de caracteres agrupados en pares ordenados (tipos de corchetes, denotados gráficamente por "(" y ")", "[" y "]", "/*" y " */”, etc.) que cumple ciertas reglas que aseguran el anidamiento secuencial de subsecuencias encerradas entre paréntesis abiertos y cerrados del mismo tipo.

Las secuencias de corchetes regulares forman el lenguaje de Dyck y se definen formalmente de la siguiente manera:

la cadena vacía es una secuencia de paréntesis válida;
una secuencia de paréntesis regular tomada entre paréntesis del mismo tipo es una secuencia de paréntesis regular;
una secuencia regular de corchetes a la que se agrega una secuencia regular de corchetes a la izquierda oa la derecha también es una secuencia regular de corchetes.

Número de secuencias de paréntesis correctas

El número de secuencias de paréntesis correctas a partir de paréntesis ( apertura y cierre) del mismo tipo es igual al número catalán , que se puede derivar de varias formas: $2n$ $norte$ $norte$ $C_{n}$

Relación recurrente :

{\ estilo de visualización C_ {0} = 1}

y para

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

{\ estilo de visualización n \ geq 1.}

Esta relación se puede obtener fácilmente observando que cualquier secuencia de paréntesis regular que no esté vacía se puede representar de forma única en la forma , donde son secuencias de paréntesis regulares. $\omega$ $\omega =(\omega_{{1}})\omega_{{2}}$ $\omega _{{1,2}}$

Expresión en términos de coeficientes binomiales :

C_{n}={\frac {1}{n+1}}{2n \elegir n}={\frac {(2n)!}{n!(n+1)!}}={2n \elegir n }-{2n\elegir n-1}.

Otra relación recursiva:

R(o,n)={\begin{casos}1,&o=0\,\,{\mbox{y))\,\,n=0;\\0,&n=0\,\,{\ mbox{o}}\,\,o>n\,\,{\mbox{o}}\,\,o<0;\\R(o+1,n-1)+R(o-1, n-1),&{\mbox{de lo contrario}}.\\\end{casos}}

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

Es fácil demostrar que si hay tipos de corchetes en una secuencia de corchetes, entonces el número de posibles secuencias correctas de corchetes con corchetes de apertura es igual al producto de . De hecho, para cada soporte de apertura hay diferentes opciones para elegirlo. La elección de un paréntesis de cierre está determinada únicamente por el par de paréntesis de apertura ya elegido y no se tiene en cuenta. $k$ $norte$ $C_{n}$ $k^{n}$ $norte$ $k$

Generación de secuencias de paréntesis correctas

Introduzcamos ahora el orden lexicográfico en las secuencias de paréntesis. En primer lugar, tenga en cuenta que la llave de apertura viene antes que la llave de cierre; porque la secuencia de corchetes que comienza con el corchete de cierre no es correcta. Ahora a cada uno de los tipos de corchetes se le asignará su propia prioridad lexicográfica. La elección de esta prioridad no es fundamental y no afectará nada en el curso del razonamiento posterior. Por lo tanto, supondremos que el i - ésimo tipo de paréntesis se encuentra en la i - ésima posición en el orden lexicográfico. Obviamente, la primera secuencia con paréntesis de apertura será una secuencia de la forma . $k$ $norte$ $(_{1}(_{1}...(_{1})_{1})_{1}...)_{1}$