Empezamos calculando las correspondientes funciones de generación. Tomando un
cadena binaria o cadena de paréntesis ampliamos todo bien equilibrada
subsecuencias a ser máxima. Esto deja de llenado adicional que tiene
la propiedad que no puede contener un abrir paréntesis seguido por un
el cierre de uno. Que parametrizar el relleno de la variable $q$
que indica su longitud, de modo que no se $q+1$ admisible rellenos de
la longitud de la $q$ $q+1$ lugares para la inserción de un bien equilibrada
no palabra vacía. Además, hemos catalana de generación de números
la función
$$C(z) = \frac{1-\sqrt{1-4z}}{2z}.$$
La inserción en el relleno nos encontramos con la mezcla de OGF de binario palabras con
pares de bien equilibrada entre paréntesis marcado que es variable ( $z$
la longitud de la palabra y $u$ para los pares de paréntesis)
$$\sum_{q\ge 0} (q+1) z^q
\sum_{p=0}^{p+1} {p+1\elegir p} (C(uz^2)-1)^p
\\ = \sum_{q\ge 0} (q+1) z^q C(uz^2)^{q+1}
= \frac{C(uz^2)}{(1-zC(uz^2))^2}.$$
En esta interpretación del problema que tenemos que abrir un paréntesis
emparejado con un cerrado uno con una secuencia entre ellos que no es
bien equilibrado, no cuentan. El coeficiente binomial indica el
la elección de las ranuras en el relleno donde no vacía bien equilibrada palabra es
coloca. Este paso puede ser omitido si se admite el vacío equilibrada
palabra en cuyo caso se procederá a la línea siguiente.
Ahora para extraer los coeficientes de esto podemos recordar el funcional
ecuación de $C(z)$ que es
$$C(z) = 1 + z C(z)^2
\quad\text{o}\quad
z = \frac{C(z)-1}{C(z)^2}.$$
Hacemos el coeficiente de $[u^k]$ ($k$ pares de paréntesis) y
ver $C(uz^2)$ como una función de la $u$ que los rendimientos de
$$u = \frac{1}{z^2} \frac{C(uz^2)-1}{C(uz^2)^2}.$$
El coeficiente de extractor de aquí es
$$[u^k] \frac{C(uz^2)}{(1-zC(uz^2))^2} =
\frac{1}{2\pi i} \int_{|u|=\epsilon}
\frac{1}{u^{k+1}} \frac{C(uz^2)}{(1-zC(uz^2))^2}
\; du.$$
Dejamos $w=C(uz^2)$, de modo que $u=(w-1)/w^2/z^2$ y
$$du = \frac{1}{z^2}
\left(\frac{1}{w^2} - 2\frac{w-1}{w} {^3}\right) \; dw
= \frac{1}{z^2} \frac{2-w}{w} {^3} \; dw$$
que los rendimientos de la integral
$$\frac{1}{2\pi i} \int_{|w-1|=\gamma}
z^{2k+2} \frac{w^{2k+2}}{(w-1)^{k+1}}
\frac{w}{(1-zw)^2} \frac{1}{z^2} \frac{2-w}{w} {^3} \; dw
\\ = \frac{z^{2k}}{2\pi i} \int_{|w-1|=\gamma}
\frac{w^{2k}}{(w-1)^{k+1}}
\frac{1}{(1-zw)^2} (2-w) \; ps.$$
Se obtienen dos piezas de aquí, que son
$$\frac{z^{2k}}{2\pi i} \int_{|w-1|=\gamma}
\frac{w^{2k}}{(w-1)^{k+1}}
\frac{1}{(1-zw)^2} \; dw$$
y
$$-\frac{z^{2k}}{2\pi i} \int_{|w-1|=\gamma}
\frac{w^{2k}}{(w-1)^{k}}
\frac{1}{(1-zw)^2} \; ps.$$
Obviamente, se requieren donde $p\le k$
$$\frac{1}{p!}
\left(w^{2k} \frac{1}{(1-zw)^2}\right)^{(p)}$$
Esto es por Leibniz
$$\frac{1}{p!}
\sum_{q=0}^p {p\elegir q} \frac{(2k)!}{(2k-p)!} w^{2k-p}
\frac{z^{p-q} (p-q+1)!}{(1-zw)^{p-q+2}}
\\ = \sum_{q=0}^p {2k\elegir q} w^{2k-p}
\frac{z^{p-q} (p-q+1)}{(1-zw)^{p-q+2}}.$$
Evaluar en $w=1$ para obtener
$$\sum_{q=0}^p {2k\elegir q}
\frac{z^{p-q} (p-q+1)}{(1-z)^{p-q+2}}.$$
La contribución de las dos integrales se convierte ahora en el
$${2k\elegir k} \frac{z^{2k}}{(1-z)^2}
+ z^{2k} \sum_{q=0}^{k-1} {2k\elegir q}
\left(\frac{z^{k-q} (k-q+1)}{(1-z)^{k-q+2}}
- \frac{z^{k-1-p} (k-q)}{(1-z)^{k-q+1}}\right)
\\ = {2k\elegir k} \frac{z^{2k}}{(1-z)^2}
\\ + z^{2k} \sum_{q=0}^{k-1} {2k\elegir q}
\left(\frac{z^{k-q} (k-q+1) - z^{k-1-p} (k-q)
+ z^{k-q} (k-q) }{(1-z)^{k-q+2}}\right)
\\ = {2k\elegir k} \frac{z^{2k}}{(1-z)^2}
\\ + z^{2k} \sum_{q=0}^{k-1} {2k\elegir q}
\left(\frac{z^{k-q} (2k-2t+1) - z^{k-1-p} (k-q) }
{(1-z)^{k-q+2}}\right)
\\ = z^{2k} \sum_{q=0}^{k} {2k\elegir q}
\frac{z^{k-q} (2k-2t+1) - z^{k-1-p} (k-q) }
{(1-z)^{k-q+2}}.$$
Haciendo el coeficiente de extracción en $[z^n]$ (word contiene $n$
paréntesis en total) se obtienen dos piezas, es decir,
$$\sum_{q=0}^{k} {2k\elegir q}
[z^{n-3k+q}] \frac{2k-2t+1}
{(1-z)^{k-q+2}}
\quad\text{y}\quad
-\sum_{q=0}^{k} {2k\elegir q}
[z^{n-3k+q+1}] \frac{k-q}
{(1-z)^{k-q+2}}$$
que producen
$$\sum_{q=0}^{k} {2k\elegir q}
(2k-2t+1)
{n-2k+1\elegir k-q+1}
\quad\text{y}\quad
-\sum_{q=0}^{k} {2k\elegir q}
(k-q)
{n-2k+2 \elegir k-q+1}.$$
Con el fin de unirse a estos podemos poner
$${n-2k+1 \elegir k-q+1} =
\frac{n-3k+q+1} {n-2k+2} {n-2k+2 \elegir k-q+1}$$
para obtener
$$\sum_{q=0}^{k} {2k\elegir q}
{n-2k+2\elegir k-q+1}
\frac{(k-q+1)(n+2t+1-4k)}{n-2k+2}$$
y llegar a la forma cerrada donde claramente $n\ge 2k:$
$$\bbox[5px,border:2px solid #00A000]{
\sum_{q=0}^{k} {2k\elegir q}
{n-2k+1\elegir k-q}
(n+2t+1-4k).}$$
Como una comprobación de validez de al $n=2k$ debemos obtener ordinario catalán
números. Obtenemos
$$\sum_{q=0}^{k} {2k\elegir q}
{1\elegir k-q}
(2t+1-2k)
= {2k\elegir k} - {2k\elegir k-1}
= \frac{1}{k+1} {2k\elegir k}$$
y el cheque pasa a través de. Hemos verificado todo lo anterior en madera de Arce
incluyendo una enumeración de rutina, que es sorprendentemente baratos eficaz incluso
en las cadenas de, digamos, $16$ paréntesis. Aquí está la generación de la función
para los pares de paréntesis entre $8$ paréntesis:
$$14\,{u}^{4}+84\,{u}^{3}+100\,{u}^{2}+49\,u+9$$
y aquí es por $10$ paréntesis:
$$42\,{u}^{5}+270\,{u}^{4}+375\,{u}^{3}+245\,{u}^{2}+81\,u+11.$$
Para $11$ paréntesis tenemos
$$264\,{u}^{5}+660\,{u}^{4}+660\,{u}^{3}+352\,{u}^{2}+100\,u+12.$$
El líder plazo no es un catalán de número de $n$ es impar. Este fue el
Arce código:
con(planta);
GATO := n -> 1/(n+1)*binomial(2*n,n);
CAT_PARS :=
proc(n)
opción de recordar;
local recurse, res;
res := [];
recurse :=
proc(hasta la fecha, oc, cc)
si oc = 0 y cc = 0, entonces
res := [op(res), hasta la fecha];
de retorno;
fi;
si oc > 0 entonces
recurse([op(hasta la fecha), `(`], oc-1, cc+1);
fi;
si cc > 0 entonces
recurse([op(hasta la fecha), `)`], oc, cc-1);
fi;
end;
recurse([], n, 0);
convertir(res,``);
end;
BALCOUNT :=
proc(parlist)
local posA, posB, intervA, intervB, len, subseq, conde,
res, n;
subseq := [];
n := nops(parlist);
para posA a n do
para posB de posA+1 hasta n hacer
intervA := parlist[posA..posB];
len := posB - posA + 1;
si el tipo(len, incluso) y
intervA en CAT_PARS(len/2), a continuación,
subseq := [op(subseq), [posA, posB]];
fi;
od;
od;
res := [];
subseq :=
sort(subseq,
(a, b) -> a[2]-[1] < b[2] b[1]);
count := nops(subseq);
para posA para contar ¿
intervA := subseq[ley];
para posB de posA+1 para contar ¿
intervB := subseq[posB];
si intervB[1] <= intervA[1] y
intervB[2] >= intervA[2]
break;
fi;
od;
si posB = count + 1
res := [op(res), intervA];
fi;
od;
agregar (iv[2] iv[1]+1)/2, iv en res);
end;
La GFP :=
proc(n)
opción de recordar;
local gf, idx, d, parlist;
gf := 0;
para idx de 2^n 2*2^n-1 hacer
d := convert(idx, base, 2);
parlist :=
subs([0=`(`, 1=`)`], d[1..n]);
gf := gf + u^BALCOUNT(parlist);
od;
gf;
end;
GFA :=
proc(n)
local C;
C := (1-sqrt(1-4*u*z^2))/(2*u*z^2);
coeftayl(C/(1-z*C)^2, z=0, n);
end;
GFB :=
n -> add(u^k*agregar(binomial(2*k,q)*binomial(n-2*k+1, k-p)
*(n+2*p+1-4*k), q=0..k), k=0..suelo(n/2));
GFC :=
n -> add(u^k*(n+1-2*k)^2/(n+1)*binomial(n+1,k),
k=0..suelo(n/2));
Adicional simplificación. La división de la suma en dos
las piezas que nos dan para la primera parte
$$(n+1-4k) \sum_{q=0}^{k} {2k\elegir q}
{n-2k+1\elegir k-q}
\\ = (n+1-4k) \sum_{q=0}^{k} {2k\elegir q}
[z^{k-q}] (1+z)^{n-2k+1}
\\ = (n+1-4k) [z^k] (1+z)^{n-2k+1}
\sum_{q=0}^{k} {2k\elegir q} z^q.$$
Ahora podemos extender $q$ más allá de la $k$ porque la suma plazo no
contribuir a que el coeficiente de extractor en ese caso, la obtención de
$$(n+1-4k) [z^k] (1+z)^{n-2k+1}
\sum_{q\ge 0} {2k\elegir q} z^q
\\ = (n+1-4k) [z^k] (1+z)^{n-2k+1} (1+z)^{2k}
= (n+1-4k) [z^k] (1+z)^{n+1}
= (n+1-4k) {n+1\elegir k}.$$
La segunda parte es
$$ 2\sum_{q=0}^{k} {2k\elegir q} q
{n-2k+1\elegir k-q}
= 2\sum_{q=1}^{k} {2k\elegir q} q
{n-2k+1\elegir k-q}
\\ = 4k\sum_{q=1}^{k} {2k-1\elegir q-1}
{n-2k+1\elegir k-q}
= 4k\sum_{q=0}^{k-1} {2k-1\elegir q}
{n-2k+1\elegir k-p-1}
\\ = 4k\sum_{q=0}^{k-1} {2k-1\elegir q}
[z^{k-1-p}] (1+z)^{n-2k+1}
\\ = 4k [z^{k-1}] (1+z)^{n-2k+1}
\sum_{q=0}^{k-1} {2k-1\elegir q} z^q
= 4k [z^{k-1}] (1+z)^{n-2k+1}
\sum_{q\ge 0} {2k-1\elegir q} z^q
\\ = 4k [z^{k-1}] (1+z)^{n-2k+1} (1+z)^{2k-1}
= 4k [z^{k-1}] (1+z)^{n}
= 4k {n\elegir k-1}
\\ = 4k {n+1\elegir k} \frac{k}{n+1}.$$
La adición de estas dos tenemos la segunda forma cerrada
$$\bbox[5px,border:2px solid #00A000]{
\frac{(n+1-2k)^2}{n+1} {n+1\elegir k}.}$$
Ahora es inmediato que se obtiene un catalán número al $n=2k$
desde
$$\frac{1}{2k+1} {2k+1\elegir k}
=\frac{1}{2k+1} {2k\elegir k} \frac{2k+1}{k+1}
= \frac{1}{k+1} {2k\elegir k}.$$
Hay que tener en cuenta aquí que aunque la forma cerrada se define
incluso para $2k\gt n$ debemos tener ese $2k\le n$ desde $k$ equilibrada
el paréntesis requieren al menos $2k$ personajes, con un equilibrado
el paréntesis que participan en exactamente un par. Observar que el cerrado
la forma es simétrica con respecto a $k\to n+1-k.$
El algoritmo para generar equilibrada palabras de paréntesis parece
han aparecido varias veces en stackexchange sitios, uno de referencia
es este enlace en stackoverflow
com.
