Permutaciones que contienen una subsecuencia determinada

Question

Dejemos que $f(n)$ denotan el número de $4n$ -cuerdas largas formadas por $2n$ a's y $2n$ b's, de manera que la cadena contenga, como una subsecuencia (posiblemente no consecutiva), un patrón que contenga $n$ a's y $n$ b's. (Tenga en cuenta que $f(n)$ no depende del patrón, por lo que dos posibles patrones serían $$\overbrace{\strut a\cdots a}^{n\textrm{ times}}\, \overbrace{\strut b\cdots b}^{n\textrm{ times}}\quad\textrm{ or }\quad \overbrace{abab\cdots ab}^{n \textrm{ pairs}}.)$$

En la notación de este puesto este número es $\left[\begin{array}{c}2n,2n\\n,n\end{array}\right]$ .

Utilizando el primer patrón, y sumando el número de b's que aparecen antes del $n$ -a, encontramos que $$(*)\quad f(n)= \sum_{r=0}^n \binom{n+r-1}{r}\binom{3n-r}{n}.$$

La secuencia resultante es $$1, 5, 53, 662, 8885, 124130, 1778966, 25947612, 383358645, \ldots$$ que aparece en la OEIS como A036910 donde encontramos una buena forma cerrada para el $n$ -año: $$(**)\quad\frac12\left(\binom{4n}{2n}+\binom{2n}{n}^2\right).$$

La maquinaria del par WZ debería demostrar que $(*)$ y $(**)$ son iguales, así que eso no es una preocupación. Mi pregunta: ¿existe un argumento combinatorio directo que dé la cuenta $(**)$ directamente (es decir, no como resultado de la evaluación de una suma)?

La forma cerrada sugiere la fórmula del índice de ciclo para una involución, pero no veo una respuesta en ese sentido.

Answer 1

La maquinaria de WZ es muy potente, pero también es un incentivo para evaluar estas sumas manualmente, por ejemplo, utilizando el método de Egorychev, que espero que sea una lectura gratificante.

Supongamos que intentamos evaluar $$\sum_{r=0}^n {r+n-1\choose n-1} {3n-r\choose n}.$$

Poner $${3n-r\choose n} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n-r}}{w^{n+1}} \; dw$$

y además introducir $$[[0\le r \le n]] = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z+z^2+\cdots+z^n}{z^{r+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^{n+1}-1}{(z-1)z^{r+1}} \; dz.$$

Esta segunda integral controla el rango de manera que podemos extender la suma hasta el infinito para obtener $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^{n+1}-1}{(z-1)z} \sum_{r=0}^\infty {r+n-1\choose n-1} \frac{1}{z^r (1+w)^r} \; dz \; dw.$$

Esto se simplifica a $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^{n+1}-1}{(z-1)z} \frac{1}{(1-1/z/(1+w))^n} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^{n+1}-1}{(z-1)z} \frac{z^n}{(z-1/(1+w))^n} \; dz \; dw.$$

Calculando las contribuciones del polo en $z=1/(1+w)$ (no hay polo en el cero) obtenemos dos piezas, llámalas $A$ y $B$ , $A$ es $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{z^{n-1}}{(z-1/(1+w))^n} \; dz \; dw.$$

Tenemos $$\frac{1}{1-z} = \frac{1}{1-1/(w+1)-(z-1/(w+1))} = \frac{1}{w/(w+1)-(z-1/(w+1))} \\ = \frac{1}{w/(w+1)}\frac{1}{1-(z-1/(1+w))/(w/(w+1))} = \frac{w+1}{w}\frac{1}{1-(z-1/(1+w))(w+1)/w}.$$

