Número de particiones dentro de jóvenes forma $\lambda$

Question

Es bien sabido que el número de particiones contenidas dentro de una $m\times n$ rectángulo es $\binom{m+n}{n}$.

Además, no es difícil calcular el número de particiones dentro de una Joven de la forma $\lambda$ donde $\lambda $ es también una partición, para las "pequeñas" $\lambda$ por recursivamente contar entramado de caminos con los pasos de arriba y a la derecha.

Por ejemplo, el número de particiones contenidas dentro de la forma $\lambda = (3,2,1,1)$ 19.

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$

Hay una forma más simple para determinar el número de particiones contenidas dentro de la forma $\lambda=(\lambda_1,\dots,\lambda_n$)?

Answer 1

No está seguro de lo simple que es, pero Percy MacMahon ideado una manera general a hacer esto como una aplicación de generación de funciones trabajó fuera de avión de particiones. Ver Combinatorio Análisis v2, $\S$X, 11, párrafos 497-498. Estos son, en la segunda de las páginas 245-246 de la década de 1960 Chelsea reimpresión.

La respuesta para un general $n$ parte de la partición es el factor determinante de una $n \times n$ matriz. Él trabaja hasta cuatro piezas en detalle; aquí es el cálculo de su ejemplo (de modo $p_1 = 3$, $p_2 = 2$, $p_3 = p_4 = 1$).

$$ \frac{1}{4!} \begin{vmatrix} p_1 + 1 & p_2(p_2+1) & (p_3-1)p_3(p_3+1) & (p_4-2)(p_4-1)p_4(p_4+1) \\ 1 & 2(p_2+1) & 3p_3(p_3+1) & 4(p_4-1)p_4(p_4+1) \\ 0 & 1 & 3 (p_3+1) & 6p_4(p_4+1) \\ 0 & 0 & 1 & 4(p_4+1)\end{vmatrix} \\ = \frac{1}{24} \begin{vmatrix} 4 & 6 & 0 & 0 \\ 1 & 6 & 6 & 0 \\ 0 & 1 & 6 & 12 \\ 0 & 0 & 1 & 8 \end{vmatrix} = \frac{456}{24} = 19$$

Desde una partición y su conjugado tienen el mismo número de particiones, el trabajo es más fácil teniendo en cuenta la partición del conjugado (4,2,1).

$$ \frac{1}{3!} \begin{vmatrix} p_1 + 1 & p_2(p_2+1) & (p_3-1)p_3(p_3+1) \\ 1 & 2(p_2+1) & 3p_3(p_3+1) \\ 0 & 1 & 3 (p_3+1) \end{vmatrix} = \frac{1}{6} \begin{vmatrix} 5 & 6 & 0 \\ 1 & 6 & 6 \\ 0 & 1 & 6 \end{vmatrix} = \frac{114}{6} = 19$$

Answer 2

Ira Gessel tiene muy amablemente explicó cómo esto puede ser resuelto por contar nonintersecting entramado de caminos. De nuevo, trabajando a través del ejemplo de $(3,2,1,1)$ le explicará el enfoque general.

En primer lugar, convertir el problema a contar las distintas parte particiones contenidas en $(3+3,2+2,1+1,1+0) = (6,4,2,1)$. Ahora una colección de cuatro nonintersecting rutas de $(0,0), (1,0), (2,0), (3,0)$ $(1,6), (2,4), (3,2), (4,1)$da un subpartition mirando la altura de cada columna de los cuadros. E. g.,

corresponde a $(5,3,2,0)$ $(6,4,2,1)$ y la partición de $(5-3,3-2,2-1,0-0) = (2,1,1)$$(3,2,1,1)$. El uso de la Gessel-Viennot Lema, el número de cuartetos de nonintersecting de los caminos es dada por

$$ \begin{vmatrix} \binom{7}{1} & \binom{6}{2} & \binom{5}{3} & \binom{5}{4} \\ \binom{6}{0} & \binom{5}{1} & \binom{4}{2} & \binom{4}{3} \\ \binom{7}{-1} & \binom{4}{0} & \binom{3}{1} & \binom{3}{2} \\ \binom{8}{-2} & \binom{5}{-1} & \binom{2}{0} & \binom{2}{1} \end{vmatrix} = \begin{vmatrix} 7 & 15 & 10 & 5 \\ 1 & 5 & 6 & 4 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 1 & 2 \end{vmatrix} = 19.$$

Nota que se mueve a distintas parte de las particiones es necesario para este enfoque, ya que, por ejemplo, el vacío de la partición de $(0,0,0,0)$ $(3,2,1,1)$ corresponden a caminos que se entrecruzan otros puntos a lo largo de la parte inferior. En el equivalente a distintas parte subpartition problema, el vacío de partición corresponde a $(3,2,1,0)$.

Permítanme concluir con una nota histórica. En el contexto de los Jóvenes diagramas, este determinante resultado es generalmente atribuida a Kreweras 1965. En el contexto de las particiones, MacMahon la solución está en su 1915 colección y podrá fecha incluso anterior. (MacMahon y Kreweras soluciones son muy similares, y Gessel y Viennot conectarse a Kreweras como una aplicación de sus resultados.)