Fuss–Número catalán

En matemáticas combinatorias y estadística, los números de Fuss-Catalan son números de la forma

${\displaystyle A_{m}(p,r)\equiv {\frac {r}{mp+r}}{\binom {mp+r}{m}}={\frac {r}{m!}}\prod _{i=1}^{m-1}(mp+r-i)=r{\frac {\Gamma (mp+r)}{\Gamma (1+m)\Gamma (m(p-1)+r+1)}}.}$

Llevan el nombre de N. I. Fuss y Eugène Charles Catalan .

En algunas publicaciones, esta ecuación se denomina a veces números de Fuss-Catalan de dos parámetros o números de Raney . La implicación es que los números de Fuss-Catalan de un solo parámetro son cuando y . ${\displaystyle \,r=1\,}$ ${\displaystyle \,p=2\,}$

Usos

El Fuss-Catalan representa el número de permutaciones legales o formas permitidas de ordenar un número de artículos, que está restringido de alguna manera. Esto significa que están relacionadas con el Coeficiente Binomial . La diferencia clave entre Fuss-Catalan y el Coeficiente Binomial es que no hay permutaciones de ordenación "ilegales" dentro del Coeficiente Binomial, pero sí dentro del Fuss-Catalan. Un ejemplo de permutaciones legales e ilegales se puede demostrar mejor con un problema específico como el de los paréntesis equilibrados (véase Lenguaje Dyck ).

Un problema general consiste en contar la cantidad de paréntesis equilibrados (o permutaciones legales) que forma una cadena de m paréntesis abiertos y m paréntesis cerrados (un total de 2m paréntesis). En el caso de la disposición legal, se aplican las siguientes reglas:

• Para la secuencia en su conjunto, el número de paréntesis abiertos debe ser igual al número de paréntesis cerrados.
• Trabajando a lo largo de la secuencia, el número de paréntesis abiertos debe ser mayor que el número de paréntesis cerrados.