Esto da para la integral interna de $A$ $$\frac{w+1}{w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \left(\sum_{q\ge 0} (z-1/(1+w))^q \frac{(w+1)^q}{w^q}\right) \\ \times \left(\sum_{p=0}^{n-1} {n-1\choose p} (z-1/(1+w))^p \frac{1}{(1+w)^{n-1-p}}\right) \frac{1}{(z-1/(1+w))^n} \; dz.$$

Calculando el residuo obtenemos $$\frac{w+1}{w} \sum_{p=0}^{n-1} {n-1\choose p} \frac{(1+w)^{n-1-p}}{w^{n-1-p}} \frac{1}{(1+w)^{n-1-p}} \\ = \frac{w+1}{w} \sum_{p=0}^{n-1} {n-1\choose p} \frac{1}{w^{n-1-p}} \\ = \frac{w+1}{w} \left(1+\frac{1}{w}\right)^{n-1} = \frac{(1+w)^{n}}{w^n}.$$

Sustituyendo esto en $A$ obtenemos $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{(1+w)^{n}}{w^n} \; dw = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{4n}}{w^{2n+1}} \; dw = {4n\choose 2n}.$$

Volviendo a $B$ que es $$-\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{z^{2n}}{(z-1/(1+w))^n} \; dz \; dw.$$

obtenemos para la integral interna $$\frac{w+1}{w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \left(\sum_{q\ge 0} (z-1/(1+w))^q \frac{(w+1)^q}{w^q}\right) \\ \times \left(\sum_{p=0}^{2n} {2n\choose p} (z-1/(1+w))^p \frac{1}{(1+w)^{2n-p}}\right) \frac{1}{(z-1/(1+w))^n} \; dz.$$

Calculando el residuo obtenemos $$\frac{w+1}{w} \sum_{p=0}^{n-1} {2n\choose p} \frac{(1+w)^{n-1-p}}{w^{n-1-p}} \frac{1}{(1+w)^{2n-p}} \\ = \frac{w+1}{w} \frac{1}{(1+w)^{n+1} \times w^{n-1}} \sum_{p=0}^{n-1} {2n\choose p} w^p \\ = \frac{1}{(1+w)^n w^n} \sum_{p=0}^{n-1} {2n\choose p} w^p.$$

Sustituyendo esto en $B$ obtenemos $$-\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{3n}}{w^{n+1}} \frac{1}{(1+w)^n w^n} \sum_{p=0}^{n-1} {2n\choose p} w^p \; dw \\ = - \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n}}{w^{2n+1}} \sum_{p=0}^{n-1} {2n\choose p} w^p \; dw.$$

Esto es $$-\sum_{p=0}^{n-1} {2n\choose p} {2n\choose 2n-p}.$$ Por simetría esto se evalúa como $$-\frac{1}{2}\left(-{2n\choose n}^2 + \sum_{p=0}^{2n} {2n\choose p} {2n\choose 2n-p}\right).$$

Esta última suma es $$ [x^{2n}] (1+x)^{2n} (1+x)^{2n} = [x^{2n}] (1+x)^{4n} = {4n\choose 2n}.$$

por lo que finalmente tenemos por pieza $B$ el valor $$-\frac{1}{2}\left(-{2n\choose n}^2 + {4n\choose 2n}\right).$$

Podemos concluir ahora, recogiendo las aportaciones de $A$ y $B$ a obtener

$${4n\choose 2n} -\frac{1}{2}\left(-{2n\choose n}^2 + {4n\choose 2n}\right) = \frac{1}{2} \left({4n\choose 2n} + {2n\choose n}^2\right).$$

Answer 2

A continuación consideramos sin pérdida de generalidad la cadena $a^nb^n$ de longitud $2n$ que es una abreviatura de \begin{align*} \overbrace{\strut a\cdots a}^{n\textrm{ times}}\, \overbrace{\strut b\cdots b}^{n\textrm{ times}} \end{align*}

Mostramos el número de cadenas de longitud $4n$ con $2n$ $a$ y $2n$ $b$ que contiene la subsecuencia (no necesariamente contigua) $a^nb^n$ es \begin{align*} \frac{1}{2}\left[\binom{4n}{2n}+\binom{2n}{n}^2\right] \tag{1} \end{align*}

