We provide a combinatorial interpretation of bisnomial coefficients, by using paths that lie on hypergrids. 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. Bisnomial 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 bisnomial coefficient, as well as a presentation of some new arithmetical properties of these numbers. First, we need to introduce some definitions and concepts concerning bisnomial coefficients, s-Pascal triangle and Catalan numbers.
1.1 Definition 1.1 Let s
1, n the coefficient of xk in the following development 0 be integers and let k 2 { 0, 1, . . . , sn}. The bisnomial coefficient denoted by nk s, is (1 + x + x2 + · · · + xs)n = X ✓n◆
xk. j1+j2+···+js=k ✓ n ◆✓j1◆ j1 j2 · · · ✓js 1 .
◆ js ✓n◆ bk/(s+1)c
X ( 1)j ✓n◆✓k j j(s + 1) + n 1◆ (1) (2) (3) • Symmetry relation, • Generalized Pascal Formula, • Diagonal recurrence relation, ✓n◆ k s = ✓
sn ✓n◆ k s
s ✓ n = X m=0 n k
◆ k s k s
n ✓ n ◆✓ = X m=0 m k m s 1
.
Cn =
1 n + 1 ✓2n◆ n
, n 2 Z+.
C(x) =
X Cnxn = n 1 p 1 2x 4x
By definition, Pascal triangle is the triangular array of binomial coefficients, where each of their elements is calculated
by using Pascal Formula, nk = nk 1 + nk 11 . We consider a generalization of Pascal triangle denoted by s-Pascal
triangle, as the array of bisnomial 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 bisnomial coefficients in SLOANE [
n\k
0
1
2
3
4
Catalan numbers are given in Sloane [
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).
In the following section, we give combinatorial interpretations of both bisnomial coefficients and generalized Pascal Formula, through using oriented paths that moving on Hypergrids.
Combinatorial interpretation of bisnomial coefficients
Freund [
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 · · · 2 · · · nn · · · n, |i1 {tizmes} |i2 {tizmes} |in{tizmes} 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, 3 1 we have, p3,1 = 1112 = 1 2 .
2nd -16st o o
o • 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 bisnomial coefficients by counting the cardinality of the set Pn,k,s.
Theorem 2.1 For n, k, s 2 Z+, with 0 k sn, we have, #Pn,k,s = n . 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+kn1 s = Pknsm1=s0 +k nkmn2s s + · · · + = k s + = Pisn+1=0 #n1i1 2i2 · · · nin | Pnm=1 im = k n k s s = Pisn+1=0 #n1i1 2i2 · · · nin (n + 1)in+1 | Pnm=1 im = k in+1; i1, i2, . . . , in s = #n1i1 2i2 · · · nin (n + 1)in+1 | Pnm+=11 im = k; i1, i2, . . . , in, in+1 so. o = #Pn+1,k,s.
in+1; i1, i2, . . . , in s o 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 O s s s
s 1st In fact, #n1i1 2i2 3i3 4i4 ; i1 + i2 + i3 + i4 = 3; i1, i2, i3, i4 1o = 43 1 = 43 = 4.
Definition 2.2 We denote by Jn 1, the projection map on the hypergrid Hn 1,s, defined as,
Jn 1 : Pn,k,s ! pi1,i2,...,in 7!
Ss
m=0 Pn 1,k m,s pi1,i2,...,in 1 following bijection, Pn,k,s Jns 1 Ssm=0 Pn 1,k m,s.
Theorem 2.2 The generalized Pascal Formula, nk s = Psm=0 kn m1 s, can be interpreted over hypergrids by the Proof 2.2 Obviously, the map Jn 1 is surjective by definition, so, Jn 1(Pn,k,s) = Ssm=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 clear that, Pn 1,k m1,s T Pn 1,k m2,s = ; , so, #Jn 1(Pn,k,s) = # Ssm=0 Pn 1,k m,s = Psm=0 #Pn 1,k m,s = Psm=0 kn m1 s = nk s. Consequently, we have proved that the two sets Pn,k,s and Ssm=0 Pn 1,k m,s, have the same cardinality, then, they are in bijection.
Example 2.3 For n = 4, k = 6, s = 3, the generalized Pascal Formula, 46 3 = P3m=0 6 3m 3 = 10 + 12 + 12 + 10, is interpreted over hypergrids by the following bijection, P4,6,3 Js3 P3,6,3 [ P3,5,3 [ P3,4,3 [ P3,3,3, see Table 4,
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, [
Raney numbers, [
Hilton and Pedersen, [
Koç et al., [
In the rest of this paper we consider an odd integer s. First, we define central bisnomial coefficients as a generalization of central binomial coefficients, as follows Definition 3.1 For n 2 Z+, central bisnomial coefficients are given by the following form, 2snn s. Remark 3.1 Central bisnomial coefficients divide s-Pascal triangle into two symmetric parts, as in the classical case, for s = 1.
0, we define s-Catalan numbers as
Cn,s =
✓2n◆
sn s
The values which correspond to the s-Catalan numbers appeared in physics of particles theory (under another
appellation), especially, in the issues related to spin multiplicities, see the two recent papers of, E. Cohen et al., [
We get the s-Catalan numbers by subtracting from the middle column of the s-Pascal triangle, 2snn 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 [
The following theorem gives the generalization of Formulae (10) and (11), respectively.
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.