Open access peer-reviewed chapter

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

Downloaded: 81


In this chapter, we consider the Catalan numbers, C n = 1 n + 1 2 n n , and two of their generalizations, Catalan triangle numbers, B n , k and A n , 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 = 1 n k m B n , k j , ∑ k = 1 n + 1 2 k − 1 m A n , k j , 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.


  • Catalan numbers
  • combinatorial identities
  • binomial coefficients
  • moments

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


The generating formula for Catalan numbers is


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

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


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


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


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


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.,


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:


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:


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


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


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:


(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


for n1; see also ([22], Section 3).

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


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:


which are given by


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

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


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


appear as the entries of this other Catalan triangle,


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




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


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. For nN, 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. For n1, 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:


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. For n1,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


3. Sums of squares of combinatorial numbers

We consider the sequence of integer numbers defined by


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:


where polynomials pii1,2,3are defined by


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

Theorem 3.1. For n1, the following identity holds


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


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


and we conclude the proof. □

Now we consider this second sequence of integer numbers defined by


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:


where polynomials qii1,2,3are defined by


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

Theorem 3.2. For n1, the following identity holds


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


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. For n1, the following two identities hold


where Qn147n4546n3+666n2293n+34.

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


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. For n1, the following identity holds


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


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


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


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


Finally, we get that




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.,


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. For n1, 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


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

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


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. For nN,

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

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

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


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

Theorem 4.3. For nN,

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

  2. Ψ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. For n1, 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:


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


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


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


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


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,


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.


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.


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.


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.


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,


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.


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.,


    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,


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


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.

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.

Additional information

Mathematics Subject Classification: 05A19; 05A10; 11B65, 11B75

© 2020 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Pedro J. Miana and Natalia Romero (April 22nd 2020). Moments of Catalan Triangle Numbers, Number Theory and Its Applications, Cheon Seoung Ryoo, IntechOpen, DOI: 10.5772/intechopen.92046. Available from:

chapter statistics

81total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Modular Sumset Labelling of Graphs

By Sudev Naduvath

Related Book

First chapter

Cyclotomic and Littlewood Polynomials Associated to Algebras

By José-Antonio de la Peña

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us