El número de posibilidades a seleccionar $2n$ posiciones fuera de $4n$ para colocar la cadena $a^nb^n$ es \begin{align*} \binom{4n}{2n} \end{align*} El otro $2n$ posiciones pueden ser colocadas libremente por el otro $n$ a's y $n$ b's.

Primer paso: Para que cada cadena válida no se cuente más de una vez, tenemos que respetar las simetrías.

Por lo tanto, sólo contamos aquellos patrones fuera de la $\binom{4n}{2n}$ cadenas en las que colocamos no $b's$ en la mitad izquierda. En otras palabras, contamos aquellos patrones con menos o igual $n$ posiciones seleccionadas en la mitad izquierda.

Ya que tenemos $n$ $a$ y $n$ $b$ 's en reserva Siempre podemos cubrir las posiciones de la mitad izquierda con $b$ 's de la reserva en consecuencia, correspondiendo a los patrones fuera de la $\binom{4n}{2n}$ selecciones con $k>n$ posiciones en el lado izquierdo.

Esto lleva a casi a \begin{align*} \frac{1}{2}\binom{4n}{2n}\tag{2} \end{align*}

La fórmula (2) cuenta correctamente los casos con $0\leq k <n$ $a$ en la mitad izquierda, pero no es el caso de $k=n$ $a's$ .

Segundo paso: Tenemos además el caso especial con $k=n$ $a$ a tener en cuenta.

En todos los demás casos, siempre que consideremos $0\leq k<n$ $a$ en la mano izquierda, tenemos el colgante de $n$ $a$ y $n-k$ $b$ 's en la mano izquierda dando $\binom{2n}{k}=\binom{2n}{n-k}$ posibilidades. Pero, en caso de $k=n$ $a$ 's tenemos que contar cada ocurrencia con $n$ $a$ 's en el lado izquierdo sin cortarlos por la mitad. El número de todas las cadenas válidas con exactamente $n$ $a$ en el lado izquierdo y $n$ $b$ en el lado derecho es \begin{align*} \binom{2n}{n}^2 \end{align*} Como la mitad de estas posibilidades ya está contada por (2) tenemos que añadir la otra mitad $\frac{1}{2}\binom{2n}{n}^2$ y así vemos finalmente que la afirmación (1) es válida.

Nota: La interpretación combinatoria se basa en la identidad binomial \begin{align*} \sum_{k=0}^{2n}\binom{2n}{k}^2=\binom{4n}{2n} \end{align*} y la simetría \begin{align*} \binom{4n}{2n}&=\sum_{k=0}^{n-1}\binom{2n}{k}\binom{2n}{2n-k}+\binom{2n}{n}^2+\sum_{k=n+1}^{2n}\binom{2n}{k}\binom{2n}{2n-k}\\ &=2\sum_{k=0}^{n-1}\binom{2n}{k}^2+\binom{2n}{n}^2\\ \end{align*} de la cual \begin{align*} \sum_{k=0}^{n-1}\binom{2n}{k}^2&=\frac{1}{2}\left[\binom{4n}{2n}-\binom{2n}{n}^2\right]\\ \text{and}\\ \sum_{k=0}^{n}\binom{2n}{k}^2&=\frac{1}{2}\left[\binom{4n}{2n}+\binom{2n}{n}^2\right]\\ \end{align*} seguir.

Answer 3

Aquí hay un argumento de conteo directo. Sea $S$ sea el conjunto de permutaciones de la palabra $a^{2n}b^{2n}$ . Para cualquier palabra $w\in S$ y para cualquier patrón $p$ , escriba $w\vdash p$ para significar que $w$ contiene $p$ como una subsecuencia.

