Del problema a las funciones generadoras

Question

Estoy tratando de entender cómo puedo derivar una función generadora para el siguiente problema:

Dados son $2n$ puntos $\{1, ... ,2n \}$ dispuestos en una línea. Ahora cada punto se conecta exactamente con otro punto mediante un arco. Pero la disposición de los arcos necesita estar conectada, esto significa que cada dos arcos pueden estar conectados por una cadena de arcos cruzados, donde dos arcos $\{a,b\}$ y $\{c,d\}$ cruzar si $a<c<b<d$ . El objetivo es contar $c_n$ es decir, el número de formas de organizar $n$ arcos conectados entre $2n$ puntos.

Aquí está el argumento de cómo llegar a una función generadora:

Para poder meter la mano en él se quita el arco $\{1,a\}$ . Por lo tanto, el arreglo cae en $k$ componentes conectados no vacíos $X_1, ... , X_k$ , donde $X_i$ consiste en $n_i$ muchos arcos. Además, todos los $X_1, ... , X_k$ están anidados, lo que significa que $X_{i+1}$ se encuentra en uno de los $2n_i-1$ muchos espacios entre elementos consecutivos de $X_i$ . Además, $a$ se encuentra en uno de los $2n_k-1$ elementos consecutivos de $X_k$ .

La parte mencionada anteriormente es absolutamente clara para mí.

Pero lo que no entiendo es por qué es tan fácil concluir ahora que la función generadora $A$ pour $c_n$ sigue la ecuación $A= x\sum_{k \geq 0} (2xA'-A)^k$ .

Puedo ver alguna semejanza pero estoy lejos de entender cómo derivar esta ecuación para $A$ .

Answer 1

[La secuencia $c_n$ es el número A000699 en la OEIS. Véase también Flajolet y Noy, Combinatoria analítica de los diagramas de cuerda (Informe de investigación del INRIA nº 3914), $\S1$ , p. 2, y la pregunta anterior De las funciones generadoras a la recurrencia en esta secuencia].

Dejemos que $I_n:=\{1,\ldots,2n\}$ . Supongamos que, en un arreglo conectado de arcos en $I_n$ marcamos uno de los segmentos $[i,i+1]$ , donde $i\in\{1,\ldots,2n-1\}$ . Llame al número de arreglos marcados $d_n$ ; obviamente $d_n=(2n-1)c_n$ . Sea $B:=\sum_{n>0} d_n x^n$ sea la función generadora de $d_n$ .

Por el argumento que das arriba, dado un arreglo conectado de arcos en $I_n$ después de eliminar $\{1,a\}$ obtenemos una secuencia de arreglos conectados de arcos en subconjuntos de $I_n$ y si renumeramos los vértices de cada disposición conservando el orden, obtenemos una secuencia $X_1$ , $\ldots$ , $X_k$ de arreglos conectados de arcos en $I_{n_1}$ , $\ldots$ , $I_{n_k}$ , donde $n_1+\cdots+n_k=n-1$ . Como la secuencia con la que empezamos está anidada, para $i=1$ , $\ldots$ , $k-1$ podemos marcar el segmento en cada $I_{n_i}$ que, en la disposición original, se ampliaría para contener $X_{i+1}$ ; en el caso $i=k$ marque el segmento que se expande para contener $a$ . Esto da una secuencia $X'_1$ , $\ldots$ , $X'_k$ de arreglos conectados marcados de arcos en $I_{n_1}$ , $\ldots$ , $I_{n_k}$ a partir de la cual el arreglo conectado original de arcos en $I_n$ se puede recuperar. Por lo tanto, existe una correspondencia biyectiva entre

• arreglos conectados de arcos en $I_n$

y

• secuencias de arreglos conectados marcados de arcos en $I_{n_1}$ , $\ldots$ , $I_{n_k}$ , donde $n_1+\cdots+n_k=n-1$ . ( $k$ puede ser cero, en cuyo caso la secuencia está vacía).

Así que, $$ c_n=\sum_{k\ge 0} \sum_{n_1+\cdots+n_k=n-1} d_{n_1}\cdots d_{n_k}.\qquad (1) $$ Para convertir (1) en una igualdad de funciones generadoras, multiplique cada lado de (1) por $x^n$ y sumar sobre $n$ . Haciendo esto en el lado izquierdo se obtiene $A$ la función generadora de $c_n$ . Si arreglamos algunos $k$ en el lado derecho y luego realizar la multiplicación y la suma, obtenemos $$ \sum_{n>0} \sum_{n_1+\cdots+n_k=n-1} d_{n_1}\cdots d_{n_k} x^{n} $$ $$ = \sum_{n>0} \sum_{n_1+\cdots+n_k=n-1} d_{n_1}\cdots d_{n_k} x^{n_1+\cdots+n_k+1} $$ $$ = x \sum_{n_1,\ldots,n_k} d_{n_1}\cdots d_{n_k} x^{n_1+\cdots+n_k}, $$ que es igual a $$ x B^k. $$ Por lo tanto, reinsertando la suma sobre $k$ da $$ A=x \sum_{k\ge 0} B^k.\qquad (2) $$ Pero, como $$ A=\sum_{n>0} c_n x^n $$ y $$2xA^\prime = \sum_{n>0} 2nc_n x^n$$ tenemos $$2xA^\prime-A = \sum_{n>0} (2n-1)c_nx^n = \sum_{n>0} d_n x^n=B.\qquad (3)$$ Combinando (2) y (3) se obtiene $$ A=x \sum_{k\ge 0} (2xA'-A)^k, $$ como se desee.