=Paper=
{{Paper
|id=Vol-2925/short3
|storemode=property
|title=Combinatorial interpretation of bisnomial coefficients and generalized Catalan numbers
|pdfUrl=https://ceur-ws.org/Vol-2925/short3.pdf
|volume=Vol-2925
|authors=Hacène Belbachir,Oussama Igueroufa
|dblpUrl=https://dblp.org/rec/conf/algos/BelbachirI20
}}
==Combinatorial interpretation of bisnomial coefficients and generalized Catalan numbers
==
https://ceur-ws.org/Vol-2925/short3.pdf
C OMBINATORIAL INTERPRETATION OF BIs NOMIAL
COEFFICIENTS AND GENERALIZED C ATALAN NUMBERS
Hacène Belbachir Oussama Igueroufa
Faculty of Mathematics Faculty of Mathematics
USTHB, RECITS Laboratory, CATI Team USTHB, RECITS Laboratory, CATI Team
B.P. 32, El Alia, 16111, Bab Ezzouar, Algeria. B.P. 32, El Alia, 16111, Bab Ezzouar, Algeria.
A BSTRACT
We provide a combinatorial interpretation of bis nomial coefficients, by using paths that lie on hyper-
grids. We also give a generalization of Catalan numbers, called as s-Catalan, through using s-Pascal
triangle. Two identities of s-Catalan numbers are derived.
Keywords Bis nomial coefficients · s-Pascal triangle · Generalized Pascal Formula · Hypergrids · s-Catalan numbers.
1 Introduction
Bis nomial coefficients were introduced for the first time in 1730, by Abraham de Moivre [7], in his study to answer to
the following question: "Considering L dices with (s + 1) numbered faces. If they are thrown randomly, what would
be the chance of the sum of exhibited numbers to be equal to k ?", see also Hall and Knight [16]. Some years later,
Euler [8, 9], studied these coefficients and derived a number of properties, as formulae (4), (6) below. In 1876, André
[1] used combinations on words to establish several other properties.
Recently, the authors [3], published a paper that focused on a historical introduction of bis nomial coefficient, as well
as a presentation of some new arithmetical properties of these numbers. First, we need to introduce some definitions
and concepts concerning bis nomial coefficients, s-Pascal triangle and Catalan numbers.
1.1 Bis nomial Coefficients
n
Definition 1.1 Let s 1, n 0 be integers and let k 2 {0, 1, . . . , sn}. The bis nomial coefficient denoted by k s , is
the coefficient of xk in the following development
X ✓n ◆
(1 + x + x2 + · · · + xs )n = xk . (1)
k s
k 0
For k < 0 or k > sn, we have, nk s = 0. For s = 1, we get the classical binomial coefficient n
k 1 =
n
k . In the
literature of bis nomial coefficients, we often meet the following well known properties
• Expression of bis nomial coefficients in terms of binomial coefficients,
✓ ◆ X ✓ ◆✓ ◆ ✓ ◆
n n j1 js 1
= ··· . (2)
k s j1 j2 js
j1 +j2 +···+js =k
• de Moivre alternate summation,
✓ ◆ bk/(s+1)c
X ✓ ◆✓ ◆
n n k j(s + 1) + n 1
= ( 1)j . (3)
k s j=0
j n 1
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
• Symmetry relation, ✓ ◆ ✓ ◆
n n
= . (4)
k s sn k s
• Generalized Pascal Formula, ✓ ◆ s ✓
X ◆
n n 1
= . (5)
k s m=0 k m s
• Diagonal recurrence relation,
✓ ◆ n ✓ ◆✓
X ◆
n n m
= . (6)
k s m=0 m k m s 1
By definition, Pascal triangle is the triangular array of binomial coefficients, where each of their elements is calculated
by using Pascal Formula, nk = n k 1 + nk 11 . We consider a generalization of Pascal triangle denoted by s-Pascal
triangle, as the array of bis nomial coefficients that are generated by using Relation (5). For example, Table 1, gives the
3-Pascal triangle in the left justified form. We find the first values of bis nomial coefficients in SLOANE [22], through
using the codes A027907, A008287 and A053343, for, s = 2, s = 3 and s = 4, respectively.
n
Table 1: Triangle of bi3 nomial coefficients k 3.
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12
0 1
1 1 1 1 1
2 1 2 3 4 3 2 1 0
3 1 3 6 10 12 12 10 6 3 1
4 1 4 10 20 31 40 44 40 31 20 10 4 1
1.2 Catalan Numbers
For a well introduction to Catalan numbers, their properties and combinatorial interpretations, the reader can refer to
Stanley [23], Kochy [19]. Catalan numbers, named after the Belgian mathematician Eugène Charles Catalan (1814-
1894), are defined as follows, ✓ ◆
1 2n
Cn = , n 2 Z+ . (7)
n+1 n
The generating function of these numbers is,
p
X 1 1 4x
n
C(x) = Cn x = . (8)
n
2x
Catalan numbers are given in Sloane [22], by using the code A000108, the first elements are,
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, . . . .
These numbers could be generated by subtracting the mentioned columns of Pascal triangle, as given in Table 2. This
permit us to get the three Formulae, (9), (10), (11).
✓ ◆ ✓ ◆
2n 2n
Cn = , n 0. (9)
n n+1
✓ ◆ ✓ ◆
2n 1 2n 1
Cn = , n 1. (10)
n n+1
✓ ◆ ✓ ◆
2n 2n
Cn+1 = , n 0. (11)
n n+2
In the following section, we give combinatorial interpretations of both bis nomial coefficients and generalized Pascal
Formula, through using oriented paths that moving on Hypergrids.
Table 2: Right part of Pascal triangle.
1
1
2 1
3 1
6 4 1
10 5 1
20 15 6 1
35 21 7 1
70 56 28 8 1
.. .. .. .. ..
. . . . .
2n 2n 1 2n 2n 1 2n
n n n+1 n+1 n+2
2 Combinatorial interpretation of bis nomial coefficients
Freund [10], gave a combinatorial interpretation of bis nomial coefficients nk s , as the number of different ways of
distributing k objects among n cells, where each cell contains at most s objects, see also, Bondarenko [4]. Recently,
A. Bazeniar et al., [2], provided an interpretation of these numbers, as the number of lattice paths that connect the two
points of a grid, (0, 0) and (k, n 1), for 0 k sn, by taking at most s vertices in the eastern direction. We begin
by giving some definitions and terminologies that we need in the rest of this paper.
2.1 Definitions and Notations
We denote by Hn,s , an hypergrid of dimension n, (we consider n ordered directions), such that each axis contains
s vertices without counting the vertex of origin O. As particular cases, for s = 1 and n 4, hypergrids are called
hypercubes, whereas, for n = 2 and s 2, we talk about grids.
Definition 2.1 Let n, s, p 2 Z+ , i 2 {1, 2, . . . , n}. An up-oriented path lying on the hypergrid Hn,s , is a path of a
finite length, such that
1. it starts from the vertex O,
2. when the path reaches the vertex U by taking the ith direction, it should reach a vertex V by taking the (i+p)th
direction.
We denote by pi1 ,i2 ,...,in , an up-oriented path lying on the hypergrid Hn,s , that reached,
• i1 vertices by taking the 1st direction,
• i2 vertices by taking the 2nd direction,
.
• ..
• in vertices by taking the nth direction,
with 0 im s, for m 2 {1, 2, . . . , n}.
We represent the up-oriented path pi1 ,i2 ,...,in by the linear form,
11 · · · 1} 22
| {z · · · 2} · · · nn
| {z · · · n},
| {z
i1 times i2 times in times
or by the power form, 1i1 2i2 · · · nin . We denote by the number k, the length of pi1 ,i2 ,...,in , such that k = i1 + i2 +
· · · + in , as well as Pn,k,s the set of all pi1 ,i2 ,...,in of length k that lie on the hypergrid Hn,s .
Example 2.1 In Figure 1, we differentiate an up-oriented path from ordinary paths that lie on the grid H2,3 , as
follows,
• The first path on the left is an up-oriented path because the directions are taken in an increasing order, then,
we have, p3,1 = 1112 = 13 21 .
2nd -
6
st o o o
1
Figure 1: An up-oriented path and ordinary paths on the grid H2,3 .
• The second and the third paths to the right, are not up-oriented paths due to a disorder on directions of the
two paths.
The following theorem gives a combinatorial interpretation of bis nomial coefficients by counting the cardinality of the
set Pn,k,s .
n
Theorem 2.1 For n, k, s 2 Z+ , with 0 k sn, we have, #Pn,k,s = k s.
Proof 2.1 For n = 0, 1, 2, it is easy to verify the statement. We Suppose it true for n, let us prove it for the dimension
(n + 1). By using Relation (5), we get,
n+1 Ps n
k s = m=0 k m s
= k s + k 1 s + kn 2 s + · · · + kn s s
n n
Ps n Pn o
= in+1 =0 # 1i1 2i2 · · · nin | m=1 im = k in+1 ; i1 , i2 , . . . , in s
Ps n Pn o
= in+1 =0 # 1i1 2i2 · · · nin (n + 1)in+1 | m=1 im = k in+1 ; i1 , i2 , . . . , in s
n Pn+1 o
= # 1i1 2i2 · · · nin (n + 1)in+1 | m=1 im = k; i1 , i2 , . . . , in , in+1 s .
= #Pn+1,k,s .
Example 2.2 In Figure 2, we count four possible up-oriented paths of length 3 in the hypercube H4,1 . In Table 3, we
distinguish these paths accordingly to their linear and power forms.
s
s
s
s
3rd 4th
s s
⇥
@6
2nd
I
@ ⇥ -st
1 O O
Figure 2: The up-oriented paths of length 3 in the hypergrid H4,1 and their final vertices.
Table 3: Linear and power forms of the up-oriented paths of length 3 in the hypergrid H4,1 .
i1 i2 i3 i4 Linear forms Power forms
1 1 1 0 123 11 21 31 40
1 1 0 1 124 11 21 30 41
1 0 1 1 134 11 20 31 41
0 1 1 1 234 10 21 31 41
n o
4 4
In fact, # 1i1 2i2 3i3 4i4 ; i1 + i2 + i3 + i4 = 3; i1 , i2 , i3 , i4 1 = 3 1 = 3 = 4.
In the following subsection, by using Theorem 2.1, we derive a combinatorial interpretation of generalized Pascal
Formula over hypergrids.
2.2 Combinatorial interpretation of generalized Pascal Formula
Definition 2.2 We denote by Jn 1 , the projection map on the hypergrid Hn 1,s , defined as,
Ss
Jn 1 : Pn,k,s ! m=0 Pn 1,k m,s
pi1 ,i2 ,...,in 7! pi1 ,i2 ,...,in 1
Ps
Theorem 2.2 The generalized Pascal Formula, nk s = n 1
m=0 k m s , can be interpreted over hypergrids by the
Jn 1 S s
following bijection, Pn,k,s s m=0 Pn 1,k m,s .
Ss
Proof 2.2 Obviously, the map Jn 1 is surjective by definition, so, Jn 1 (Pn,k,s ) = m=0 Pn 1,k m,s . On one hand,
by Theorem 2.1, we have, #Pn,k,s = nk s . On the other hand, for all m1 , m2 2 {0, 1, . . . , s}, such that m1 6= m2 , it is
T Ss Ps
clear that, Pn 1,k m1 ,s Pn 1,k m2 ,s = ;, so, #Jn 1 (Pn,k,s ) = # m=0 Pn 1,k m,s = m=0 #Pn 1,k m,s =
Ps n 1 n S s
m=0 k m s = k s . Consequently, we have proved that the two sets Pn,k,s and m=0 Pn 1,k m,s , have the same
cardinality, then, they are in bijection.
P3
Example 2.3 For n = 4, k = 6, s = 3, the generalized Pascal Formula, 46 3 = 3
m=0 6 m 3 = 10 + 12 + 12 + 10,
J3
is interpreted over hypergrids by the following bijection, P4,6,3 s P3,6,3 [ P3,5,3 [ P3,4,3 [ P3,3,3 , see Table 4,
J S3
Table 4: The bijection P4,6,3 s3 m=0 P3,6 m,3 .
P4,6,3 P3,6,3 P4,6,3 P3,5,3 P4,6,3 P3,4,3 P4,6,3 P3,3,3
111222 111222 111234 11123 111244 1112 111444 111
111223 111223 222334 22233 123344 1233 222444 222
112223 112223 111334 11133 112344 1123 333444 333
111233 111233 112234 11223 223344 2233 233444 233
111333 111333 112334 11233 122344 1223 133444 133
222333 222333 122234 12223 112244 1122 123444 123
122233 122233 113334 11333 113344 1133 223444 223
122333 122333 112224 11222 233344 2333 122444 122
112333 112333 123334 12333 122244 1222 112444 112
112233 112233 223334 22333 133344 1333 113444 113
122334 12233 222344 2223
111224 11122 111344 1113
3 Generalized Catalan numbers
In this section, our aim is to generalize Catalan numbers by using s-Pascal triangle, as well as to extend their identities
corresponding to this generalization. First, we recall some generalizations of Catalan numbers.
Stanley, [23], Koshy, [19] and Grimaldi, [15], collect many combinatorial interpretations of Catalan numbers through
using: paths, parenthesis, words or binary numbers, binary trees, . . . . In 1791, before Eugène Charles Catalan studied
kn
these numbers, Fuss, [11], introduced Fuss-numbers, given under many expressions, as, F (k, n) = (k 1)n+1 1
n , see
kn+1
[14], or, F (k, n) = kn+1
1
n , see [19], also as follows, F (k, n) = n1 nkn1 , see, [15, 17]. We mention that, for
k = 2, F (2, n) gives the Catalan numbers. A combinatorial interpretation of these numbers is given as the number of
paths from (0, 0) to (n, (k 1)n), which take steps of the set {(0, 1), (1, 0)}, that lie below the line y = (k 1)x, see
[20].
kn+r
Raney numbers, [21], are defined as R(k, r, n) = kn+rr
n , this is a generalization of Fuss-numbers, as we have,
R(k, 1, n) = F (k, n). R(k, r, n) counts the forests composed by r ordered rooted trees, with k components and n
vertices, see [23].
Hilton and Pedersen, [17], presented a solution to the well known ballot problem, as well as they gave a generalization
of Catalan numbers. They showed that the number of paths lie completely below the line y = x, which connect the two
points (1, 0) and (a, b), for a > b two integers, is equal to the number aa+bb a+b
a . As a particular case, for a = n + 1
and b = n, we get the Catalan numbers.
(2m)!(2n)!
Gessel,[12], called S(m, n) = m!n!(m+n)! as Super-Catalan numbers. This is a generalization of Catalan numbers,
as we have, S(1, n)/2 = Cn . Gessel and Xin, [13], presented a combinatorial interpretation of these numbers for
m = 2, 3, by using the famous Dyck paths.
m+1 n+m
Koç et al., [18], gave the following generalization, C(n, m) = n n+1 n , with m n. As a particular case,
C(n, n) gives Catalan numbers. They showed that C(n, m) is the number of paths from (0, 0) to (n, m) through using
right step and up-step without moving upper the line x = y.
3.1 s-Catalan numbers
In the rest of this paper we consider an odd integer s. First, we define central bis nomial coefficients as a generalization
of central binomial coefficients, as follows
2n
Definition 3.1 For n 2 Z+ , central bis nomial coefficients are given by the following form, sn s .
Remark 3.1 Central bis nomial coefficients divide s-Pascal triangle into two symmetric parts, as in the classical case,
for s = 1.
Definition 3.2 For n 0, we define s-Catalan numbers as
✓ ◆ ✓ ◆
2n 2n
Cn,s = . (12)
sn s sn + 1 s
The values which correspond to the s-Catalan numbers appeared in physics of particles theory (under another appel-
lation), especially, in the issues related to spin multiplicities, see the two recent papers of, E. Cohen et al., [5] and T.
Curtright et al., [6].
We get the s-Catalan numbers by subtracting from the middle column of the s-Pascal triangle, 2n sn s , its next column
2n
to the right of the same level, sn+1 s
. For s = 3, Table 5 and Table 6, give the first numbers of 3-Catalan numbers as
follows,
1, 1, 4, 34, 364, 4269, 52844, 679172, 8976188, 121223668, 1665558544, . . . ,
see [22], as A264607.
Table 5: The first columns of 3-P ascal triangle right part.
1
1 1
4 3 2 1
12 10 6 3 1
44 40 31 20 10
155 135 101 65 35
580 546 456 336 216
2128 1918 1554 1128 720
8092 7728 6728 5328 3823
.. .. .. .. .. .. .. .. ..
. . . . . . . . .
2n 2n 1 2n 2n 1 2n 2n 1 2n 2n 1 2n
3n 3 3n 1 3 3n+1 3 3n 3 3n+2 3 3n+1 3 3n+3 3 3n+1 3 3n+3 3 ···
Through using 5-Pascal triangle, the first values of 5-Catalan numbers, are
1, 1, 6, 111, 2666, 70146, 1949156, 56267133, 1670963202, 50720602314, . . . ,
see [22], as A272391.
The following theorem gives the generalization of Formulae (10) and (11), respectively.
Table 6: Generating of 3-Catalan numbers by definition.
2n 2n 2n 2n
n 3n 3 3n+1 3 Cn,3 = 3n 3 3n+1 3
0 1 0 1
1 4 3 1
2 44 40 4
3 580 546 34
4 8092 7728 364
5 116304 112035 4269
6 1703636 1650792 52844
7 25288120 24608948 679172
8 379061020 370084832 8976188
9 5724954544 5603730876 121223668
10 86981744944 85316186400 1665558544
Theorem 3.1 We have, ✓ ◆ ✓ ◆
2n 1 2n 1
Cn,s = , n 1. (13)
sn s sn + 1 s
✓ ◆ ✓ ◆
2n 2n
Cn+1,s = , n 0. (14)
sn s sn + (s + 1) s
Ps Ps
Proof 3.1 By using Formula (5), we get, Cn,s = 2n sn s
2n
sn+1 s =
2n 1
m=0 sn m s
2n 1
m=0 sn+1 m s =
2n 1 2n 1 2n 1 2n 1 2n 1 2n 1
sn s s sn+1 s . Formula (4) gives, sn s s = sn s , then we find, Cn,s = sn s sn+1 s .
To get Formula (14), first we calculate Cn+1,s , by using Formula (12), then we follow the same proof of Formula (13),
by applying Formula (5) twice.
As a future work, we want to find a combinatorial interpretation of s-Catalan numbers, especially, by using up-oriented
paths on hypergrids.
References
[1] D. André. Mémoire sur les combinaisons régulière et leurs applications, Annales scientifique de l’ENS. 2eme série,
tome 5, pages 155–198, 1876.
[2] A. Bazeniar, M. Ahmia, H. Belbachir. Connection between bis nomial coefficients and their analogs and symmetric
functions. Turkish Journal of Mathematics, 42, pages 807–818, doi: 10.3906/ mat-1705-27, 2018.
[3] H. Belbachir, O. Igueroufa. Congruence properties for bis nomial coefficients and like extended Ram
and Kummer theorems under suitable hypothesis. Mediterranean Journal of Mathematics, 17:36,
https://doi.org/10.1007/s00009-019-1457-0, 2020.
[4] B. Bondarenko. Generalized Pascal triangle and Pyramids, their fractals graphs and applications. The Fibonacci
Association, Santa Clara, 1993.
[5] E. Cohen, T. Hansen, N. Itzhanki. From entanglement witness to generalized Catalan numbers. Scientific Reports,
6:30232, doi:10.1038/srep30232, 2016.
[6] T. Curtright, T. V. Kortryk, C. Zachos. Spin Multiplicities. Physics letter A. Elsevier, 381, pages 422–427, 2017.
[7] A. de Moivre. The Doctrine of Chances, 3rd ed. London: Millar, 1756, rpt. New York: Chelsea, 1967.
[8] L. Euler. De evolutione potestatis polynomialis cuiuscunque (1+x+x2 +· · · )n . Nova Acta Academiae Scientarum
Imperialis Petropolitinae 12, 1801, 47-57; Opera Omnia: Series 1, Volume 16, 28–40. Original copy is available
online in Euler’s archive.
[9] L. Euler. Observationes analyticae, Novi Commentarii Academiae Scientarum Petropolitanae. 11, 1767, 124–143,
Opera Omnia, Series 1 Vol. 15, 50–69. Original copy is available online in Euler’s archive.
[10] J. E. Freund. Restricted Occupancy Theory A Generalization of Pascal’s Triangle. The American Mathematical
Monthly, 63, No. 1, pages 20–27, 1956.
[11] N. Fuss. Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi
quaeat. Nova acta academiae scientiarum imperialis Petropolitanae, 9, p. 243–251, 1791.
[12] I. M. Gessel. Super ballot numbers. Journal of Symbolic Computation. Elsevier, 14, pages 179–194, 1992.
[13] I. M. Gessel, G. Xin. A combinatorial interpretation of the numbers 6(2n)!n!(n + 2)!. Journal of Integer Se-
quences, 8, article 05.2.3, 2005.
[14] R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics. Addison-Wesley, Boston, 1994.
[15] R. P. Grimaldi. Fibonacci and Catalan numbers An introduction. Wiley, 2012.
[16] H. S. Hall, S. R. Knight. Higher Algebra: a Sequel to Elementary Algebra for Schools. London : Macmillan and
Co, 1894.
[17] P. Hilton, J. Pedersen. Catalan numbers, their generalization, and their uses. The Mathematical Intelligencer, 13,
pages 64–75, 1991.
[18] C. Koç, I. Güloglu, S. Esin. Generalized Catalan number, sequences and polynomials. Turkish Journal of Math-
ematics, 34, pages 441–449, 2010.
[19] T. Koshy. Catalan Numbers with Applications. Oxford University Press, 2009.
[20] C.H. Lin. Some Combinatorial Interpretations and Applications of Fuss-Catalan Numbers. International Schol-
arly Research Network ISRN Discrete Mathematics, article ID 534628, doi:10.5402/2011/534628, 2011.
[21] G. N. Raney. Functional composition patterns and power series reversion. American Mathematical Society, 94,
No 3, pages 441–451, 1960.
[22] Sloane. The On-Line Encyclopedia of Integer Sequences. Available on line at https://oeis.org/.
[23] R. P. Stanley. Catalan numbers. Cambridge University Press, 2015.