Set $A=\{w\in S\mid w\vdash a^nb^n\}$ y $B=\{w\in S\mid w\vdash b^n a^n\}=\{w\in S\mid \bar w\vdash a^n b^n\}$ Nota $$|A|=|B|=\left[\matrix{2n,2n\\n,n}\right].$$ La observación clave es que $A\cup B=S$ es decir, para cualquier $w\in S$ al menos uno de $\{w,\bar w\}$ contiene $a^n b^n$ como una subsecuencia. (Para ver esto, dejemos que $a_i$ y $b_i$ sea la posición del $i$ -a ocurrencia de $a$ y $b$ en $w$ respectivamente. Si $w\not\vdash a^nb^n$ , entonces hay como máximo $n-1$ $b$ 's después de la $n$ -a $a$ Así que $b_{n+1}<a_n$ Por lo tanto $w\vdash b^{n+1}a^{n+1}$ y en particular $\bar w\vdash a^nb^n$ .) Por lo tanto, $$2\left[\matrix{2n,2n\\n,n}\right]=|A|+|B|=|A\cup B|+|A\cap B|=|S|+|A\cap B|.$$ Afirmamos que $A\cap B$ consiste precisamente en las palabras en las que tanto la primera como la última mitad contienen exactamente $n$ $a$ y $n$ $b$ 's. (Para ver esto, observe que $w\in A\cap B$ si $b_{n+1}>a_n \textrm{ and } a_{n+1}>b_n$ Así que $b_{n+1}\ge 2n+1$ y $a_{n+1}\ge 2n+1$ . Esto implica que la segunda mitad de $w$ contiene al menos $n$ $a$ y $n$ $b$ por lo que la caracterización sigue). De ello se desprende que $|A\cap B|={\binom{2n}n}^2$ . Desde $|S|=\binom{4n}{2n}$ hemos terminado.

Observación. Este argumento también se puede plantear en términos de la fórmula del índice de ciclo. Definir una acción de ${\Bbb Z}_2$ en $S$ a través de la involución $\iota:S\to S$ enviando $w\mapsto w$ si $w\in A\cap B$ y $w\mapsto\bar w$ de lo contrario. La observación anterior dice que cada ${\Bbb Z}_2$ -órbita contiene exactamente una $w$ tal que $w\vdash a^nb^n$ . Entonces el número de ${\Bbb Z}_2$ -orbitas en $S$ es $$\left[\matrix{2n,2n\\n,n}\right]= \frac12\left(|\textrm{Fix}(\textrm{id})|+|\textrm{Fix}(\iota)|\right) =\frac12\left(|S|+|A\cap B|\right). $$

Answer 4

Adenda. El cálculo en la otra respuesta no es del todo riguroso en el sentido de que la serie infinita que aparece no converge en una vecindad de cero para $z.$ Esto se puede arreglar utilizando un soporte Iverson diferente.

Supongamos que, como antes, tratamos de evaluar $$S = \sum_{r=0}^n {r+n-1\choose n-1} {3n-r\choose n}$$

que es $$S_2-S_1 = \sum_{r=0}^{2n} {r+n-1\choose n-1} {3n-r\choose n} - \sum_{r=n+1}^{2n} {r+n-1\choose n-1} {3n-r\choose n}.$$

Comience por evaluar $S_2.$

Poner $${3n-r\choose n} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n-r+1}} \frac{1}{(1-w)^{n+1}} \; dw.$$

y utilizar el siguiente soporte Iverson $$[[0\le r \le 2n]] = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^{r}}{z^{2n+1}}\frac{1}{1-z} \; dz.$$

Esta segunda integral controla el rango de manera que podemos extender la suma hasta el infinito para obtener $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} \frac{1}{(1-w)^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{1-z} \sum_{r=0}^\infty {r+n-1\choose n-1} z^r w^r \; dz \; dw.$$

Esto se simplifica a $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} \frac{1}{(1-w)^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{1-z} \frac{1}{(1-wz)^n} \; dz \; dw.$$

Evaluamos la integral interna utilizando el hecho de que los residuos en los tres polos suman cero. El residuo en $z=0$ es la suma $S_2$ que estamos tratando de calcular. El residuo en $z=1$ rinde

$$-\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} \frac{1}{(1-w)^{2n+1}} \; dw = -{2n+2n\choose 2n} = -{4n\choose 2n}.$$

