Open access peer-reviewed chapter - ONLINE FIRST

Moments of Catalan Triangle Numbers

By Pedro J. Miana and Natalia Romero

Submitted: November 11th 2019Reviewed: March 9th 2020Published: April 22nd 2020

DOI: 10.5772/intechopen.92046

Abstract

In this chapter, we consider the Catalan numbers, Cn=1n+12nn, and two of their generalizations, Catalan triangle numbers, Bn,k and An,k, for n,k∈N. They are combinatorial numbers and present interesting properties as recursive formulae, generating functions and combinatorial interpretations. We treat the moments of these Catalan triangle numbers, i.e., with the following sums: ∑k=1nkmBn,kj,∑k=1n+12k−1mAn,kj, for j,n∈N and m∈N∪0. We present their closed expressions for some values of m and j. Alternating sums are also considered for particular powers. Other famous integer sequences are studied in Section 3, and its connection with Catalan triangle numbers are given in Section 4. Finally we conjecture some properties of divisibility of moments and alternating sums of powers in the last section.

Keywords

• Catalan numbers
• combinatorial identities
• binomial coefficients
• moments
• 2010 Mathematics Subject Classification: 05A19; 05A10; 11B65
• 11B75

1. Introduction

After the binomial coefficients, the well-known Catalan numbers Cnn0are the most frequently occurring combinatorial numbers. They are treated deeply in many books, monographs, and papers (e.g., [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]). Catalan numbers play an important role and have a major importance in computer science and combinatorics.

They appear in studying astonishingly many combinatorial problems. They count the number of different ways to triangulate a regular polygon with n+2sides; or, the number of ways that 2npeople seat around a circular table are simultaneously shaking hands with another person at the table in such a way that none of the arms cross each other, and also in tree enumeration problem, see these examples and others in [19, 20].

Other applications of the Catalan numbers appear in engineering in the field of cryptography to form keys for secure transfer of information; in computational geometry, they are generally used in geometric modeling; they may be also found in geographic information systems, geodesy, or medicine.

There are several ways to define Catalan numbers; one of them is recursively by C0=1and Cn=i=0n1CiCn1ifor n1; the first terms in this sequence are

1,1,2,5,14,42,132,E1

The generating formula for Catalan numbers is

Cx114x2x=n0Cnxn,0<x<1/14E2

[10] and ([20], Proposition 1.3.1).

Catalan triangle numbers Bn,kn,k1and An,kn,k1are defined by

Bn,kkn2nnk,An,k2k12n+12n+1n+1kn,kN,kn+1.E3

Notice that Bn,1=An,1=Cn. In [14], Shapiro introduced Catalan triangles whose entries are given by the coefficients

nkBn,kxn=xkC2kx,E4

see a more general approach in [10].

Although the numbers Bn,k(and also An,k) are not as well-known as Catalan numbers, they have also several applications, for example, Bn,kis the number of walks of nsteps, each in direction N, S, W, or E, starting at the origin, remaining in the upper half-plane and ending at height k; see more details in [4, 13, 14, 16] for additional information.

Both Catalan triangle numbers may be written in unified expression. We consider combinatorial numbers Cm,km1,k0,given by

Cm,km2kmmk.E5

These combinatorial numbers Cm,km1,k0are suitable rearrangements of the known ballot numbers am,kwith am,k=k+1m+12mkmfor m0and 0km, i.e.,

am,k=C2m+1k,mk,Cm,k=amk1,m2k1,E6

see example [21]. Note that C2n,nk=Bn,kand also C2n+1,n+1k=An,k. In ([9], Theorem 1.1), the authors show that any binomial coefficient can be written as weighted sums along the rows of the Catalan triangle, i.e.,

n+k+1k=j=0kCn,j2kj.E7

The generalized kth Catalan numbers kCn1nnkn1, k1, are presented in [17] to count the number of ways of subdividing a convex polygon into kdisjoint n+1-polygons by means of nonintersecting diagonals, k1; see also [2, 11].

In this paper, our main objective is to study in detail the moments of Catalan triangle numbers:

k=1nkmBn,kj,k=1n+12k1mAn,kj,E8

