In combinatorial mathematics and statistics, the FussâCatalan numbers are numbers of the form
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 and .
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:
As an numeric example how many combinations can 3 pairs of brackets be legally arranged? From the Binomial interpretation there are or numerically = 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 or =5. By simple subtraction, there are or =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 or =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:
Below is listed a few formulae, along with a few notable special cases
General Form | Special Case |
---|---|
If , we recover the
Binomial coefficients
If , Pascal's Triangle appears, read along diagonals:
For subindex the numbers are:
Examples with :
Examples with :
Examples with :
This means in particular that from
and
one can generate all other FussâCatalan numbers if p is an integer.
Riordan (see references) obtains a convolution type of recurrence:
Paraphrasing the Densities of the Raney distributions [2] paper, let the ordinary generating function with respect to the index m be defined as follows:
Looking at equations (1) and (2), when r=1 it follows that
Also note this result can be derived by similar substitutions into the other formulas representation, such as the Gamma ratio representation at the top of this article. Using (6) and substituting into (5) an equivalent representation expressed as a generating function can be formulated as
Finally, extending this result by using Lambert's equivalence
The following result can be derived for the ordinary generating function for all the Fuss-Catalan sequences.
Recursion forms of this are as follows: The most obvious form is:
Also, a less obvious form is
In some problems it is easier to use different formula configurations or variations. Below are a two examples using just the binomial function:
These variants can be converted into a product, Gamma or Factorial representations too.
In combinatorial mathematics and statistics, the FussâCatalan numbers are numbers of the form
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 and .
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:
As an numeric example how many combinations can 3 pairs of brackets be legally arranged? From the Binomial interpretation there are or numerically = 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 or =5. By simple subtraction, there are or =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 or =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:
Below is listed a few formulae, along with a few notable special cases
General Form | Special Case |
---|---|
If , we recover the
Binomial coefficients
If , Pascal's Triangle appears, read along diagonals:
For subindex the numbers are:
Examples with :
Examples with :
Examples with :
This means in particular that from
and
one can generate all other FussâCatalan numbers if p is an integer.
Riordan (see references) obtains a convolution type of recurrence:
Paraphrasing the Densities of the Raney distributions [2] paper, let the ordinary generating function with respect to the index m be defined as follows:
Looking at equations (1) and (2), when r=1 it follows that
Also note this result can be derived by similar substitutions into the other formulas representation, such as the Gamma ratio representation at the top of this article. Using (6) and substituting into (5) an equivalent representation expressed as a generating function can be formulated as
Finally, extending this result by using Lambert's equivalence
The following result can be derived for the ordinary generating function for all the Fuss-Catalan sequences.
Recursion forms of this are as follows: The most obvious form is:
Also, a less obvious form is
In some problems it is easier to use different formula configurations or variations. Below are a two examples using just the binomial function:
These variants can be converted into a product, Gamma or Factorial representations too.