Para el residuo en $z=1/w$ reescribir la integral de la siguiente manera: $$\frac{(-1)^n}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{3n+1}} \frac{1}{(1-w)^{n+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{1-z} \frac{1}{(z-1/w)^n} \; dz \; dw.$$

Necesitamos una derivada que calculamos mediante la regla de Leibniz: $$\frac{1}{(n-1)!} \left(\frac{1}{z^{2n+1}} \frac{1}{1-z}\right)^{(n-1)} \\ = \frac{1}{(n-1)!} \sum_{q=0}^{n-1} {n-1\choose q} (-1)^q \frac{(2n+q)!}{(2n)! \times z^{2n+1+q}} \frac{(n-1-q)!}{(1-z)^{1+n-1-q}} \\ = \sum_{q=0}^{n-1} {2n+q\choose 2n} (-1)^q \frac{1}{z^{2n+1+q}} \frac{1}{(1-z)^{n-q}}.$$

Evaluar en $z=1/w$ para conseguir

$$\sum_{q=0}^{n-1} {2n+q\choose 2n} (-1)^q w^{2n+1+q} \frac{w^{n-q}}{(w-1)^{n-q}}.$$

Sustituya esto de nuevo en la integral en $w$ para obtener $$\sum_{q=0}^{n-1} {2n+q\choose 2n} (-1)^q \frac{(-1)^n}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{3n+1}} \frac{1}{(1-w)^{n+1}} \frac{w^{3n+1}}{(w-1)^{n-q}} \; dw \\ = \sum_{q=0}^{n-1} {2n+q\choose 2n} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(1-w)^{2n-q+1}} \; dw = 0.$$

Hemos demostrado que $$S_2 = {4n\choose 2n}.$$

Continuando con $S_1$ vemos que $$S_1 = \sum_{r=0}^{n-1} {r+2n\choose n-1} {2n-1-r\choose n} = \sum_{r=0}^{n-1} {r+2n\choose n-1} {2n-1-r\choose n-1-r}.$$

Para esta suma no se necesita el corchete de Iverson ya que la segunda binomial controla el rango a través de la siguiente integral:

$${2n-1-r\choose n-1-r} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n-1-r}}{w^{n-r}} \; dw.$$

Además, introduzca $${r+2n\choose n-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{r+2n}}{z^n} \; dz.$$

Esto da la integral $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n-1}}{w^{n}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^n} \sum_{r\ge 0} \frac{w^r (1+z)^r}{(1+w)^r} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n-1}}{w^{n}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^n} \frac{1}{1-w(1+z)/(1+w)} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n}}{w^{n}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^n} \frac{1}{1+w-w(1+z)} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n}}{w^{n}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^n} \frac{1}{1-wz} \; dz \; dw.$$

Extrayendo el residuo interior obtenemos $$\sum_{q=0}^{n-1} {2n\choose n-1-q} w^q$$ que da como resultado $$\sum_{q=0}^{n-1} {2n\choose n-1-q} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2n}}{w^{n-q}} \; dw \\= \sum_{q=0}^{n-1} {2n\choose n-1-q} {2n\choose n-1-q}.$$

Esto es $$\sum_{q=0}^{n-1} {2n\choose q}^2$$ que puede ser evaluado por inspección como en la otra respuesta, y recogiendo las contribuciones de $S_2$ y $S_1$ volvemos a obtener

$$\frac{1}{2} \left({4n\choose 2n} + {2n\choose n}^2\right).$$

Observación. Para ser totalmente rigurosos también debemos demostrar que el residuo en infinito de

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{1-z} \frac{1}{(1-wz)^n} \; dz$$

es cero. Recordemos la fórmula del residuo en el infinito $$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

que en este caso da como resultado $$-\mathrm{Res}_{z=0} \frac{1}{z^2} z^{2n+1} \frac{1}{1-1/z} \frac{1}{(1-w/z)^n} \\ = -\mathrm{Res}_{z=0} z^{2n} \frac{1}{z-1} \frac{1}{(1-w/z)^n} \\ = -\mathrm{Res}_{z=0} z^{3n} \frac{1}{z-1} \frac{1}{(z-w)^n}$$ que es cero por inspección.