en>Aclany: Added tags to the page using Page Curation (unreferenced)

2013-12-17T20:22:12Z

Added tags to the page using Page Curation (unreferenced)

New page

{{Underlinked|date=December 2013}}

In [[combinatorics|combinatorial mathematics]] and statistics, the '''Fuss–Catalan''' numbers are numbers of the form

:<math>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)}. </math>

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 {{math|r}}=1.

==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 examples 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 ''2m'' brackets forms. 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 difference between the number of open and closed brackets cannot be negative
As an numeric example how many combinations can 6 brackets be legally arranged? From the Binomial interpretation there are <math>\tbinom {2m}{m}</math> or numerically <math>\tbinom 63</math> = 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 <math>\tfrac{1}{2m+1}\tbinom{2m}{m}</math> or <math>\tfrac{1}{4}\tbinom63</math>=5. By simple subtraction, there are <math>\tfrac{m}{m+1}\tbinom{2m}{m}</math> or <math>\tfrac34\tbinom63</math> =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 <math>\tbinom{2m-2}{m-1}</math> or <math>\tbinom42</math>=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 problem 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.

==Special Cases==
:<math>A_0(p,r)=1</math>;
:<math>A_1(p,r)=r</math>;
:<math>A_{2}(p,1) = p</math>.

If <math>p=0</math>, we recover the [[Binomial coefficient]]s <math>A_m(0,r){{=}}\binom{r}{m}</math>
:<math>A_m(0,1) = 1,1</math>;
:<math>A_m(0,2) = 1,2,1</math>;
:<math>A_m(0,3) = 1,3,3,1</math>;
:<math>A_m(0,4) = 1,4,6,4,1</math>.

