En matemática y estadística combinatoria , los números Fuss-Catalan son números de la forma
Llevan el nombre de N. I. Fuss y Eugène Charles Catalan .
En algunas publicaciones, esta ecuación a veces se denomina números Fuss-catalán de dos parámetros o números Raney . La implicación es que los números Fuss-Catalan de un solo parámetro son cuando r = 1 yp = 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 relacionados con el Coeficiente Binomial . La diferencia clave entre Fuss-Catalan y el Coeficiente Binomial es que no hay permutaciones de arreglo "ilegales" dentro del Coeficiente Binomial, pero sí dentro de Fuss-Catalan. Un ejemplo de permutaciones legales e ilegales se puede demostrar mejor mediante un problema específico, como los corchetes equilibrados (consulte el lenguaje Dyck ).
Un problema general es contar el número de corchetes balanceados (o permutaciones legales) que forma una cadena de m corchetes abiertos ym cerrados (total de 2m corchetes). Por arreglos legales, se aplican las siguientes reglas:
- Para la secuencia en su conjunto, el número de corchetes abiertos debe ser igual al número de corchetes 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 organizar legalmente 3 pares de corchetes? De la interpretación Binomial hay o numéricamente = 20 formas de disponer 3 corchetes abiertos y 3 cerrados. Sin embargo, hay menos combinaciones legales que estas cuando se aplican todas las restricciones anteriores. Evaluándolos a mano, hay 5 combinaciones legales, a saber: () () (); (()) (); () (()); (() ()); ((())). Esto corresponde a la fórmula Fuss-Catalan cuando p = 2, r = 1 que es la fórmula numérica en catalán 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 simplemente usando la fórmula Binomial, se vería que las 2 reglas implican que la secuencia debe comenzar con un corchete abierto y terminar con un corchete cerrado. Esto implica que hay o = 6 combinaciones. Esto es inconsistente con la respuesta anterior de 5, y la combinación que falta es: ()) ((), que es ilegal y completaría la interpretación binomial.
Si bien lo anterior es un ejemplo concreto de números catalanes, problemas similares se pueden evaluar usando la fórmula Fuss-Catalan:
- Pila de computadora : formas de organizar y completar una pila de instrucciones de computadora, cada vez que se procesa la instrucción del paso 1 y llegan nuevas instrucciones al azar. 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 apostada.
- Intentos : cálculo del número deintentosde orden m en n nodos. [1]
Casos especiales
A continuación se enumeran algunas fórmulas, junto con algunos casos especiales notables
Forma general | Caso especial |
---|---|
Si , recuperamos los coeficientes binomiales
- ;
- ;
- ;
- .
Si , Aparece el Triángulo de Pascal , leído a lo largo de las diagonales:
- ;
- ;
- ;
- ;
- ;
- .
Ejemplos de
Para subíndice los números son:
Ejemplos con :
Ejemplos con :
Ejemplos con :
Álgebra
Reaparición
- ecuación (1)
Esto significa, en particular, que desde
- ecuación (2)
y
- ecuación (3)
se pueden generar todos los demás números Fuss-Catalan si p es un número entero .
Riordan (ver referencias) obtiene un tipo de recurrencia de convolución:
- ecuación (4)
Función generadora
Parafraseando las densidades de las distribuciones de Raney [2] , definamos la función generadora ordinaria con respecto al índice m de la siguiente manera:
- ecuación (5) .
Mirando las ecuaciones (1) y (2), cuando r = 1 se sigue que
- ecuación (6) .
También tenga en cuenta que este resultado se puede obtener mediante sustituciones similares en la representación de otras fórmulas, como la representación de la relación Gamma en la parte superior de este artículo. Usando (6) y sustituyendo en (5) una representación equivalente expresada como una función generadora se puede formular como
- .
Finalmente, extendiendo este resultado usando la equivalencia de Lambert
- .
El siguiente resultado se puede derivar para la función generadora ordinaria para todas las secuencias Fuss-Catalan .
- .
Representación de recursividad
Las formas de recursividad de esto son las siguientes: La forma más obvia es:
Además, una forma menos obvia es
Representaciones alternativas
En algunos problemas, es más fácil utilizar diferentes configuraciones o variaciones de fórmulas. A continuación se muestran dos ejemplos que utilizan solo la función binomial:
Estas variantes se pueden convertir en un producto, también en representaciones factoriales o gamma.
Ver también
Referencias
- ^ Clark, David (1996). "Compact Tries". Árboles compactos de Pat (tesis). pag. 34.
- ^ Mlotkowski, Wojciech; Penson, Karol A .; Zyczkowski, Karol (2013). "Densidades de las distribuciones de Raney". Documenta Mathematica . 18 : 1593-1596. arXiv : 1211.7259 . Código Bibliográfico : 2012arXiv1211.7259M .
- Fuss, 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. Código Bibliográfico : 1997InMat.128 ... 89J . doi : 10.1007 / s002220050137 . S2CID 119372640 .
- Przytycki, Jozef H .; Sikora, Adam S. (2000). "Disecciones de polígono y números de Euler, Fuss, Kirkman y Cayley". Revista de Teoría Combinatoria, serie A . 92 : 68–76. arXiv : matemáticas / 9811086 . doi : 10.1006 / jcta.1999.3042 .
- Aval, Jean-Christophe (2008). "Números multivariados Fuss-Catalan". Matemáticas discretas . 20 (308): 4660–4669. arXiv : 0711.0906 . doi : 10.1016 / j.disc.2007.08.100 .
- 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 .
- Mlotkowski, Wojciech (2010). "Números Fuss-Catalan en probabilidad no conmutativa" . Documenta Mathematica . 15 : 939–955.
- Penson, Karol A .; Zyczkowski, Karol (2011). "Producto de matrices de Ginibre: distribuciones Fuss-Catalan y Raney". Revisión E física . 83 (6): 061118. arXiv : 1103.3453 . Código Bibliográfico : 2011PhRvE..83f1118P . doi : 10.1103 / PhysRevE.83.061118 . PMID 21797313 .
- Gordon, Ian G .; Griffeth, Stephen (2012). "Números catalanes para grupos de reflexión complejos". Revista Estadounidense de Matemáticas . 134 (6): 1491–1502. arXiv : 0912.1578 . doi : 10.1353 / ajm.2012.0047 .
- Mlotkowski, W .; Penson, KA (2015). "Una familia tipo Fuss de secuencias definidas positivas". arXiv : 1507.07312 [ math.PR ].
- Él, Tian-Xiao; Shapiro, Louis W. (2017). "Matrices Fuss-Catalan, sus sumas ponderadas y subgrupos estabilizadores del grupo Riordan". Álgebra lineal y sus aplicaciones . 532 : 25–42. doi : 10.1016 / j.laa.2017.06.025 .