Repetición para lenceria perfecta revisitada.

Question

Me gusta el estudio de la combinatoria, un poco como un hobby, y recientemente una pregunta que me pareció interesante fue que plantea pedir a derivar una recurrencia para la generación de la función $G_n(x)$, el ordinario de generación de función para una perfecta elecciones en el set $[2n]=\{1,2,\dots,2n\}$, donde el coeficiente de $x^s$ es el número de $s$ de los bordes cortos. Un borde corto es un borde con forma de $\{i,i+1\}$.

La recurrencia fue de $$ G_n(x)=(x+2n-2)G_{n-1}(x)+(1-x)\frac{d}{dx}G_{n-1}(x). $$

¿Por qué es?

---

He reorganizado como este $$ G_n(x)=xG_{n-1}(x)+(2n-2)G_{n-1}(x)+\frac{d}{dx}G_{n-1}(x)-x\frac{d}{dx}G_{n-1}(x). $$ Atendiendo a los distintos coeficientes de los sumandos, veo que:

• El coeficiente de $x^s$ $G_n(x)$ es el número perfecto de matchings en $[2n]$ $s$ bordes cortos.

• El coeficiente de $x^s$ $xG_{n-1}(x)$ es el número perfecto de matchings en $[2n-2]$ $s-1$ bordes cortos.

• El coeficiente de $x^s$ $(2n-2)G_{n-1}(x)$ $2n-2$ multiplicado por el número de perfecto elecciones en $[2n-2]$ $s$ bordes cortos.

• El coeficiente de $x^s$ $\frac{d}{dx}G_{n-1}(x)$ $s+1$ multiplicado por el número de perfecto elecciones en $[2n-2]$ $s+1$ bordes cortos.

• El coeficiente de $x^s$ $x\frac{d}{dx}G_{n-1}(x)$ $s$ multiplicado por el número de perfecto elecciones en $[2n-2]$ $s$ bordes cortos.

Denotando estas cantidades como $A$, $B$, $C$, $D$, y $E$, respectivamente, debe ser que $A=B+C+D-E$. ¿Hay alguna forma inteligente de mostrar que las cuatro posibilidades en el lado derecho de contar todas las posibilidades? Creo que esto demostraría que la identidad es verdadera. Gracias.

Con Michael Lugo sugerencia, es probable que sea mejor considerar $A+E=B+C+D$. Así que estoy tratando de determinar por qué $$ (2n,s)+s(2n-2,s)=(2n-2,s-1)+(2n-2)(2n-2,s)+(s+1)(2n-2,s+1) $$ donde $(x,y)$ representa el número de perfecto elecciones en $x$ $y$ bordes cortos.

Answer 1

La manera de ver esto es buscar en el borde que contiene $2n$. Revisión de una coincidencia en $\{1,\ldots,2n\}$ contiene $s$ bordes cortos, y deje $2n$ estar emparejado con el vértice $j\in\{1,\ldots,2n-1\}$. Entonces tenemos las siguientes posibilidades:

(a) $j=2n-1$. Después de quitar el borde de la $\{2n-1,2n\}$, nos quedamos con un juego en $\{1,\ldots,2n-2\}$ $s-1$ bordes cortos.

(b) $j\in\{2,\ldots,2n-2\}$, e $\{j-1,j+1\}$ es una ventaja. En este caso, si el borde de la $\{j,2n\}$ es eliminado y los vértices $j+1$, $\ldots$, $2n-1$ se renumeran como $j$, $\ldots$, $2n-2$, el borde de la $\{j-1,j+1\}$ se convertirá en el borde corto de la $\{j-1,j\}$, por lo que tendremos una coincidencia en $\{1,\ldots,2n-2\}$ $s+1$ bordes cortos.

(c) Los restantes posibilidad es que cualquiera de las $j=1$ o, aunque $j\in\{2,\ldots,2n-2\}$, $\{j-1,j+1\}$ no es un borde. En este caso, si quitamos $\{j,2n\}$ y volver a numerar los vértices $j+1$, $\ldots$, $2n-1$ como en (b), el número de bordes cortos no va a aumentar, por lo que tendremos una coincidencia en $\{1,\ldots,2n-2\}$ $s$ bordes cortos.

Esta construcción da un bijection entre los matchings en $\{1,\ldots,2n\}$ y los pares que consiste en un $j$ $\{1,\ldots,2n-1\}$ y un juego en $\{1,\ldots,2n-2\}$. También, dada la coincidencia en $\{1,\ldots,2n-2\}$ $s+1$ bordes cortos, no se $s+1$ formas de seleccionar un $j$, como en (b), ya que podemos colocar $j$ en el centro de cada borde corto. Del mismo modo, dada una coincidencia en $\{1,\ldots,2n-2\}$ $s$ bordes cortos, hay $2n-2-s$ formas de seleccionar un $j$, como en (c), ya que de las $2n-2$ opciones posibles en $\{1,\ldots,2n-2\}$, sólo el $j$s de que iba a caer en el medio de la $s$ bordes cortos que se hayan descartado. Por lo tanto, si $(x,y)$ es el número perfecto de matchings en $\{1,\ldots,x\}$ $y$ bordes cortos,

$$(2n,s)=(2n-2,s-1)+(s+1)(2n-2,s+1)+(2n-s-2)(2n-2,s),$$

como se desee.