# Some Combinatorial Interpretations and Applications of Fuss-Catalan Numbers

Authors: Chin-Hung Lin
Journal: ISRN Discrete Mathematics
 (2011)

---

## Abstract

Fuss-Catalan number is a family of generalized Catalan numbers. We begin by two definitions of Fuss-Catalan numbers and some basic properties. And we give some combinatorial interpretations different from original Catalan numbers. Finally we generalize the Jonah's theorem as its applications.


---

## Body

## 1. Introduction

Catalan numbers{cn}n≥0 [1] are said to be the sequence satisfying the recursive relation(1.1)cn+1=c0cn+c1cn-1+⋯+cnc0,c0=1.
It is well known that the nth term of Catalan numbers is cn=(1/(n+1))(2nn)=(1/(2n+1))(2n+1n) and {cn}n≥0={1,1,2,5,14,42,132,…}. Also, one of many combinatorial interpretations of Catalan numbers is that cn is the number of shortest lattice paths from (0,0) to (n,n) on the 2-dimensional plane such that those paths lie beneath the line y=x.On the other hand,Fuss-Catalan numbers{cn(s)}s,n≥0 were investigated by Fuss [2] and studied by several authors [1, 3–7]. Hence we have the following proposition.Proposition 1.1.
Ifn and s are nonnegative integers, the following statements are equivalent:      (1)
(1.2)cn(s)=1sn+1(sn+1n);(2)
(1.3)cn+1(s)=∑r1+r2+⋯+rs=ncr1(s)×cr2(s)×⋯×crs(s),c0(s)=1;(3)
cn(s) is the number of shortest lattice paths from (0,0) to (n,(s-1)n) on the 2-dimensional plane such that those paths lie beneath y=(s-1)x.It is easy to see that in the case whens=2, the sequence of Catalan numbers {cn} is a special case of the family of Fuss-Catalan numbers {cn(2)}. Although Fuss-Catalan numbers could be viewed as one kind of generalized Catalan numbers, Fuss finished this work many years before Catalan [8].The proposition describing Fuss-Catalan numbers could be restated in the language of generating functions.Proposition 1.2.
The generating functionC(s)(x)=∑n≥0cn(s)xn satisfies the equation x(A(s))s(x)=A(s)(x)-1, where A(x) is a generating function. That is,
(1.4)x(C(s))s(x)=C(s)(x)-1.There are many combinatorial interpretations of Fuss-Catalan numbers, but most of them are similar to that of Catalan numbers. In order to demonstrate the importance of Fuss-Catalan number, in Section2 we tried to find some combinatorial interpretations which is different from original Catalan numbers.Finally, Hilton and Pedersen [9] generalized an identity called Jonah's theorem which involves Catalan numbers. So in Section 3 we restated the identity in Jonah's theorem in the form of Fuss-Catalan numbers.


## 2. Some Other Interpretations

It is remarkable that the interpretation in Proposition1.1 illustrates the relation between paths in an n×n square and Catalan numbers. It is reasonable to consider whether Fuss-Catalan numbers are relevant to paths in an n×n×n cube. As the cube in Figure 1, consider the shortest path in it from (0,0,0) to (n,n,n). There are (3n)!/n!n!n! paths. But it is notable that (3n)!/n!n!n! could be also written as(2.1)(3nn)(2nn)(nn)=(2n+1)cn(3)×(n+1)cn(2).Figure 1
Ann×n×n cube.Maybe by giveing some constraints, shown in Figure2, the number of paths will be precisely cn(3)×cn(2). And here are some results, which consider a more general case on an n×n×(s-1)n cuboid.Figure 2
Constrained regions in Corollary2.2 and Theorem 2.1.Theorem 2.1.
From(0,0,0) to (n,n,(s-1)n) and under the following constraints:
(2.2)(s-1)y-z≥0,x-1sy-1sz≥0,
there are cn(s+1)×cn(s) shortest paths.Proof.
LetP be a shortest path constrained by the conditions in Theorem 2.1. First consider the projection of P on the yz-plane. The projection could be thought as a shortest path in an n×(s-1)n right triangle in Proposition 1.1. So there are cn(s) ways to decide a path on this triangle. Fix one path and use this path to cut the cuboid with the positive direction of the x-axis. The graph is like a ladder in the right side of Figure 3 and could be put on a plane, and then it becomes an n×sn right triangle. So in this situation, there are cn(s+1) ways to be chosen. Finally since we may choose the paths in the n×(s-1)n triangle and that in the n×sn triangle independently, there are cn(s+1)×cn(s) paths totally.Figure 3
Auxiliary graphs for Theorem2.1.Corollary 2.2.
From(0,0,0) to (n,n,n) and under the following constraints:
(2.3)y-z≥0,x-12y-12z≥0,
there are cn(3)×cn(2) shortest paths.Proof.
This is a special case of Theorem2.1.If now we loosen the condition “the base of the cuboid must be square”, we can get some more general result. And the proof of this theorem is similar to that of Theorem2.1.Theorem 2.3.
Letm, n, s, t be positive integers and sn=(t-1)m. From (0,0,0) to (m,n,(s-1)n) and under the following constraints:
(2.4)(s-1)y-z≥0,x-msny-msnz≥0,
there are cm(t)×cn(s) shortest paths.


## 3. Generalized Jonah's Theorem