for j,nNand mN0. In previous papers, the authors have considered some particular cases of these sums: for j=1and m=0in [14], for j=2in [12, 13], and for j=3and m=0in [22]. In [7], the authors solved a conjecture posed in [22] about divisibility properties in the case m=0. However, there are no results in the literatures for moments for j>2. We complete and present a full treatment of these moments, for j=1in Section 2 and for j=2and for some cases of j=3in Section 4.

In the paper [23], the authors treat several families of binomial sum identities whose definition involves the absolute value function. Here we present alternating sums of for several powers of Catalan triangle numbers (Theorem 2.2, Proposition 4.1 (iii), and Proposition 4.4 (iii)). In ([24], Theorem 2.3), the following identityis proved:

k=1n1kk2Bn,k2=nn22n1Cn1,n1.E9

In this paper, we treat k=1n1kk2Bn,kjand k=1n+11kk2An,kjfor j1,2,3,4,5, and we conjecture some divisibility properties in Conjecture 5.7.

The WZ theory is a powerful tool to show hypergeometric identities. We have applied this tool in Theorem 2.1 to check certain identities. In detail, we have used the Maple program and the EKHAD package as software for the WZ method; see ([25], Example 7.5.3). Although analytic proofs are not presented, alternative proofs as to apply WZ theory [26, 27] or some mathematical software indicate us what these identities hold. Note that an analytic proof will give us some extra information about these natures of the sums.

In Section 3, we prove new identities involving sequences ann0and bnn1where

ank=0nn+kn2,bnk=0nnknn1+kn12nN,E10

and Catalan numbers Cnn0. In Theorems 3.1 and 3.2, we show that for n1,

22n+1annan1=21n+8n+122Cn2,E11
22n+1bn+1nbn=7n2+8n+2Cn2.E12

Lemma 3.3 shows that sequences ann1and bnn1are deeply connected with Catalan numbers. Recurrence relations (30) and (36) (and polynomials in these relations) play delicate roles which allow to give proof of the identity:

n+1Cn2=43an12bn,n1,E13

(Theorem 3.4).

In Section 4, we give the moments of second order in Theorem 4.2 and 4.3, and for third order, we present that

k=0nBn,k3=n+12Cnbn,k=1n+1An,k3=n+1Cn2n+1Cn23an,E14

Finally, we conjecture some divisibility properties in Section 5; in particular

k=1nk2mBn,k=n+12CnnPm1n,E15
k=1nk2m1Bn,k=2nm1Qm1n,E16
k=1n+1k2mAn,k=n+1CnRm1n,E17
k=1n+1k2m1An,k=22nSm1n,E18

where Pm1,Qm1,Rm1and Sm1are polynomials of integer coefficients at the degree at most m1(Conjectures 5.1 and 5.2). In Conjecture 5.3, we state that the factor n+12Cncould divide k=0nk2mBn,k3for m,nN; similarly the factor n+1Cnmight divide k=0n+12k12mAn,k3for m,nN(Conjecture 5.4). Similar conjectures about moments of fourth order and alternating sums are also presented in Conjectures 5.5–5.7.

2. Sums and alternating sums of Catalan triangle numbers

Catalan triangle numbers Bn,kn1,1knwere introduced in [14]. These combinatorial numbers Bn,kare the entries of the following Catalan triangle:

E19

which are given by

Bn,kkn2nnk,n,kN,kn.E20

Notice that Bn,1=Cnand Bn,n=1n1.

In the last years, Catalan triangle (19) has been studied in detail. For instance, the formula

k=1iBn,kBn,n+kin+2ki=n+1Cn2n1i1,in,E21

which appears in a problem related with the dynamical behavior of a family of iterative processes has been proved in ([8], Theorem 5). These numbers Bn,knk1have been analyzed in many ways. For instance, symmetric functions have been used in [1], recurrence relations in [15], or in [6] the Newton interpolation formula, which is applied to conclude divisibility properties of the sums of products of binomial coefficients.

Other combinatorial numbers An,kdefined as follows

An,k2k12n+12n+1n+1k,n,kN,kn+1,E22

appear as the entries of this other Catalan triangle,

E23

which is considered in [13]. Notice that An,1=Cnand C2n+1,nk+1=An,kfor kn+1.

Entries Bn,kand An,kof the above two particular Catalan triangles satisfy the recurrence relations