Como ejemplo numérico, ¿cuántas combinaciones se pueden ordenar legalmente con 3 pares de paréntesis? Según la interpretación binomial, hay o numéricamente = 20 formas de ordenar 3 paréntesis abiertos y 3 cerrados. Sin embargo, hay menos combinaciones legales que estas cuando se aplican todas las restricciones anteriores. Evaluando estas a mano, hay 5 combinaciones legales, a saber: ()()(); (())(); ()(()); (()()); ((())). Esto corresponde a la fórmula de Fuss-Catalan cuando p=2, r=1 , que es la fórmula numérica de Catalan o = 5. Por simple resta, hay o = 15 combinaciones ilegales. Para ilustrar aún más la sutileza del problema, si uno persistiera en resolver el problema solo usando la fórmula binomial, se daría cuenta de que las 2 reglas implican que la secuencia debe comenzar con un paréntesis abierto y terminar con un paréntesis cerrado. Esto implica que hay o = 6 combinaciones. Esto es inconsistente con la respuesta anterior de 5, y la combinación faltante es: ())((), lo cual es ilegal y completaría la interpretación binomial. ${\displaystyle {\tbinom {2m}{m}}}$ ${\displaystyle {\tbinom {6}{3}}}$ ${\displaystyle {\tfrac {1}{2m+1}}{\tbinom {2m}{m}}}$ ${\displaystyle {\tfrac {1}{4}}{\tbinom {6}{3}}}$ ${\displaystyle {\tfrac {m}{m+1}}{\tbinom {2m}{m}}}$ ${\displaystyle {\tfrac {3}{4}}{\tbinom {6}{3}}}$ ${\displaystyle {\tbinom {2m-2}{m-1}}}$ ${\displaystyle {\tbinom {4}{2}}}$

Aunque lo anterior es un ejemplo concreto de números catalanes, se pueden evaluar problemas similares utilizando la fórmula de Fuss-Catalan:

• Pila de ordenador : formas de ordenar y completar una pila de instrucciones de ordenador, cada vez que se procesa una instrucción y llegan p nuevas instrucciones aleatoriamente. Si al principio de la secuencia hay r instrucciones pendientes.
• Apuestas : formas de perder todo el dinero al apostar. Un jugador tiene un bote de apuesta total que le permite hacer r apuestas y juega un juego de azar que paga p veces la apuesta.
• Intentos : Cálculo del número de intentos de orden m en n nodos. ^[1]

Casos especiales

A continuación se enumeran algunas fórmulas, junto con algunos casos especiales notables.

Si , recuperamos los coeficientes binomiales ${\displaystyle p=0}$ ${\displaystyle A_{m}(0,r){=}{\binom {r}{m}}}$

${\displaystyle A_{m}(0,1)=1,1}$;

${\displaystyle A_{m}(0,2)=1,2,1}$;

${\displaystyle A_{m}(0,3)=1,3,3,1}$;

${\displaystyle A_{m}(0,4)=1,4,6,4,1}$.

Si aparece el Triángulo de Pascal , léase a lo largo de las diagonales: ${\displaystyle p=1}$

${\displaystyle A_{m}(1,1)=1,1,1,1,1,1,1,1,1,1,\ldots }$;

${\displaystyle A_{m}(1,2)=1,2,3,4,5,6,7,8,9,10,\ldots }$;

${\displaystyle A_{m}(1,3)=1,3,6,10,15,21,28,35,45,55,\ldots }$;

${\displaystyle A_{m}(1,4)=1,4,10,20,35,56,84,120,165,220,\ldots }$;

${\displaystyle A_{m}(1,5)=1,5,15,35,70,126,210,330,495,715,\ldots }$;

${\displaystyle A_{m}(1,6)=1,6,21,56,126,252,462,792,1287,2002,\ldots }$.

Ejemplos

Para el subíndice los números son: ${\displaystyle m\geq 0}$

Ejemplos con : ${\displaystyle p=2}$

${\displaystyle A_{m}(2,1)=1,1,2,5,14,42,132,429,1430,4862,\ldots }$ OEIS : A000108 , conocida como Números Catalanes

${\displaystyle A_{m}(2,2)=1,2,5,14,42,132,429,1430,4862,16796,\ldots =A_{m+1}(2,1)}$

${\displaystyle A_{m}(2,3)=1,3,9,28,90,297,1001,3432,11934,41990,\ldots }$ OEIS : A000245

${\displaystyle A_{m}(2,4)=1,4,14,48,165,572,2002,7072,25194,90440,\ldots }$ OEIS : A002057

Ejemplos con : ${\displaystyle p=3}$

${\displaystyle A_{m}(3,1)=1,1,3,12,55,273,1428,7752,43263,246675,\ldots }$ Norma OEIS : A001764

${\displaystyle A_{m}(3,2)=1,2,7,30,143,728,3876,21318,120175,690690,\ldots }$ Norma OEIS : A006013

${\displaystyle A_{m}(3,3)=1,3,12,55,273,1428,7752,43263,246675,1430715,\ldots =A_{m+1}(3,1)}$

${\displaystyle A_{m}(3,4)=1,4,18,88,455,2448,13566,76912,444015,2601300,\ldots }$ Norma OEIS : A006629

Ejemplos con : ${\displaystyle p=4}$

${\displaystyle A_{m}(4,1)=1,1,4,22,140,969,7084,53820,420732,3362260,\ldots }$ Norma OEIS : A002293

${\displaystyle A_{m}(4,2)=1,2,9,52,340,2394,17710,135720,1068012,8579560,\ldots }$ Norma OEIS : A069271

${\displaystyle A_{m}(4,3)=1,3,15,91,612,4389,32890,254475,2017356,16301164,\ldots }$ Norma OEIS : A006632

${\displaystyle A_{m}(4,4)=1,4,22,140,969,7084,53820,420732,3362260,27343888,\ldots =A_{m+1}(4,1)}$

Álgebra

Reaparición

${\displaystyle A_{m}(p,r)=A_{m}(p,r-1)+A_{m-1}(p,p+r-1)}$ ecuación (1)

Esto significa en particular que a partir de

${\displaystyle A_{m}(p,0)=0}$ ecuación (2)

y

${\displaystyle A_{0}(p,r)=1}$ ecuación (3)

Se pueden generar todos los demás números de Fuss-Catalan si p es un entero .

Riordan (ver referencias) obtiene un tipo de convolución de recurrencia:

${\displaystyle A_{m}(p,s+r)=\sum _{k=0}^{m}A_{k}(p,r)A_{m-k}(p,s)}$ ecuación(4)

Función generadora

Parafraseando el artículo Densidades de las distribuciones de Raney ^[2] , dejemos que la función generadora ordinaria con respecto al índice m se defina de la siguiente manera:

${\displaystyle B_{p,r}(z):=\sum _{m=0}^{\infty }A_{m}(p,r)z^{m}}$ ecuación (5) .

Observando las ecuaciones (1) y (2), cuando r = 1 se deduce que

${\displaystyle A_{m}(p,p)=A_{m+1}(p,1)}$ ecuación (6) .

También tenga en cuenta que este resultado se puede derivar mediante sustituciones similares en las otras representaciones de fórmulas, como la representación de la relación gamma en la parte superior de este artículo. Utilizando (6) y sustituyendo en (5), se puede formular una representación equivalente expresada como una función generadora como

${\displaystyle B_{p,1}(z)=1+zB_{p,p}(z)}$.

Finalmente, extendiendo este resultado mediante el uso de la equivalencia de Lambert

${\displaystyle B_{p,1}(z)^{r}=B_{p,r}(z)}$.

El siguiente resultado se puede derivar para la función generadora ordinaria para todas las secuencias de Fuss-Catalan .

${\displaystyle B_{p,r}(z)=[1+zB_{p,r}(z)^{p/r}]^{r}}$.

Representación recursiva

Las formas de recursión de esto son las siguientes: La forma más obvia es:

${\displaystyle A_{m}(p,r)={\frac {m-1}{m}}{\frac {\binom {mp+r-1}{m-1}}{\binom {(m-1)p+r-1}{m-2}}}A_{m-1}(p,r)}$

Además, una forma menos obvia es

${\displaystyle A_{m}(p,r)={\frac {(m-1)p+r}{m}}{\frac {\binom {mp+r-1}{p-1}}{\binom {m(p-1)+r}{p-1}}}A_{m-1}(p,r)}$

Representaciones alternativas

En algunos problemas es más fácil utilizar distintas configuraciones o variaciones de fórmulas. A continuación se muestran dos ejemplos que utilizan únicamente la función binomial:

${\displaystyle A_{m}(p,r)\equiv {\frac {r}{mp+r}}{\binom {mp+r}{m}}={\frac {r}{m(p-1)+r}}{\binom {mp+r-1}{m}}={\frac {r}{m}}{\binom {mp+r-1}{m-1}}}$

Estas variantes también se pueden convertir en representaciones de producto, gamma o factoriales.

Véase también

• Combinatoria
• Estadística
• Coeficiente binomial
• Distribución binomial
• Número catalán
• Lenguaje Dyck
• Triángulo de Pascal

Referencias

1. Clark, David (1996). "Compact Tries". Árboles compactos de Pat (Tesis). pág. 34.
2. Mlotkowski, Wojciech; Penson, Karol A.; Zyczkowski, Karol (2013). "Densidades de las distribuciones de Raney". Documenta Matemática . 18 : 1593-1596. arXiv : 1211.7259 . Código Bib : 2012arXiv1211.7259M. doi :10.4171/dm/437. S2CID  17493895.

• Alboroto, NI (1791). "Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat". Nova Acta Academiae Scientiarum Imperialis Petropolitanae . 9 : 243–251.
• Riordan, J. (1968). Identidades combinatorias . Wiley. ISBN 978-0471722755.
• Bisch, Dietmar; Jones, Vaughan (1997). "Álgebras asociadas a subfactores intermedios". Inventiones Mathematicae . 128 (1): 89–157. Bibcode :1997InMat.128...89J. doi :10.1007/s002220050137. S2CID  119372640.
• Przytycki, Jozef H.; Sikora, Adam S. (2000). "Disecciones de polígonos y números de Euler, Fuss, Kirkman y Cayley". Journal of Combinatorial Theory, Serie A. 92 : 68–76. arXiv : math/9811086 . doi :10.1006/jcta.1999.3042. S2CID:  15724561.
• Aval, Jean-Christophe (2008). "Números multivariados de Fuss-Catalan". Matemáticas discretas . 20 (308): 4660–4669. arXiv : 0711.0906 . doi :10.1016/j.disc.2007.08.100. S2CID  509695.
• Alexeev, N.; Götze, F; Tikhomirov, A. (2010). "Distribución asintótica de valores singulares de potencias de matrices aleatorias". Revista matemática lituana . 50 (2): 121–132. arXiv : 1012.2743 . doi :10.1007/s10986-010-9074-4. S2CID  3799186.
• Mlotkowski, Wojciech (2010). "Números de Fuss-Catalan en probabilidad no conmutativa". Documenta Mathematica . 15 : 939–955. doi : 10.4171/dm/318 . S2CID  8083529.
• Penson, Karol A.; Zyczkowski, Karol (2011). "Producto de matrices de Ginibre: distribuciones Fuss-Catalan y Raney". Physical Review E . 83 (6): 061118. arXiv : 1103.3453 . Código Bibliográfico :2011PhRvE..83f1118P. doi :10.1103/PhysRevE.83.061118. PMID  21797313. S2CID  15289531.
• Gordon, Ian G.; Griffeth, Stephen (2012). "Números catalanes para grupos de reflexión complejos". American Journal of Mathematics . 134 (6): 1491–1502. arXiv : 0912.1578 . doi :10.1353/ajm.2012.0047. S2CID  2654664.
• Mlotkowski, W.; Penson, KA (2015). "Una familia de secuencias definidas positivas de tipo Fuss". arXiv : 1507.07312 [math.PR].
• He, Tian-Xiao; Shapiro, Louis W. (2017). "Matrices de Fuss-Catalan, sus sumas ponderadas y subgrupos estabilizadores del grupo de Riordan". Álgebra lineal y sus aplicaciones . 532 : 25–42. doi : 10.1016/j.laa.2017.06.025 .