Jonah's theorem [9] is the identity(3.1)(n+1m)=∑i≥0ci(n-2im-i),n∈N0,m∈N0,
where ℕ0 is the set of nonnegative integers and ci is the ith term of Catalan numbers. Hilton and pedersen [9] proved the new identity(3.2)(n+1m)=∑i≥0ci(n-2im-i),n∈R,m∈N0,
where ℝ is the set of real numbers. The theorem is proven by lattice paths. Here we try to generalize the identity (3.2) as follows showing the connection with Fuss-Catalan numbers cn(s):(3.3)(n+1m)=∑i≥0ci(s)(n-sim-i),n∈R,m∈N0.The following lemmas will be needed to prove the identity (3.3).Lemma 3.1.
For any generating functionf(x) with f(0)=0, the equation
(3.4)f(x)Bs(x)=B(x)-1
has at most one solution of generating function (abbreviated SGF). That is, if f(x) is a generating function with f(0)=0, there is at most one generating function g(x) satisfying
(3.5)f(x)gs(x)=g(x)-1.Proof.
The casess=0 and s=1 is easy since (3.4) could be solved immediately. So we assume that s≥2. If g(x) is one SGF of (3.4), we have the identity
(3.6)fBs-B+1=(B-g)(fBs-1+fgBs-2+⋯+fgs-2B+fgs-1-1),
where f, B, and g are the abbreviations of f(x), B(x), and g(x). Since the ring of formal power series is an integral domain, if B(x) has any SGF other than g(x) then the second term in the right hand side must be identically zero. However, if B(x) is a generating function, we have B(0)<+∞ and so f(0)Bi(0)=f(0)gs-1(0)=0 for all proper integer i. Since the second term on the right equals −1 but not 0 as x=0, it could not be identically zero. That is, g(x) is the only SGF.Lemma 3.2.
Let(3.7)p(x)=1+x,q(x)=C(s)(x(1+x)-s)=∑i≥0ci(s)xi(1+x)-is,
where C(s) is the generating function of cn(s) where s is fixed. Then for f(x)=x(1+x)-s, both p(x) and q(x) are SGFs of (3.4). Hence p(x)=q(x). That is,
(3.8)1+x=∑i≥0ci(s)xi(1+x)-is.Proof.
Naturallyp(x) is a generating function;  q(x) is also a generating function since it is the linear combinartion of power of the generating function f(x).
Observe that
(1)
x(1+x)-sps(x)=x(1+x)-s(1+x)s=x=p(x)-1;(2)
x(1+x)-sqs(x)=x(1+x)-s(C(s)(x(1+x)-s))s=C(s)(x(1+x)-s)-1=q(x)-1, since
(3.9)x(C(s)(x))s=C(s)(x)-1
by Proposition 1.2. So both p(x) and q(x) are SGFs of (3.4). Finally by Lemma 3.1, there is at most one SGF. Hence p(x)=q(x).Theorem 3.3.
For any real numbern and integer m, the following identity holds:
(3.10)(n+1m)=∑i≥0ci(s)(n-sim-i),n∈R,m∈N0.Proof.
By multiplying both sides of (3.8) by (1+x)n, we have
(3.11)(1+x)n+1=c0(s)(1+x)n+c1(s)x(1+x)n-s+⋯+cm(s)xm(1+x)n-ms+⋯.
Then we get (3.10) by comparing the coefficients.The following are the special cases of Theorem3.3:(i)s=0⇒Pascal's theorem(3.12)(n+1m)=(nm)+(nm-1),(ii)s=1⇒Chu Shih-Chieh's theorem(3.13)(n+1m)=(nm)+(n-1m-1)+⋯+(n-m0).(iii)s=2⇒Jonah's theorem.On the other hand, even whenm≥n+1 the identity holds.Example 3.4.
Recall that(aa)=1 and (ab)=0 when b>a.
(i) Whens=3, n=4, m=5,
(3.14)1=(55)=c0(3)(45)+c1(3)(14)+c2(3)(-23)+c3(3)(-52)+c4(3)(-81)+c5(3)(-110)=1×0+1×0+3×(-4)+12×15+55×(-8)+273×1=1.
(ii)
Whens=3, n=3, m=5,
(3.15)0=(45)=c0(3)(35)+c1(3)(04)+c2(3)(-33)+c3(3)(-62)+c4(3)(-91)+c5(3)(-120)=1×0+1×0+3×(-10)+12×21+55×(-9)+273×1=0.Note 1.
Theorem3.3 can also be proved by lattice paths when n is nonnegative integer and n-m+1≥(s-1)m (see Figure 4).
Consider the number of shortest path from(0,0) to (m,n-m+1), which is (n+1m). On the other hand, consider the auxiliary line L:y=(s-1)x. Then every path must pass through L in order to reach the ending point (m,n-m+1). So we can classify all the paths by the points they pass L for the “first time”. Then there are ci(s)(n-sim-i) paths passing by point (i,(s-1)i), because before (i,(s-1)i) the path lies beneath L, and thus there are ci(s) ways; after (i,(s-1)i) the path must go upward to (i,(s-1)i+1) and then finally reach (m,n-m+1) without any constraints, and thus there are (n-sim-i) ways. So the total number of paths will be the summation of that of each point.Figure 4
The lattice for the proof of Theorem3.3.



---

*Source: 534628-2011-11-14.xml*