Bn,k=Bn1,k1+2Bn1,k+Bn1,k+1,k2,E24

and

An,k=An1,k1+2An1,k+An1,k+1,k2.E25

For mN0, we define the moments of order mby the sum

Δmnk=0nkmBn,k,Λmnk=0n+12k1mAn,k,n1.E26

As it was shown in [14], the values of the sums (or moments of order 0) of Bn,kand An,kare expressed in terms of Catalan numbers; see item (i) and (iii) in the next theorem. We apply the WZ theory to show the following moments for m017.

Theorem 2.1.FornN, the following identities hold:

1. Δ0n=n+12Cn,Δ2n=nn+12Cn,Δ4n=n2n1n+12Cn,Δ6n=n6n2+4n+1n+12Cn.

2. Δ1n=22n2,Δ3n=22n33n1,Δ5n=22n415nn1+2,Δ7n=22n5105n3210n2+147n34.

3. Λ0n=n+1Cn,Λ2n=n+1Cn4n+1,Λ4n=n+1Cn32n2+8n+1,Λ6n=n+1Cn384n332n2+12n+1.

4. Λ1n=22n,Λ3n=22n6n+1,Λ5n=22n60n2+1,Λ7n=22n840n3420n2+126n+1.

For alternating sums, the following theorem was proved in [5] and ([22], Corollary 1.3).

Theorem 2.2.Forn1, we have

1. k=1n1kBn,k=Cn1,

2. k=1n+11kAn,k=0.

Other interesting combinatorial numbers which have been deeply studied in the last decade are the well-known harmonic numbers Hnn1. These numbers are given by the following formula:

Hn=k=1n1k,nN.E27

A deep treatment of closed formulas for the sums of the form k=1nakHkis given in [18]. Also, the WZ theory is applied to get identities in [26], and infinite series involving harmonic numbers is presented in [3]. See other approaches in ([28], Chapter 7) and reference therein.

In ([22], Corollary 1.5) the next relationships between Catalan triangle numbers and harmonic numbers Hnn1are given.

Corollary 2.3.Forn1,we have

1. k=0n1Bn,kHnk=2nHn1n+14nCn22n112n,

2. k=1nAn,kHnk+1=Hnn+1Cn22n12n+1.

Remark. It is worth to consider other powers of Catalan triangle numbers and harmonic numbers to obtain, for example, formulae of

k=0n1Bn,k2Hnk,andk=1nAn,k2Hnk+1.E28

3. Sums of squares of combinatorial numbers

We consider the sequence of integer numbers defined by

ank=0nn+kn2,nN0.E29

Note that a0=1,a1=5, a2=46, a3=517, a4=6376, etc. This sequence appears indexed in the On-Line Encyclopedia of Integer Sequences by N.J.A. Sloane [16] with the reference A112029. V. Kotesovec in 2012 proved the following recurrence relation:

p1nan=p2nan1+p3nan2,n2,E30

where polynomials pii1,2,3are defined by

p1n22n+121n13n2,E31
p2n1365n41517n3+240n2+216n64,E32
p3n4n12n1221n+8.E33

Next, in the following theorem, we provide an identity which relates the square of Catalan numbers and ann0.

Theorem 3.1.Forn1, the following identity holds

22n+1annan1=21n+8n+122Cn2.E34

Proof. We show this identity by induction method. For n=1, we check directly that 29=211+8C12. Now suppose that the identity holds for any mn. Note that

21n+8n+222Cn+12=21n+842n+12n+122Cn2=42n+1222n+1annan1,

where we have applied the induction hypothesis. Then we apply the law of recurrence (30) to get that

21n+821n+29n+222Cn+1=821n+292n+13an+p3n+1an1=p1n+1an+1+821n+292n+13p2n+1an=22n+321n+8n+12an+121n+8n+13an=21n+8n+1222n+3an+1n+1an,

and we conclude the proof. □

Now we consider this second sequence of integer numbers defined by

bnk=0nkn2nk1n12=k=0nnknn1+kn12,nN.E35

Note that b1=1,b2=3, b3=19, b4=163, b5=1625, etc. This sequence also appears indexed in the On-Line Encyclopedia of Integer Sequences by N.J.A. Sloane [16] with the reference A183069, and V. Kotesovec proved the following recurrence relation:

