Una fórmula de autoconvolución que cuenta las expresiones de corchetes

Question

El problema: Considere un alfabeto de tamaño $m+2$ que consiste en los dos símbolos de corchetes $\ [ \ ] \ $ más $m$ símbolos sin corchetes ( $m \ge 0$ ). Definir $f_m(n)$ para ser el número de longitudes $n$ en este alfabeto, en el que los paréntesis sólo pueden aparecer en la forma habitual "equilibrada" de paréntesis posiblemente anidados. Queremos una fórmula para $f_m(n)$ .

¿Cómo se demuestra la siguiente fórmula? (¿Hay alguna derivación combinatoria?)

Conjetura : Si $m,n$ son enteros no negativos, entonces $f_m(n) = a(n+2)$ , donde $a()$ es la secuencia definida por la siguiente recursión:

$$\begin{array}{lcl} a(1) & = & m/2 \\ a(2) & = & 1 \\ a(i) & = & a(1)a(i-1) + a(2)a(i-2) + \cdots + a(i-1)a(1), \ \ \ i \ge 3 \end{array}$$

(El $a(i)$ se debe escribir $a_m(i)$ para demostrar que dependen de $m$ pero se suprime para simplificar).

En otras palabras, para cada $m$ la secuencia infinita $(f_m(0), \ f_m(1) , \ f_m(2), \ \dots)$ se genera empezando por el segmento inicial $(m/2, \ f_m(0))$ en una secuencia auxiliar, calculando luego cada elemento adicional como la autoconvolución de su prefijo.

Ejemplo : $f_1(4) = 9$ . Hay 9 cadenas admisibles de longitud 4 en un alfabeto con 1 símbolo que no es corchete (digamos $x$ ); a saber, $\ xxxx, \ xx[], \ x[x], \ [xx], \ x[]x, \ [x]x, \ []xx, \ [[]], \ [][]$ . La fórmula da
$f_1(4) = a(4+2) = 9$ en la secuencia que comienza con ( $1/2, 1$ ):

$$\begin{array}{lcl} 1/2 \\ 1 \\ (1/2)(1)+(1)(1/2)=1 \\ (1/2)(1)+(1)(1)+(1)(1/2)=2 \\ (1/2)(2)+(1)(1)+(1)(1)+(2)(1/2)=4 \\ (1/2)(4)+(1)(2)+(1)(1)+(2)(1)+(4)(1/2)=9 \end{array}$$

Motivación : En ciertos lenguajes informáticos primitivos (por ejemplo, P'' y su brainfuck variaciones), los programas son justo el tipo de cadenas que estamos considerando, y quería contar la longitud- n programas. (Para P'', hay $m = 3$ símbolos que no son corchetes, y para la descerebración $m = 6$ .) Aquí hay una tabla de algunos $f_m(n)$ valores calculados por enumeración de fuerza bruta:

Some f_m(n) values computed by enumeration

m   OEIS     n = 0  1   2    3     4     5      6       7       8        9     10
--  -------  --------------------------------------------------------------------
0   A126120      1  0   1    0     2     0      5       0      14        0     42
1   A001006      1  1   2    4     9    21     51     127     323      835   2188
2   A000108      1  2   5   14    42   132    429    1430    4862    16796  58786
3   A002212      1  3  10   36   137   543   2219    9285   39587   171369
4   A005572      1  4  17   76   354  1704   8421   42508  218318
5   A182401      1  5  26  140   777  4425  25755  152675
6   A025230      1  6  37  234  1514  9996  67181  458562

Cada fila de esta tabla corresponde a una secuencia que se encuentra en OEIS pero no he encontrado ninguna referencia que conecte todos ellos con un único problema combinatorio (por ejemplo, nuestro problema de recuento de "cadenas de corchetes") ni que los genere todos a partir de una única fórmula paramétrica (por ejemplo, nuestra conjetura).

A parte : Puede parecer peculiar que la fórmula utilice medios enteros para generar entero secuencias (para impar $m$ ). Creo que esto forma parte de un patrón general en el que un segmento inicial de algún número de racionales puede utilizarse para parametrizar una familia de secuencias racionales generadas a partir del segmento inicial por autoconvolución. Si el segmento inicial es un semi-integro seguido de algunos enteros, el resultado será siempre una secuencia de enteros.

Answer 1

Su fórmula es correcta, pero quizás no expresada de la manera más esclarecedora. Escríbala en su lugar como $\displaystyle f_m(n) = mf_m(n-1) + \sum_{k=0}^{n-2} f_m(k)f_m(n-2-k)$ . El primer término corresponde a las cadenas que comienzan con un carácter no corchete. En caso contrario, el primer carácter es un corchete izquierdo, seguido de algún número de caracteres (una cadena de este tipo de cierta longitud $k$ ) seguido de un corchete derecho, seguido de una cadena de este tipo de longitud $n-2-k$ para una longitud total de $n$ . (Esta es la misma idea que en la prueba de la recurrencia catalana).

Como alternativa, se tiene $\displaystyle f_m(n) = \sum_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{2k}m^{n-2k}C_k$ , donde $C_k$ son los números catalanes.