Fuss–Catalan number

The Fuss-Catalan represents the number of legal permutations or allowed ways of arranging a number of articles, that is restricted in some way. This means that they are related to the Binomial Coefficient. The key difference between Fuss-Catalan and the Binomial Coefficient is that there are no "illegal" arrangement permutations within Binomial Coefficient, but there are within Fuss-Catalan. An example of legal and illegal permutations can be better demonstrated by a specific problem such as balanced brackets (see Dyck language).

A general problem is to count the number of balanced brackets (or legal permutations) that a string of m open and m closed brackets forms (total of 2m brackets). By legally arranged, the following rules apply:

• For the sequence as a whole, the number of open brackets must equal the number of closed brackets
• Working along the sequence, the number of open brackets must be greater than the number of closed brackets

As an numeric example how many combinations can 3 pairs of brackets be legally arranged? From the Binomial interpretation there are ${\displaystyle {\tbinom {2m}{m}}}$ or numerically ${\displaystyle {\tbinom {6}{3}}}$ = 20 ways of arranging 3 open and 3 closed brackets. However, there are fewer legal combinations than these when all of the above restrictions apply. Evaluating these by hand, there are 5 legal combinations, namely: ()()(); (())(); ()(()); (()()); ((())). This corresponds to the Fuss-Catalan formula when p=2, r=1 which is the Catalan number formula ${\displaystyle {\tfrac {1}{2m+1}}{\tbinom {2m}{m}}}$ or ${\displaystyle {\tfrac {1}{4}}{\tbinom {6}{3}}}$=5. By simple subtraction, there are ${\displaystyle {\tfrac {m}{m+1}}{\tbinom {2m}{m}}}$ or ${\displaystyle {\tfrac {3}{4}}{\tbinom {6}{3}}}$ =15 illegal combinations. To further illustrate the subtlety of the problem, if one were to persist with solving the problem just using the Binomial formula, it would be realised that the 2 rules imply that the sequence must start with an open bracket and finish with a closed bracket. This implies that there are ${\displaystyle {\tbinom {2m-2}{m-1}}}$ or ${\displaystyle {\tbinom {4}{2}}}$=6 combinations. This is inconsistent with the above answer of 5, and the missing combination is: ())((), which is illegal and would complete the binomial interpretation.

Whilst the above is a concrete example Catalan numbers, similar problems can be evaluated using Fuss-Catalan formula:

• Computer Stack: ways of arranging and completing a computer stack of instructions, each time step 1 instruction is processed and p new instructions arrive randomly. If at the beginning of the sequence there are r instructions outstanding.
• Betting: ways of losing all money when betting. A player has a total stake pot that allows them to make r bets, and plays a game of chance that pays p times the bet stake.
• Tries: Calculating the number of order m tries on n nodes.[1]

Below is listed a few formulae, along with a few notable special cases

General Form	Special Case
${\displaystyle A_{0}(p,r)=1}$	${\displaystyle A_{0}(p,p)=A_{1}(p,1)=1}$
${\displaystyle A_{1}(p,r)=r}$	${\displaystyle A_{1}(p,p)=A_{2}(p,1)=p}$
${\displaystyle A_{2}(p,r)=r(2p+r-1)/2}$	${\displaystyle A_{2}(p,p)=A_{3}(p,1)=p(3p-1)/2}$
${\displaystyle A_{3}(p,r)=r(3p+r-1)(3p+r-2)/6}$	${\displaystyle A_{3}(p,p)=A_{4}(p,1)=p(4p-1)(4p-2)/6}$
${\displaystyle A_{4}(p,r)=r(4p+r-1)(4p+r-2)(4p+r-3)/24}$	${\displaystyle A_{4}(p,p)=A_{5}(p,1)=p(5p-1)(5p-2)(5p-3)/24}$

If ${\displaystyle p=0}$, we recover the Binomial coefficients ${\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}$.

If ${\displaystyle p=1}$, Pascal's Triangle appears, read along diagonals:

${\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 }$.

For subindex ${\displaystyle m\geq 0}$ the numbers are:

Examples with ${\displaystyle p=2}$:

${\displaystyle A_{m}(2,1)=1,1,2,5,14,42,132,429,1430,4862,\ldots }$ OEIS: A000108, known as the Catalan Numbers

${\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

Examples with ${\displaystyle p=3}$:

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

${\displaystyle A_{m}(3,2)=1,2,7,30,143,728,3876,21318,120175,690690,\ldots }$ 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 }$ OEIS: A006629

Examples with ${\displaystyle p=4}$:

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

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

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

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

• Combinatorics
• Statistics
• Binomial coefficient
• Binomial Distribution
• Catalan number
• Dyck language
• Pascal's triangle

• Fuss, N. I. (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). Combinatorial identities. Wiley. ISBN 978-0471722755.
• Bisch, Dietmar; Jones, Vaughan (1997). "Algebras associated to intermediate subfactors". Inventiones Mathematicae. 128 (1): 89–157. Bibcode:1997InMat.128...89J. doi:10.1007/s002220050137. S2CID 119372640.
• Przytycki, Jozef H.; Sikora, Adam S. (2000). "Polygon dissections and Euler, Fuss, Kirkman , and Cayley Numbers". Journal of Combinatorial Theory, Series A. 92: 68–76. arXiv:math/9811086. doi:10.1006/jcta.1999.3042. S2CID 15724561.
• Aval, Jean-Christophe (2008). "Multivariate Fuss-Catalan numbers". Discrete Mathematics. 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). "Asymptotic distribution of singular values of powers of random matrices". Lithuanian Mathematical Journal. 50 (2): 121–132. arXiv:1012.2743. doi:10.1007/s10986-010-9074-4. S2CID 3799186.
• Mlotkowski, Wojciech (2010). "Fuss-Catalan Numbers in noncommutative probability". Documenta Mathematica. 15: 939–955. doi:10.4171/dm/318. S2CID 8083529.
• Penson, Karol A.; Zyczkowski, Karol (2011). "Product of Ginibre matrices: Fuss-Catalan and Raney distributions". Physical Review E. 83 (6): 061118. arXiv:1103.3453. Bibcode:2011PhRvE..83f1118P. doi:10.1103/PhysRevE.83.061118. PMID 21797313. S2CID 15289531.
• Gordon, Ian G.; Griffeth, Stephen (2012). "Catalan numbers for complex reflection groups". American Journal of Mathematics. 134 (6): 1491–1502. arXiv:0912.1578. doi:10.1353/ajm.2012.0047. S2CID 2654664.
• Mlotkowski, W.; Penson, K. A. (2015). "A Fuss-type family of positive definite sequences". arXiv:1507.07312 [math.PR].
• He, Tian-Xiao; Shapiro, Louis W. (2017). "Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group". Linear Algebra and Its Applications. 532: 25–42. doi:10.1016/j.laa.2017.06.025.