q1nbn=q2nbn1+q3nbn2,n3,E36

where polynomials qii1,2,3are defined by

q1n2n22n17n220n+14,E37
q2n455n52427n4+4850n34406n2+1728n216,E38
q3n4n22n327n26n+1.E39

In a similar way, we obtain an identity which relates numbers bnn1to the square of Catalan numbers.

Theorem 3.2.Forn1, the following identity holds

22n+1bn+1nbn=7n2+8n+2Cn2.E40

Proof. We prove the identity by the induction method. For n=1, we directly check the identity. Suppose that the identity holds for a given number n. Since n+2Cn+1=22n+1Cn, we have that

7n2+8n+27n2+22n+17n+22Cn+12=7n2+8n+27n2+22n+1742n+12Cn2=42n+127n2+22n+1722n+1bn+1nbn=82n+137n2+22n+17bn+1+q3n+2bn=q1n+2bn+2+82n+137n2+22n+17q2n+2bn+1=27n2+8n+22n+3n+22bn+27n2+8n+2n+22n+1bn,

where we have applied the recurrence relation (36), we obtain the identity for n+1, and we conclude the result. □

Sequences ann0and bnn1are jointly connected as the next lemma shows. The proof is left to the reader.

Lemma 3.3. Forn1, the following two identities hold

q1nq3np1n1p3n1=8Qn2n12n32n2;E41
q1nq2np1n1p2n1=16Qn2n12n33,E42

whereQn147n4546n3+666n2293n+34.

Our last aim of this section is to show an alternative of the following identity

2nn2=k=0n3n2kn2n1kn12,E43

in Theorem 3.4. An original proof is presented in ([22], Theorem 2.3 (ii)), and it is a straightforward consequence of a more general identity in combinatorial numbers ([22], Theorem 2.3 (i)). The proof which we present here allows to recognize the natural connection among the sequences ann0and bnn1and the Catalan numbers Cnn0. Note that one may rewrite the identity (43) in an equivalent way.

Theorem 3.4. Forn1, the following identity holds

n+1Cn2=43an12bn,n1.E44

Proof. We write by cn=n+1Cn2=2nn2, and then we have to check the following identity

cn=43an12bn,n1,E45

where sequences ann0and bnn1are considered in the second section. Note that