If <math>p=1</math>, [[Pascal's Triangle]] appears, read along diagonals:
:<math>A_m(1,1) = 1,1,1,1,1,1,1,1,1,1,\ldots</math>;
:<math>A_m(1,2) = 1,2,3,4,5,6,7,8,9,10,\ldots</math>;
:<math>A_m(1,3) = 1,3,6,10,15,21,28,35,45,55,\ldots</math>;
:<math>A_m(1,4) = 1,4,10,20,35,56,84,120,165,220,\ldots</math>;
:<math>A_m(1,5) = 1,5,15,35,70,126,210,330,495,715,\ldots</math>;
:<math>A_m(1,6) = 1,6,21,56,126,252,462,792,1287,2002,\ldots</math>.

==Examples==
For subindex <math>m\ge 0</math> the numbers are:

Examples with <math>p=2</math>:
:<math>A_m(2,1) = 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,\ldots</math> {{OEIS2C|A000108}}, known as the [[Catalan Numbers]]
:<math>A_m(2,2) = 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, \ldots = A_{m+1}(2,1)</math>
:<math>A_m(2,3) = 1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, \ldots</math> {{OEIS2C|A000245}}
:<math>A_m(2,4) = 1, 4, 14, 48, 165, 572, 2002, 7072, 25194, 90440,\ldots</math> {{OEIS2C|A002057}}

Examples with <math>p=3</math>:
:<math>A_m(3,1) = 1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, \ldots</math> {{OEIS2C|A001764}}
:<math>A_m(3,2) = 1, 2, 7, 30, 143, 728, 3876, 21318, 120175, 690690,\ldots </math> {{OEIS2C|A006013}}
:<math>A_m(3,3) = 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715,\ldots = A_{m+1}(3,1)</math>
:<math>A_m(3,4) = 1, 4, 18, 88, 455, 2448, 13566, 76912, 444015, 2601300,\ldots</math> {{OEIS2C|A006629}}

Examples with <math>p=4</math>:
:<math>A_m(4,1) = 1, 1, 4, 22, 140, 969, 7084, 53820, 420732, 3362260,\ldots </math> {{OEIS2C|A002293}}
:<math>A_m(4,2) = 1, 2, 9, 52, 340, 2394, 17710, 135720, 1068012, 8579560,\ldots </math> {{OEIS2C|A069271}}
:<math>A_m(4,3) = 1, 3, 15, 91, 612, 4389, 32890, 254475, 2017356, 16301164, \ldots </math> {{OEIS2C|A006632}}
:<math>A_m(4,4) = 1, 4, 22, 140, 969, 7084, 53820, 420732, 3362260, 27343888,\ldots = A_{m+1}(4,1)</math>

==Algebra==
===Recurrence===
:<math>A_m(p,r)=A_m(p,r-1)+A_{m-1}(p,p+r-1)</math> ''equation (1)''
This means in particular that from
:<math>A_m(p,0)=0</math> ''equation (2)''
and
:<math>A_0(p,r)=1</math> ''equation (3)''
one can generate all other Fuss-Catalan numbers if {{math|p}} is an integer.

Riordan (see references) obtains a convolution type of recurrence:
:<math>A_m(p,s+r) = \sum_{k=0}^m A_k(p,r)A_{m-k}(p,s)</math> ''equation(4)''

===Generating Function===
Paraphrasing the ''Densities of the Raney distributions'' <ref>{{cite journal|journal=Docum. Mathm. | year=2013 | pages=1593-1596 | volume=18
| title=Densities of the Raney distributions| first1=Wojciech | last1=Mlotkowski|first2= Karol A. | last2=Penson| first3=Karol |last3=Zyczkowski
|arxiv= | url=http://arxiv.org/abs/1211.7259}}</ref> paper , let the ordinary [[generating function]] with respect to the index {{math|m}} be defined as follows:
:<math>B_{p,r}(z):=\sum_{m=0}^\infty A_m(p,r)z^m</math> ''equation (5)''.
Looking at equations (1) and (2), when {{math|r}}=1 it follows that
:<math>A_m(p,p)=A_{m+1}(p,1)</math> ''equation (6)''.
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
:<math>B_{p,1}(z) = 1+zB_{p,p}(z)</math>. ''equation (7)''.
Finally, extending this result by using Lambert's equivalence
:<math>B_{p,1}(z)^r=B_{p,r}(z)</math> ''equation (8)''.
The following result can be derived for the ordinary generating function for all the Fuss-Catalan sequences.
:<math>B_{p,r}(z) = [1+zB_{p,r}(z)^{p/r}]^r</math>.

==See also==
* [[Binomial coefficient]]
* [[Binomial Distribution]]
* [[Catalan number]]
* [[Dyck language]]
* [[Pascal's triangle]]

==References==
{{reflist}}

*{{cite journal|first1=N. I. | last1=Fuss | year=1791 | title=Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat | journal=Nova Acta Academiae Sci. Petropolitanae | volume=9 | pages=243–251 }}
*{{cite book| year=1968| first1=J. | last1=Riordan |title=Combinatorial identities|journal=Wiley|ISBN=978-0471722755}}
*{{cite journal| first1=Dietmar | last1=Bisch | first2=Vaughan | last2=Jones
|title=Algebras associated to intermediate subfactors
|journal=Invent. Mathem. | year=1997 | volume=128 | number=1| pages=89–157
|doi=10.1007/s002220050137}}
*{{cite journal | first1=Jozef H. | last1=Przytycki | first2=Adam S. |last2=Sikora
|title=Polygon dissections and Euler, Fuss, Kirkman , and Cayley Numbers | year=2000
|journal=J. Combinat. Theory A |volume=92 | pages=68–76 | doi =10.1006/jcta.1999.3042}}
*{{cite journal|journal=Discr. Math. | year=2008 | number=308 | volume=20
|pages=4660–4669 | title=Multivariate Fuss-Catalan numbers
|first1=Jean-Christophe | last1=Aval | doi=10.1016/j.disc.2007.08.100}}
*{{cite journal| first1=N. | last1=Alexeev | first2=F | last2=Götze | first3=A.
|last3=Tikhomirov | title=Asymptotic distribution of singular values of powers of random matrices
|year=2010 | journal=Lith. Math. J. | volume=50 | number=2 | pages=121–132 |doi=10.1007/s10986-010-9074-4}}
*{{cite journal|journal=Docum. Mathm. | year=2010 | pages=939–955 | volume=15
| title=Fuss-Catalan Numbers in noncommutative probability | first1=Wojciech | last1=Mlotkowski
|url=https://eudml.org/doc/222801}}
*{{cite journal| first1=Karol A. | last1=Penson | first2=Karol | last2=Zyczkowski
|title=Product of Ginibre matrices: Fuss-Catalan and Raney distributions
|journal=Phys. Rev. E | year=2011 | volume=83 | page=061118 | doi=10.1103/PhysRevE.83.061118
|bibcode=2011PhRvE..83f1118P }}
*{{cite journal| year=2012 | first1=Ian G. | last1=Gordon | first2=Stephen | last2=Griffeth
|title=Catalan numbers for complex reflection groups|pages=1491–1502
|journal=Am. J. Math. | volume=134 | number=6 |doi=10.1353/ajm.2012.0047}}

{{Classes of natural numbers}}

{{DEFAULTSORT:Catalan Number}}
[[Category:Factorial and binomial topics]]
[[Category:Enumerative combinatorics]]

{{Num-stub}}

Separable filter - Revision history

en>Aclany: Added tags to the page using Page Curation (unreferenced)