Fuss–Catalan number

In combinatorial mathematics and statistics, the Fuss–Catalan numbers are numbers of the form

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)}}.

They are named after N. I. Fuss and Eugène Charles Catalan.

In some publications this equation is sometimes referred to as Two-parameter Fuss–Catalan numbers or Raney numbers. The implication is the single-parameter Fuss-Catalan numbers are when $\,r=1\,$ and $\,p=2\,$ .

Uses

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 ${\tbinom {2m}{m}}$ or numerically ${\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 ${\tfrac {1}{2m+1}}{\tbinom {2m}{m}}$ or ${\tfrac {1}{4}}{\tbinom {6}{3}}$ =5. By simple subtraction, there are ${\tfrac {m}{m+1}}{\tbinom {2m}{m}}$ or ${\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 ${\tbinom {2m-2}{m-1}}$ or ${\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]

Special Cases

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

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

[1]