p1n1q1n43an12bn=12q1np2n1an2+p3n1an38p1n1q2nbn1+q3nbn2=12an2(p1n1q2n+16Qn2n12n33+12an3p1n1q3n8Qn2n12n3n28p1n1(q2nbn12p1n1q3nbn2=p1n1q2n12an28bn1+p1n1q3n12an38bn2+962n12n32Qn22n3an2n2an3,

where we have applied the recurrence relations (30) and (36) and Lemma 3.3. By the induction method and Theorem 3.1, we have that

p1n1q1n43an12bn=p1n1q2ncn1+p1n1q3ncn2+242n12n32Qn21n34cn2

for n2. Since 42n32cn2=n12cn1for n2, we have that

242n12n32Qn21n34cn2=3p1n1Qncn1,n1.E46

Finally, we get that

p1n1q1n43an12bn=p1n1cn1q2n+q3nn1242n32+3Qn

and

cn1q2n+q3nn1242n32+3Qn=cn187n220n+142n13=cnn227n220n+142n1=cnq1n,

and we conclude the proof. □

4. Moments of squares and cubes of Catalan triangle numbers

In this section, we present some moments of squares and cubes of Catalan triangle numbers Bn,kn1,nk1and An,kn1,n+1k1, i.e.,

k=1nkmBn,kj,k=1n+12k1mAn,kj,E47

for j=2,3and mN. For m=0, these identities are shown in [14, 24]. See a unified proof in ([22], Corollary 2.2).

Proposition 4.1. Forn1, we have

1. k=1nBn,k2=C2n1,

2. k=1n+1An,k2=C2n,

3. k=1n1kBn,k2=n+12Cn.

Remark. The first values of k=1n+11kAn,k2are

0,4,32,236,1865,16080,E48

for 1n6. We are not able to find any closed formula for the general expression.

In ([13], Theorem 2), the closed expression of

Ωmnk=1nkmBn,k2,E49

is given for mN0. We present now for m017. Previously, the WZ theory was used to show them in ([12], Theorem 2.1, 2.2). See also ([1], Section 5).

Theorem 4.2. FornN,

1. i.Ω0n=C2n1Ω2n=3n2n4n3C2n1,Ω4n=15n330n2+16n2n4n34n5C2n1,Ω6n=105n5420n4+588n3356n2+96n10n4n34n54n7C2n1.

2. ii.Ω1n=2n3n+1CnCn2,Ω3n=n2n3n+1CnCn2,Ω5n=n3n25n+1n+1CnCn2,Ω7n=n6nn121n+1CnCn2.

In ([13], Theorem 4, 8), the closed expression of

Ψmnk=1n2k1mAn,k2,E50

is obtained for mN0. Now, we present the particular cases for m017in the next theorem.

Theorem 4.3. FornN,

1. i.Ψ0n=C2n,Ψ2n=1+4n+12n24n1C2n,Ψ4n=316n104n2+240n44n14n3C2n,Ψ6n=15+92n+1116n2+2080n34368n46720n5+6720n64n14n34n5C2n.

2. ii.Ψ1n=n+1CnCn14n2,Ψ3n=n+1CnCn116n22,Ψ5n=n+1CnCn196n3+32n24n2,Ψ7n=n+1CnCn11536n51536n4960n3160n2+20n+62n3.

Integer sequences of numbers ann0and bnn1were treated in Section 3. They play a very interesting role to describe the sums of cubes of Catalan triangle numbers, as the next result shows. See proofs and more details in ([22], Section 3).

Theorem 4.4. Forn1, we have

1. k=0nBn,k3=n+12Cnbn,

2. k=1n+1An,k3=n+1Cn2n+1Cn23an,

3. k=1n+11kAn,k3=n12n+12nn3nn.

Remark. To check k=1nBn,k3in Theorem 4.4 (i), we need to show the identity:

2nn2=k=0n3n2kn2n1kn12,n1,E51

see ([22], Theorem 3.3). In Theorem 3.4, we have presented an alternative proof of this identity.

The first values of k=1n1kBn,k3are

1,7,62,215,17332,945342,E52

for 1n6. We are not able to find any closed formula for the general expression.

5. Conclusions and future developments

In this paper we have studied in detail

k=1nkmBn,kj,k=1n+12k1mAn,kj,E53

for nNand several values of jN. The main objective is to give a closed formula where a factor is n+12Cn, n+1Cn, C2n, or other Catalan number, for example, in Theorem 2.1, Proposition 4.1, and Theorems 4.2 and 4.3. These results complete previous studies for m=0,1and 2. In the case of j=3and m=0, some known integer sequences ann0and bnn1appear in Theorem 4.4. Also the alternating sums

k=1n1kBn,kj,k=1n+11kAn,kj,E54

are considered in Theorem 2.2, Proposition 4.1 (iii), and Proposition 4.4 (iii).

To show these identities, we have combined the analytic proofs and the WZ theory which is useful to show combinatorial identities. Our results allow continuing this research, and future developments could be made.

In the following, we present some conjectures about new identities in Catalan triangle numbers. These conjectures are about the properties of divisibility of sums and alternating sums of powers of Catalan triangle numbers Bn,kand An,k. The factors which we consider are n+12Cnand n+1Cn.

Conjecture 5.1. After Theorem 2.1 (i) and (ii), it is natural to conjecture that for m,nN

Δ2mn=n+12CnnPm1n,E55
Δ2m1n=2nm1Qm1n,E56

where Pm1and Qm1are polynomials of integer coefficients at degree at most m1.

Conjecture 5.2. After Theorem 2.1 (iii) and (iv), it is also natural to conjecture that for m,nN,

Λ2mn=n+1CnRm1n,E57
Λ2m1n=22nSm1n,E58

where Rm1and Sm1are polynomials of integer coefficients at degree at most m1.

Conjecture 5.3. In Table 1, we present the moments k=1nkmBn,k3for m1,2,3,4and n1,2,3,4,5. Then we conjecture that the factor n+12Cndivides k=0nk2mBn,k3for m,nN.

nk=1nkBn,k3k=1nk2Bn,k3k=1nk3Bn,k3k=1nk4Bn,k3
11111
210121624
32563906641230
4888415,68030,59264,400
5356,374701,8201,523,1583,569,580

Table 1.

Moments of cubes of Bn,k.

Conjecture 5.4. In Table 2, we give the moments k=1n+12k1mAn,k3for m1,2,3,4and n1,2,3,4,5. We conjecture that the factor n+1Cndivides k=0n+12k12mAn,k3for m,nN.

nk=1n+12k1An,k3k=1n+12k12An,k3k=1n+12k13An,k3k=1n+12k14An,k3
14102882
2942768622820
32944986035,776139,700
4111,010417,2001,713,8267,610,960
54,677,16019,342,00887,730,360430,535,448

Table 2.

Moments of cubes of An,k.

Conjecture 5.5. We give the moments k=1nkmBn,k4for m1,2,3,4and n1,2,3,4,5in Table 3. Then we conjecture that the factor n+12Cndivides k=0nk2m1Bn,k4for m,nN.

nk=1nkBn,k4k=1nk2Bn,k4k=1nk3Bn,k4k=1nk4Bn,k4
11111
218202432
31140165827004802
4119,140203,760380,800758,304
515,339,24029,193,89060,190,200132,142,274

Table 3.

Moments of the fourth power of Bn,k.

Conjecture 5.6. In Table 4, we give the moments k=0n+12k1mAn,k4for m1,2,3,4and n1,2,3,4,5. We conjecture that n+1Cndivides k=0n+12k12m1An,k4for m,nN.

nk=1n+12k1An,k4k=1n+12k12An,k4k=1n+12k13An,k4k=1n+12k14An,k4
14102882
226477023287202
323,44075,348256,240925,092
42,699,2009,688,05037,458,400155,596,914
5368,708,2561,458,679,5086,249,158,49628,738,974,308

Table 4.

Moments of the fourth power of An,k.

Conjecture 5.7. The sums of alternating powers of Catalan triangle numbers Bn,kand An,k,

k=1n1kBn,kj,andk=1n+11kAn,kj,E59

have been considered in this paper: in Theorem 2.2 (i) and (ii) for j=1, in Proposition 4.1 (iii) for j=2, and in Theorem 4.4 (iii) for j=3. In Table 5, we present the alternating sums of the fourth and fifth powers of Catalan triangle numbers. All these results join to conjecture that the factor n+12Cndivides k=0n1kBn,k2mfor m,nNand n+1Cndivides k=0n+11kAn,k2m1for m,nN.

nk=1n1kBn,k4k=1n+11kAn,k4k=1n1kBn,k5k=1n+11kAn,k5
11010
2156431210
33705312210252,800
41295418,640777513,489,350
51,669,37432,351,744109,796,5963,453,624,720

Table 5.

Sums of alternating powers of Bn,kand An,k.

Finally we give some general comments and ideas which could be followed in future works.

1. The generating formula (1) allows an interesting way to show some combinatorial identities in an analytic way.

2. Alternating moments of Catalan triangle numbers Bn,kand An,k, i.e.,

k=1nkmBn,kj,k=1n+12k1mAn,kj,(60)

are a new interesting research which could be considered in later articles, compared with ([24], Theorem 2.3).

3. In a similar way, weight moments of Catalan triangle numbers Bn,kand An,k,

k=1nakBn,kj,k=1n+1bkAn,kj,j,nN,(61)

are worth studying them for some a,bN, compared with ([9], Theorem 1.1).

Acknowledgments

P.J. Miana has been partially supported by Project MTM2016-77710-P, DGI-FEDER, of the MCYTS and Project E26-17R, D.G. Aragón, Spain. Natalia Romero has been partially supported by the Spanish Ministry of Science, Innovation and Universities, Project PGC2018-095896-B-C21.

Appendix

In this appendix, we present some tables of powers of Catalan triangle numbers Bn,kand An,k. As we have mentioned above, they are used to conjecture some statements in the Section 5.

How to cite and reference

Cite this chapter Copy to clipboard

Pedro J. Miana and Natalia Romero (April 22nd 2020). Moments of Catalan Triangle Numbers [Online First], IntechOpen, DOI: 10.5772/intechopen.92046. Available from: