Open access peer-reviewed chapter

Moments of Catalan Triangle Numbers

Written By

Pedro J. Miana and Natalia Romero

Reviewed: 09 March 2020 Published: 22 April 2020

DOI: 10.5772/intechopen.92046

From the Edited Volume

Number Theory and Its Applications

Edited by Cheon Seoung Ryoo

Chapter metrics overview

764 Chapter Downloads

View Full Metrics

Abstract

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.

Keywords

  • Catalan numbers
  • combinatorial identities
  • binomial coefficients
  • moments

1. Introduction

After the binomial coefficients, the well-known Catalan numbers C n n 0 are 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 + 2 sides; or, the number of ways that 2 n people 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 C 0 = 1 and C n = i = 0 n 1 C i C n 1 i for n 1 ; the first terms in this sequence are

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

The generating formula for Catalan numbers is

C x 1 1 4 x 2 x = n 0 C n x n , 0 < x < 1 / 14 E2

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

Catalan triangle numbers B n , k n , k 1 and A n , k n , k 1 are defined by

B n , k k n 2 n n k , A n , k 2 k 1 2 n + 1 2 n + 1 n + 1 k n , k N , k n + 1 . E3

Notice that B n , 1 = A n , 1 = C n . In [14], Shapiro introduced Catalan triangles whose entries are given by the coefficients

n k B n , k x n = x k C 2 k x , E4

see a more general approach in [10].

Although the numbers B n , k (and also A n , k ) are not as well-known as Catalan numbers, they have also several applications, for example, B n , k is the number of walks of n steps, 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 C m , k m 1 , k 0 , given by

C m , k m 2 k m m k . E5

These combinatorial numbers C m , k m 1 , k 0 are suitable rearrangements of the known ballot numbers a m , k with a m , k = k + 1 m + 1 2 m k m for m 0 and 0 k m , i.e.,

a m , k = C 2 m + 1 k , m k , C m , k = a m k 1 , m 2 k 1 , E6

see example [21]. Note that C 2 n , n k = B n , k and also C 2 n + 1 , n + 1 k = A n , 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 + 1 k = j = 0 k C n , j 2 k j . E7

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

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

k = 1 n k m B n , k j , k = 1 n + 1 2 k 1 m A n , k j , E8

for j , n N and m N 0 . In previous papers, the authors have considered some particular cases of these sums: for j = 1 and m = 0 in [14], for j = 2 in [12, 13], and for j = 3 and m = 0 in [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 = 1 in Section 2 and for j = 2 and for some cases of j = 3 in 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 = 1 n 1 k k 2 B n , k 2 = n n 2 2 n 1 C n 1 , n 1 . E9

In this paper, we treat k = 1 n 1 k k 2 B n , k j and k = 1 n + 1 1 k k 2 A n , k j for j 1,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 a n n 0 and b n n 1 where

a n k = 0 n n + k n 2 , b n k = 0 n n k n n 1 + k n 1 2 n N , E10

and Catalan numbers C n n 0 . In Theorems 3.1 and 3.2, we show that for n 1 ,

2 2 n + 1 a n na n 1 = 21 n + 8 n + 1 2 2 C n 2 , E11
2 2 n + 1 b n + 1 nb n = 7 n 2 + 8 n + 2 C n 2 . E12

Lemma 3.3 shows that sequences a n n 1 and b n n 1 are 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 + 1 C n 2 = 4 3 a n 1 2 b n , n 1 , 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 = 0 n B n , k 3 = n + 1 2 C n b n , k = 1 n + 1 A n , k 3 = n + 1 C n 2 n + 1 C n 2 3 a n , E14

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

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

k = 1 n k 2 m B n , k = n + 1 2 C n nP m 1 n , E15
k = 1 n k 2 m 1 B n , k = 2 n m 1 Q m 1 n , E16
k = 1 n + 1 k 2 m A n , k = n + 1 C n R m 1 n , E17
k = 1 n + 1 k 2 m 1 A n , k = 2 2 n S m 1 n , E18

where P m 1 , Q m 1 , R m 1 and S m 1 are polynomials of integer coefficients at the degree at most m 1 (Conjectures 5.1 and 5.2). In Conjecture 5.3, we state that the factor n + 1 2 C n could divide k = 0 n k 2 m B n , k 3 for m , n N ; similarly the factor n + 1 C n might divide k = 0 n + 1 2 k 1 2 m A n , k 3 for m , n N (Conjecture 5.4). Similar conjectures about moments of fourth order and alternating sums are also presented in Conjectures 5.5–5.7.

Advertisement

2. Sums and alternating sums of Catalan triangle numbers

Catalan triangle numbers B n , k n 1 , 1 k n were introduced in [14]. These combinatorial numbers B n , k are the entries of the following Catalan triangle:

E19

which are given by

B n , k k n 2 n n k , n , k N , k n . E20

Notice that B n , 1 = C n and B n , n = 1 n 1 .

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

k = 1 i B n , k B n , n + k i n + 2 k i = n + 1 C n 2 n 1 i 1 , i n , 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 B n , k n k 1 have 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 A n , k defined as follows

A n , k 2 k 1 2 n + 1 2 n + 1 n + 1 k , n , k N , k n + 1 , E22

appear as the entries of this other Catalan triangle,

E23

which is considered in [13]. Notice that A n , 1 = C n and C 2 n + 1 , n k + 1 = A n , k for k n + 1 .

Entries B n , k and A n , k of the above two particular Catalan triangles satisfy the recurrence relations

B n , k = B n 1 , k 1 + 2 B n 1 , k + B n 1 , k + 1 , k 2 , E24

and

A n , k = A n 1 , k 1 + 2 A n 1 , k + A n 1 , k + 1 , k 2 . E25

For m N 0 , we define the moments of order m by the sum

Δ m n k = 0 n k m B n , k , Λ m n k = 0 n + 1 2 k 1 m A n , k , n 1 . E26

As it was shown in [14], the values of the sums (or moments of order 0 ) of B n , k and A n , k are 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 m 0 1 7 .

Theorem 2.1. For n N , the following identities hold:

  1. Δ 0 n = n + 1 2 C n , Δ 2 n = n n + 1 2 C n , Δ 4 n = n 2 n 1 n + 1 2 C n , Δ 6 n = n 6 n 2 + 4 n + 1 n + 1 2 C n .

  2. Δ 1 n = 2 2 n 2 , Δ 3 n = 2 2 n 3 3 n 1 , Δ 5 n = 2 2 n 4 15 n n 1 + 2 , Δ 7 n = 2 2 n 5 105 n 3 210 n 2 + 147 n 34 .

  3. Λ 0 n = n + 1 C n , Λ 2 n = n + 1 C n 4 n + 1 , Λ 4 n = n + 1 C n 32 n 2 + 8 n + 1 , Λ 6 n = n + 1 C n 384 n 3 32 n 2 + 12 n + 1 .

  4. Λ 1 n = 2 2 n , Λ 3 n = 2 2 n 6 n + 1 , Λ 5 n = 2 2 n 60 n 2 + 1 , Λ 7 n = 2 2 n 840 n 3 420 n 2 + 126 n + 1 .

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

Theorem 2.2. For n 1 , we have

  1. k = 1 n 1 k B n , k = C n 1 ,

  2. k = 1 n + 1 1 k A n , k = 0 .

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

H n = k = 1 n 1 k , n N . E27

A deep treatment of closed formulas for the sums of the form k = 1 n a k H k is 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 H n n 1 are given.

Corollary 2.3. For n 1 , we have

  1. k = 0 n 1 B n , k H n k = 2 nH n 1 n + 1 4 n C n 2 2 n 1 1 2 n ,

  2. k = 1 n A n , k H n k + 1 = H n n + 1 C n 2 2 n 1 2 n + 1 .

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

k = 0 n 1 B n , k 2 H n k , and k = 1 n A n , k 2 H n k + 1 . E28
Advertisement

3. Sums of squares of combinatorial numbers

We consider the sequence of integer numbers defined by

a n k = 0 n n + k n 2 , n N 0 . E29

Note that a 0 = 1 , a 1 = 5 , a 2 = 46 , a 3 = 517 , a 4 = 6376 , etc. This sequence appears indexed in the On-Line Encyclopedia of Integer Sequences by N.J.A. Sloane [16] with the reference A 112029 . V. Kotesovec in 2012 proved the following recurrence relation:

p 1 n a n = p 2 n a n 1 + p 3 n a n 2 , n 2 , E30

where polynomials p i i 1,2,3 are defined by

p 1 n 2 2 n + 1 21 n 13 n 2 , E31
p 2 n 1365 n 4 1517 n 3 + 240 n 2 + 216 n 64 , E32
p 3 n 4 n 1 2 n 1 2 21 n + 8 . E33

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

Theorem 3.1. For n 1 , the following identity holds

2 2 n + 1 a n na n 1 = 21 n + 8 n + 1 2 2 C n 2 . E34

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

21 n + 8 n + 2 2 2 C n + 1 2 = 21 n + 8 4 2 n + 1 2 n + 1 2 2 C n 2 = 4 2 n + 1 2 2 2 n + 1 a n na n 1 ,

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

21 n + 8 21 n + 29 n + 2 2 2 C n + 1 = 8 21 n + 29 2 n + 1 3 a n + p 3 n + 1 a n 1 = p 1 n + 1 a n + 1 + 8 21 n + 29 2 n + 1 3 p 2 n + 1 a n = 2 2 n + 3 21 n + 8 n + 1 2 a n + 1 21 n + 8 n + 1 3 a n = 21 n + 8 n + 1 2 2 2 n + 3 a n + 1 n + 1 a n ,

and we conclude the proof. □

Now we consider this second sequence of integer numbers defined by

b n k = 0 n k n 2 n k 1 n 1 2 = k = 0 n n k n n 1 + k n 1 2 , n N . E35

Note that b 1 = 1 , b 2 = 3 , b 3 = 19 , b 4 = 163 , b 5 = 1625 , etc. This sequence also appears indexed in the On-Line Encyclopedia of Integer Sequences by N.J.A. Sloane [16] with the reference A 183069 , and V. Kotesovec proved the following recurrence relation:

q 1 n b n = q 2 n b n 1 + q 3 n b n 2 , n 3 , E36

where polynomials q i i 1,2,3 are defined by

q 1 n 2 n 2 2 n 1 7 n 2 20 n + 14 , E37
q 2 n 455 n 5 2427 n 4 + 4850 n 3 4406 n 2 + 1728 n 216 , E38
q 3 n 4 n 2 2 n 3 2 7 n 2 6 n + 1 . E39

In a similar way, we obtain an identity which relates numbers b n n 1 to the square of Catalan numbers.

Theorem 3.2. For n 1 , the following identity holds

2 2 n + 1 b n + 1 nb n = 7 n 2 + 8 n + 2 C n 2 . 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 + 2 C n + 1 = 2 2 n + 1 C n , we have that

7 n 2 + 8 n + 2 7 n 2 + 22 n + 17 n + 2 2 C n + 1 2 = 7 n 2 + 8 n + 2 7 n 2 + 22 n + 17 4 2 n + 1 2 C n 2 = 4 2 n + 1 2 7 n 2 + 22 n + 17 2 2 n + 1 b n + 1 nb n = 8 2 n + 1 3 7 n 2 + 22 n + 17 b n + 1 + q 3 n + 2 b n = q 1 n + 2 b n + 2 + 8 2 n + 1 3 7 n 2 + 22 n + 17 q 2 n + 2 b n + 1 = 2 7 n 2 + 8 n + 2 2 n + 3 n + 2 2 b n + 2 7 n 2 + 8 n + 2 n + 2 2 n + 1 b n ,

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

Sequences a n n 0 and b n n 1 are jointly connected as the next lemma shows. The proof is left to the reader.

Lemma 3.3. For n 1 , the following two identities hold

q 1 n q 3 n p 1 n 1 p 3 n 1 = 8 Q n 2 n 1 2 n 3 2 n 2 ; E41
q 1 n q 2 n p 1 n 1 p 2 n 1 = 16 Q n 2 n 1 2 n 3 3 , E42

where Q n 147 n 4 546 n 3 + 666 n 2 293 n + 34 .

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

2 n n 2 = k = 0 n 3 n 2 k n 2 n 1 k n 1 2 , 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 a n n 0 and b n n 1 and the Catalan numbers C n n 0 . Note that one may rewrite the identity (43) in an equivalent way.

Theorem 3.4. For n 1 , the following identity holds

n + 1 C n 2 = 4 3 a n 1 2 b n , n 1 . E44

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

c n = 4 3 a n 1 2 b n , n 1 , E45

where sequences a n n 0 and b n n 1 are considered in the second section. Note that

p 1 n 1 q 1 n 4 3 a n 1 2 b n = 12 q 1 n p 2 n 1 a n 2 + p 3 n 1 a n 3 8 p 1 n 1 q 2 n b n 1 + q 3 n b n 2 = 12 a n 2 ( p 1 n 1 q 2 n + 16 Q n 2 n 1 2 n 3 3 + 12 a n 3 p 1 n 1 q 3 n 8 Q n 2 n 1 2 n 3 n 2 8 p 1 n 1 ( q 2 n b n 1 2 p 1 n 1 q 3 n b n 2 = p 1 n 1 q 2 n 12 a n 2 8 b n 1 + p 1 n 1 q 3 n 12 a n 3 8 b n 2 + 96 2 n 1 2 n 3 2 Q n 2 2 n 3 a n 2 n 2 a n 3 ,

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

p 1 n 1 q 1 n 4 3 a n 1 2 b n = p 1 n 1 q 2 n c n 1 + p 1 n 1 q 3 n c n 2 + 24 2 n 1 2 n 3 2 Q n 21 n 34 c n 2

for n 2 . Since 4 2 n 3 2 c n 2 = n 1 2 c n 1 for n 2 , we have that

24 2 n 1 2 n 3 2 Q n 21 n 34 c n 2 = 3 p 1 n 1 Q n c n 1 , n 1 . E46

Finally, we get that

p 1 n 1 q 1 n 4 3 a n 1 2 b n = p 1 n 1 c n 1 q 2 n + q 3 n n 1 2 4 2 n 3 2 + 3 Q n

and

c n 1 q 2 n + q 3 n n 1 2 4 2 n 3 2 + 3 Q n = c n 1 8 7 n 2 20 n + 14 2 n 1 3 = c n n 2 2 7 n 2 20 n + 14 2 n 1 = c n q 1 n ,

and we conclude the proof. □

Advertisement

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 B n , k n 1 , n k 1 and A n , k n 1 , n + 1 k 1 , i.e.,

k = 1 n k m B n , k j , k = 1 n + 1 2 k 1 m A n , k j , E47

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

Proposition 4.1. For n 1 , we have

  1. k = 1 n B n , k 2 = C 2 n 1 ,

  2. k = 1 n + 1 A n , k 2 = C 2 n ,

  3. k = 1 n 1 k B n , k 2 = n + 1 2 C n .

Remark. The first values of k = 1 n + 1 1 k A n , k 2 are

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

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

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

Ω m n k = 1 n k m B n , k 2 , E49

is given for m N 0 . We present now for m 0 1 7 . 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 n N ,

  1. Ω 0 n = C 2 n 1 Ω 2 n = 3 n 2 n 4 n 3 C 2 n 1 , Ω 4 n = 15 n 3 30 n 2 + 16 n 2 n 4 n 3 4 n 5 C 2 n 1 , Ω 6 n = 105 n 5 420 n 4 + 588 n 3 356 n 2 + 96 n 10 n 4 n 3 4 n 5 4 n 7 C 2 n 1 .

  2. Ω 1 n = 2 n 3 n + 1 C n C n 2 , Ω 3 n = n 2 n 3 n + 1 C n C n 2 , Ω 5 n = n 3 n 2 5 n + 1 n + 1 C n C n 2 , Ω 7 n = n 6 n n 1 2 1 n + 1 C n C n 2 .

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

Ψ m n k = 1 n 2 k 1 m A n , k 2 , E50

is obtained for m N 0 . Now, we present the particular cases for m 0 1 7 in the next theorem.

Theorem 4.3. For n N ,

  1. Ψ 0 n = C 2 n , Ψ 2 n = 1 + 4 n + 12 n 2 4 n 1 C 2 n , Ψ 4 n = 3 16 n 104 n 2 + 240 n 4 4 n 1 4 n 3 C 2 n , Ψ 6 n = 15 + 92 n + 1116 n 2 + 2080 n 3 4368 n 4 6720 n 5 + 6720 n 6 4 n 1 4 n 3 4 n 5 C 2 n .

  2. Ψ 1 n = n + 1 C n C n 1 4 n 2 , Ψ 3 n = n + 1 C n C n 1 16 n 2 2 , Ψ 5 n = n + 1 C n C n 1 96 n 3 + 32 n 2 4 n 2 , Ψ 7 n = n + 1 C n C n 1 1536 n 5 1536 n 4 960 n 3 160 n 2 + 20 n + 6 2 n 3 .

Integer sequences of numbers a n n 0 and b n n 1 were 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 n 1 , we have

  1. k = 0 n B n , k 3 = n + 1 2 C n b n ,

  2. k = 1 n + 1 A n , k 3 = n + 1 C n 2 n + 1 C n 2 3 a n ,

  3. k = 1 n + 1 1 k A n , k 3 = n 1 2 n + 1 2 n n 3 n n .

Remark. To check k = 1 n B n , k 3 in Theorem 4.4 (i), we need to show the identity:

2 n n 2 = k = 0 n 3 n 2 k n 2 n 1 k n 1 2 , n 1 , E51

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

The first values of k = 1 n 1 k B n , k 3 are

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

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

Advertisement

5. Conclusions and future developments

In this paper we have studied in detail

k = 1 n k m B n , k j , k = 1 n + 1 2 k 1 m A n , k j , E53

for n N and several values of j N . The main objective is to give a closed formula where a factor is n + 1 2 C n , n + 1 C n , C 2 n , 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 , 1 and 2 . In the case of j = 3 and m = 0 , some known integer sequences a n n 0 and b n n 1 appear in Theorem 4.4. Also the alternating sums

k = 1 n 1 k B n , k j , k = 1 n + 1 1 k A n , k j , 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 B n , k and A n , k . The factors which we consider are n + 1 2 C n and n + 1 C n .

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

Δ 2 m n = n + 1 2 C n nP m 1 n , E55
Δ 2 m 1 n = 2 n m 1 Q m 1 n , E56

where P m 1 and Q m 1 are polynomials of integer coefficients at degree at most m 1 .

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

Λ 2 m n = n + 1 C n R m 1 n , E57
Λ 2 m 1 n = 2 2 n S m 1 n , E58

where R m 1 and S m 1 are polynomials of integer coefficients at degree at most m 1 .

Conjecture 5.3. In Table 1 , we present the moments k = 1 n k m B n , k 3 for m 1,2,3,4 and n 1,2,3,4,5 . Then we conjecture that the factor n + 1 2 C n divides k = 0 n k 2 m B n , k 3 for m , n N .

n k = 1 n kB n , k 3 k = 1 n k 2 B n , k 3 k = 1 n k 3 B n , k 3 k = 1 n k 4 B n , k 3
1 1 1 1 1
2 10 12 16 24
3 256 390 664 1230
4 8884 15 , 680 30 , 592 64 , 400
5 356 , 374 701 , 820 1 , 523 , 158 3 , 569 , 580

Table 1.

Moments of cubes of B n , k .

Conjecture 5.4. In Table 2 , we give the moments k = 1 n + 1 2 k 1 m A n , k 3 for m 1,2,3,4 and n 1,2,3,4,5 . We conjecture that the factor n + 1 C n divides k = 0 n + 1 2 k 1 2 m A n , k 3 for m , n N .

n k = 1 n + 1 2 k 1 A n , k 3 k = 1 n + 1 2 k 1 2 A n , k 3 k = 1 n + 1 2 k 1 3 A n , k 3 k = 1 n + 1 2 k 1 4 A n , k 3
1 4 10 28 82
2 94 276 862 2820
3 2944 9860 35 , 776 139 , 700
4 111 , 010 417 , 200 1 , 713 , 826 7 , 610 , 960
5 4 , 677 , 160 19 , 342 , 008 87 , 730 , 360 430 , 535 , 448

Table 2.

Moments of cubes of A n , k .

Conjecture 5.5. We give the moments k = 1 n k m B n , k 4 for m 1,2,3,4 and n 1,2,3,4,5 in Table 3 . Then we conjecture that the factor n + 1 2 C n divides k = 0 n k 2 m 1 B n , k 4 for m , n N .

n k = 1 n kB n , k 4 k = 1 n k 2 B n , k 4 k = 1 n k 3 B n , k 4 k = 1 n k 4 B n , k 4
1 1 1 1 1
2 18 20 24 32
3 1140 1658 2700 4802
4 119 , 140 203 , 760 380 , 800 758 , 304
5 15 , 339 , 240 29 , 193 , 890 60 , 190 , 200 132 , 142 , 274

Table 3.

Moments of the fourth power of B n , k .

Conjecture 5.6. In Table 4 , we give the moments k = 0 n + 1 2 k 1 m A n , k 4 for m 1,2,3,4 and n 1,2,3,4,5 . We conjecture that n + 1 C n divides k = 0 n + 1 2 k 1 2 m 1 A n , k 4 for m , n N .

n k = 1 n + 1 2 k 1 A n , k 4 k = 1 n + 1 2 k 1 2 A n , k 4 k = 1 n + 1 2 k 1 3 A n , k 4 k = 1 n + 1 2 k 1 4 A n , k 4
1 4 10 28 82
2 264 770 2328 7202
3 23 , 440 75 , 348 256 , 240 925 , 092
4 2 , 699 , 200 9 , 688 , 050 37 , 458 , 400 155 , 596 , 914
5 368 , 708 , 256 1 , 458 , 679 , 508 6 , 249 , 158 , 496 28 , 738 , 974 , 308

Table 4.

Moments of the fourth power of A n , k .

Conjecture 5.7. The sums of alternating powers of Catalan triangle numbers B n , k and A n , k ,

k = 1 n 1 k B n , k j , and k = 1 n + 1 1 k A n , k j , 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 + 1 2 C n divides k = 0 n 1 k B n , k 2 m for m , n N and n + 1 C n divides k = 0 n + 1 1 k A n , k 2 m 1 for m , n N .

n k = 1 n 1 k B n , k 4 k = 1 n + 1 1 k A n , k 4 k = 1 n 1 k B n , k 5 k = 1 n + 1 1 k A n , k 5
1 1 0 1 0
2 15 64 31 210
3 370 5312 2102 52 , 800
4 1295 418 , 640 7775 13 , 489 , 350
5 1 , 669 , 374 32 , 351 , 744 109 , 796 , 596 3 , 453 , 624 , 720

Table 5.

Sums of alternating powers of B n , k and A n , 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 B n , k and A n , k , i.e.,

    k = 1 n k m B n , k j , k = 1 n + 1 2 k 1 m A n , k j , (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 B n , k and A n , k ,

    k = 1 n a k B n , k j , k = 1 n + 1 b k A n , k j , j , n N , (61)

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

Advertisement

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.

Advertisement

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

Advertisement

Additional information

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

References

  1. 1. Chen X, Chu W. Moments on Catalan numbers. Journal of Mathematical Analysis and Applications. 2009;349(2):311-316
  2. 2. Chu W. A new combinatorial interpretation for generalized Catalan numbers. Discrete Mathematics. 1987;65:91-94
  3. 3. Chu W. Summation formulae involving harmonic numbers. Filomat. 2012;26(1):143-152
  4. 4. Deutsch E, Shapiro L. A survey of the Fine numbers. Discrete Mathematics. 2001;241:241-265
  5. 5. Eplett WJR. A note about the Catalan triangle. Discrete Mathematics. 1979;25:289-291
  6. 6. Guo VJW, Zeng J. Factors of binomial sums from Catalan triangle. Journal of Number Theory. 2010;130(1):172-186
  7. 7. Guo VJW, Lian X. Proofs of two conjectures on Catalan triangle numbers. Journal of Difference Equations and Applications. 2018;24(9):1473-1487
  8. 8. Gutiérrez JM, Hernández MA, Miana PJ, Romero N. New identities in the Catalan triangle. Journal of Mathematical Analysis and Applications. 2008;341(1):52-61
  9. 9. Lee K-H, Oh S-J. Catalan triangle numbers and binomial coefficients. Contemporary Mathematics. 2018;713
  10. 10. Lang W. On polynomials related to powers of the generating function of Catalans numbers. Fibonacci Quarterly. 2000;38(5):408-419
  11. 11. Hilton P, Pedersen J. Catalan numbers, their generalization and their uses. Mathematical Intelligencer. 1991;13:64-75
  12. 12. Miana PJ, Romero N. Computer proofs of new identities in the Catalan triangle. In: Biblioteca de la Revista Matemática Iberoamericana. Proc. of the “Segundas Jornadas de Teoría de Números”; Madrid. 2007. pp. 203-208
  13. 13. Miana PJ, Romero N. Moments of combinatorial and Catalan numbers. Journal of Number Theory. 2010;130(8):1876-1887
  14. 14. Shapiro LW. A Catalan triangle. Discrete Mathematics. 1976;14:83-90
  15. 15. Slavík A. Identities with squares of binomial coefficients. Ars Combinatoria. 2014;113:377-383
  16. 16. Sloane N. Available from: http://www.research.att.com/
  17. 17. Sloane N. A Handbook of Integer Sequences. New York: Academic Press; 1973
  18. 18. Spies J. Some identities involving harmonic numbers. Mathematics of Computation. 1990;55:839-863
  19. 19. Stanley RP. Enumerative Combinatorics. Vol. 2. Cambridge: Cambridge University Press; 1999
  20. 20. Stanley RP. Catalan Numbers. Cambridge: Cambridge University Press; 2015
  21. 21. Aigner M. Catalan-like numbers and determinants. Journal of Combinatorial Theory, Series A. 1999;87:33-51
  22. 22. Miana PJ, Ohtsuka H, Romero N. Sums of powers of Catalan triangle numbers. Discrete Mathematics. 2017;340(10):2388-2397
  23. 23. Brent RP, Ohtsuka H, Osborn J-AH, Prodinger H. Some binomial sums involving absolute values. Journal of Integer Sequences. 2016;19; Article 16.3.7
  24. 24. Zhang Z, Pang B. Several identities in the Catalan triangle. Indian Journal of Pure and Applied Mathematics. 2010;41(2):363-378
  25. 25. Petkovsek M, Wilf HS, Zeilberger D. A = B . Wellesley: A. K. Peters Ltd.; 1997. Available from: http://www.cis.upenn.edu/∼wilf/AeqB.html
  26. 26. Paule P, Schneider C. Computer proofs of a new family of harmonic number identities. Advances in Applied Mathematics. 2003;31(2):359-378
  27. 27. Wilf H, Zeilberger D. Rational functions certify combinatorial. Journal of the American Mathematical Society. 1990;3:147-158
  28. 28. Benjamin AT, Quinn J. Proofs that Really Count, Dolciani Mathematical Exposition 27. Washington, DC: Mathematical Association of America; 2003

Written By

Pedro J. Miana and Natalia Romero

Reviewed: 09 March 2020 Published: 22 April 2020