On the Primality of the Generalized Fuss-Catalan Numbers

Wun-Seng Chou^{∗}

Institute of Mathematics, Academia Sinica

Taipei 11529

Taiwan

macws@math.sinica.edu.tw

Tian-Xiao He Department of Mathematics Illinois Wesleyan University

Bloomington, IL 61702

USA

the@iwu.edu

Peter J.-S. Shiue^{†}

Department of Mathematical Sciences

University of Nevada, Las Vegas

Las Vegas, NV 89154-4020

USA

shiue@unlv.nevada.edu

Abstract

In this note, we determine all primes among the Fuss-Catalan numbers the generalized Fuss-Catalan numbers, the Lobb numbers, and the ballot numbers.

∗The author would like to thank Ministry of Science and Technology of Taiwan, ROC, for partial support under grant number 106-2115-M-001-003.

†This work was completed while on sabbatical leave from the University of Nevada, Las Vegas, and the author would like to thank UNLV for its support.

1 Introduction

It has long been known (see, for example, Koshy and Salmassi [9]) that the only primes among the Catalan numbers are C_{2} = 2 and C_{3} = 5. In this note we determine all the primes among the generalized Fuss-Catalan numbers, the Lobb numbers, and the ballot numbers. The definition of the generalized Fuss-Catalan numbers follows. (The definitions of the Lobb numbers and ballot numbers are given after Corollary 3 and Corollary 4, respectively.)

Let integers m ≥ 2 and n, k ≥ 1 be given. The Catalan numbers C_{n} (see \underline{A000108} in the Online Encyclopedia of Integer Sequences are defined by

C_{n} = \frac{1}{2n + 1}\binom{2n + 1}{n} = \frac{1}{n + 1}\binom{2n}{n}.  (1)

The Fuss-Catalan numbers (see \underline{A002293}, \underline{A002294}, \underline{A002295}, \underline{A002296}) F_{m}(n) are the numbers of the form

F_{m}(n) = \frac{1}{mn + 1}\binom{mn + 1}{n} = \frac{1}{(m − 1)n + 1}\binom{mn}{n}.  (2)

The generalized Fuss-Catalan numbers F_{m}(n, k) are the number of the form

F_{m}(n, k) := \frac{k}{mn + k} \binom{mn + k}{n} = \frac{k}{(m − 1)n + k} \binom{mn + k − 1}{n}.  (3)

The generalized Fuss-Catalan numbers are named after N. I. Fuss and E. C. Catalan (see [5, 6, 10, 12, 13]), and are sometimes called the k-fold Fuss-Catalan numbers or the Raney numbers. Note that F_{m}(n, 1) = F_{m}(n) and F_{2}(n) = F_{2}(n, 1) = C_{n}.

The Fuss-Catalan numbers have several combinatorial applications; see, for example, [1, 3, 4, 6, 14, 15, 16]. The generating function F_{m}(z) for the Fuss-Catalan numbers {F_{m}(n, 1)}_{n≥0}, that is,

F_{m}(z) = ∑_{n≥0} F_{m}(n, 1)z^{n},  (4)

is called the generalized binomial series by Graham, Knuth, and Patashnik [6, p. 200]. Lambert’s formula for the Taylor expansion of the powers of F_{m}(z) (see [6, (5.60)]) is

(F_{m}(z))^{k} = ∑_{n≥0} \frac{k}{mn + k} \binom{mn + k}{n}z^{n} = ∑_{n≥0} F_{m}(n, k)z^{n}  (5)

for all integers k ≥ 1. An ingenious argument in [6, p. 363] uses (5) to show that

F_{m}(z) = 1 + z(F_{m}(z))^{m}.  (6)

In this note, we are interested in the primality of the generalized Fuss-Catalan numbers, F_{m}(n, k), defined by (3).

2 Main results

Here is our main result on the primality of the generalized Fuss-Catalan numbers.

Theorem 1. Let the generalized Fuss-Catalan numbers F_{m}(n, k) be defined by (3) with m ≥ 2 and n, k ≥ 1. Then F_{m}(n, k) is not prime except in the following cases:

(a) for n ≥ 3, the only prime of the form F_{m}(n, k) is F_{2}(3, 1) = 5;

(b) for n = 2, F_{p}(2, 1) = p, where p is prime, and F_{m}(2, 2) = 2m + 1 when m = (p − 1)/2 and p is prime;

(c) for n = 1, F_{m}(1, k) = k, where k is prime.

Proof. We separate our proof into three cases as follows: (a) n ≥ 3; (b) n = 2; and (c) n = 1. First, we show that for n ≥ 3, F_{m}(n, k) is not prime except for F_{2}(3, 1) = 5. Indeed,

F_{m}(n, k) = \frac{k}{(m − 1)n + k} \binom{mn + k − 1}{n}

= \frac{k}{(m − 1)n + k} \frac{mn + k − 1}{n} \frac{mn + k − 2}{n − 1} ⋯ \frac{mn + k − (n − 1)}{2} \frac{mn + k − n}{1}
= k \frac{mn + k − 1}{n} \frac{mn + k − 2}{n − 1} ⋯ \frac{mn + k − (n − 2)}{3} \frac{mn + k − (n − 1)}{2}.  (7)

Since m ≥ 2, n ≥ 3, and k ≥ 1, we have

\frac{mn + k − 1}{n}, \frac{mn + k − 2}{n − 1}, …, \frac{mn + k − (n − 3)}{4} > 1

and

\frac{mn + k − (n − 2)}{3} ≥ 2.

Noting m ≥ 2, and combining the above estimates, we have

F_{m}(n, k) > k((m − 1)n + k + 1) ≥ mn + k − 1

for k ≥ 2. Thus,

F_{m}(n, k) > mn + k − 1  (8)

for m ≥ 2, n ≥ 3 and k ≥ 2. Note that every prime factor of F_{m}(n, k) is less than or equal to mn+k−1 because each factor of F_{m}(n, k) must be a factor of the numerator in the definition of F_{m}(n, k) (see (7)). So, if F_{m}(n, k) were a prime, we would have F_{m}(n, k) ≤ mn + k − 1, which contradicts to (8). Hence, F_{m}(n, k) is a composite number.

We have finished the discussion for the sub-case of (a) where n ≥ 3 and k ≥ 2, and we now consider the sub-case of n ≥ 3 and k = 1, i.e., the case of

F_{m}(n, 1) = \frac{1}{(m − 1)n + 1}\binom{mn}{n}.  (9)

If n = 3, then (9) gives

F_{m}(3, 1) = \frac{1}{3m − 2}\binom{3m}{3} = \frac{m(3m − 1)}{2}.  (10)

If m = 2ℓ + 1, ℓ ≥ 1, then the above equation (10) implies that F_{2ℓ+1}(3, 1) = (2ℓ + 1)(3ℓ + 1) is not a prime number. If m = 2ℓ, ℓ ≥ 1, then (10) implies that F_{2ℓ}(3, 1) = ℓ(6ℓ − 1) is not prime unless ℓ = 1. Thus, F_{2}(3, 1) = 5 is the only prime number for m ≥ 2 and n = 3. The final phase of case (a) that we have not yet considered is n ≥ 4 and k = 1. Similarly to (7), we may write (9) as

F_{m}(n, 1) = \frac{1}{(m − 1)n + 1}\binom{mn}{n}

= \frac{1}{(m − 1)n + 1} \frac{mn}{n} \frac{mn − 1}{n − 1} ⋯ \frac{mn − (n − 3)}{3} \frac{mn − (n − 2)}{2} \frac{mn − (n − 1)}{1}
= \frac{mn}{n} \frac{mn − 1}{n − 1} ⋯ \frac{mn − (n − 4)}{4} \frac{mn − (n − 3)}{3} \frac{mn − (n − 2)}{2}
> \frac{mn − (n − 4)}{4} \frac{mn − (n − 3)}{3} \frac{mn − (n − 2)}{2}
≥ 2\frac{7}{3} \frac{mn − (n − 2)}{2}
> 2(mn − (n − 2)) > mn,

where we used n ≥ 4 and m ≥ 2 so that mn − (n − 4)/4 ≥ 2 and (mn − (n − 3)/3 ≥ 7/3, and the last inequality is due to m ≥ 2. Thus, F_{m}(n, 1) is not prime when n ≥ 4 by similar arguments as those stated right after (8). This finishes the proof of case (a).

In case (b), under the assumption n = 2, we have

F_{m}(2, k) = \frac{k}{2(m − 1) + k} \binom{2m + k − 1}{2} = \frac{k(2m + k − 1)}{2} .

Thus, if k = 1 and m = p, a prime number, then F_{m}(2, k) = p is prime. If k = 2ℓ (ℓ ≥ 1), then

F_{m}(2, 2ℓ) = ℓ(2m + 2ℓ − 1)

is not prime unless ℓ = 1 and 2m + 1 is prime, or equivalently, ℓ = 1 and m = (p − 1)/2, where p is prime. If k = 2ℓ + 1, ℓ > 1, then

F_{m}(2, k) = (2ℓ + 1)(m + 1)

is not prime.

In case (c), we assume n = 1; then

F_{m}(1, k) = k

is prime exactly when k is prime. This completes the proof of the theorem.

Corollary 2. Let F_{m}(n, 1) be the Fuss-Catalan numbers defined by (2). Then none of these are prime except for F_{p}(2, 1) = p, where p is prime, and F_{2}(3, 1) = 5.

For the Catalan numbers C_{n} = F_{2}(n, 1), Koshy and Salmassi [9] use a different method to prove the following special case of Theorem 1.

Corollary 3. The Catalan numbers C_{n} are not prime except C_{2} = 2 and C_{3} = 5.

Lobb [11] defines the Lobb numbers \underline{A039599}

L_{n,m} := \frac{2m + 1}{n + m + 1}\binom{2n}{n + m}

for n ≥ m ≥ 0, which have the combinatorial interpretation as follows: L_{n,m} is the number of sequences of length 2n with n + m of the terms equal to 1 and n − m of the terms equal to −1, such that no partial sum is negative. Bobrowski et al. [2] extend Lobb numbers to the number of sequences with (k − 1)n + m terms equal to 1 and n − m terms equal to 1 − k. The extended Lobb numbers are denoted by L_{m,n}^{k} and are defined by

L_{n,m}^{k} := \frac{km + 1}{(k − 1)n + m + 1}\binom{kn}{(k − 1)n + m}.  (11)

Generalized Lobb numbers include many number sequences as special cases. For example, when k = 2, the numbers L_{n,m}^{2} are the classical Lobb numbers. When m = 0, the numbers

L_{n,0}^{k} = \frac{1}{(k − 1)n + 1}\binom{kn}{n} = F_{k}(n)

are the Fuss-Catalan numbers. When k = 2 and m = 0, the numbers

L_{n,0}^{2} = \frac{1}{n + 1}\binom{2n}{n} = C_{n}

are the classical Catalan numbers. When k = 1, the numbers

L_{n,m}^{1} = \binom{n}{m}

are the binomial coefficients. Other special cases can be seen in [7].

Equations (3) and (10) imply that

L_{n,m}^{k} = F_{k}(n − m, km + 1).  (12)

Hence, we have the inverse relationship

F_{m}(n, k) = L_{n+(k−1)/m,(k−1)/m}^{m},  (13)

which can be used to transfer the results of Theorem 1 for the generalized Fuss-Catalan numbers to corresponding results for the generalized Lobb numbers. This gives us the following corollary to Theorem 1.

Corollary 4. For integers m ≥ 2 and n, k ≥ 1, the only extended Lobb numbers which are prime are L_{1+(k−1)/m,(k−1)/m}^{m} = k, where k is prime, L_{2,0}^{p} = p, where p is prime, L_{3,0}^{2} = 5, and L_{2+1/m,1/m}^{m} = 2m + 1, where m = (p − 1)/2 and p is prime.

The Lobb numbers L_{n,m}^{2} are also related to the ballot numbers \underline{A002026} (see, for example, [6])

B(a, b) = \frac{a − b}{a + b}\binom{a + b}{a} = \frac{a − b}{a + b}\binom{a + b}{b}.  (14)

Namely, when L_{n,m}^{k} and B(a, b) are defined by (13) and (14), respectively, we have

L_{n,m}^{2} = B(n + m + 1, n − m),  (15)

or equivalently,

B(n, m) = L_{\frac{n+m−1}{2} , \frac{n−m−1}{2}}^{2} .  (16)

Hence, L_{n,m}^{2} is a ballot number. From Corollary 4, we immediately have

Corollary 5. Let the ballot numbers B(a, b) be defined by (11). Then the only prime numbers of the form B(a, b) are B(k + 1, 1) = k, where k is prime, B(3, 2) = 2, and B(4, 2) = B(4, 3) = 5.

3 Acknowledgments

The authors wish to express their sincere gratitude and appreciation to Professor Tom Brown for helpful comments and remarks that led to an revised version of the original manuscript. The authors also wish to thank the Editor-in-Chief and the anonymous referee for useful comments and suggestions.

References

[1] D. Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Mem. Amer. Math. Soc., 202 (2009).

[2] J. Bobrowski, T. X. He, and P. J.-S. Shiue, Divisibility of generalized Catalan numbers and Raney numbers, J. Comput. Anal. Appl., to appear.

[3] M. Bousquet-Mélou and G. Schaeffer, Enumeration of planar constellations, Adv. in Appl. Math. 24 (2000), 337–368.

[4] P. H. Edelman, Chain enumeration and non-crossing partitions, Discrete Math. 31 (1980), 171–180.

[5] P. J. Forrester and D.-Z. Liu, Raney distributions and random matrix theory, J. Stat. Phys. 158 (2015), 1051–1082.

[6] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[7] T. X. He, Parametric Catalan numbers and Catalan triangles, Linear Algebra Appl. 438 3 (2013), 1467–1484.

[8] T. X. He and L. Shapiro, FussCatalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Linear Algebra Appl. 532 (2017), 25–42.

[9] T. Koshy and M. Salmassi, Parity and primality of Catalan numbers, College Math. J., 37 (2006), 52–53.

[10] J.-G. Liu and R. Pego, On generating functions of Hausdorff moment sequences, Trans. Amer. Math. Soc. 368 (2016), 8499–8518.

[11] A. M. Lobb, Deriving the nth Catalan number, Math. Gaz. 83 (1999), 109–110.

[12] W. Mlotkowski, Fuss-Catalan numbers in noncommutative probability, Doc. Math. 15 (2010), 939–955.

[13] K. A. Penson and K. Życzkowski, Product of Ginibre matrices: Fuss-Catalan and Raney distributions, Phys. Rev. E, 83 (2011) 061118.

[14] J. H. Przytycki and A. S. Sikora, Polygon Dissections and Euler, Fuss, Kirkman, and Cayley Numbers, J. Combin. Theory Series A, 92 (2000), 68–76.

[15] A. Schuetz and G. Whieldon, Polygonal dissections and reversions of series, arxiv

preprint, 2014. Available at https://arxiv.org/abs/1401.7194.

[16] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2010 Mathematics Subject Classification: Primary 11B39, Secondary 11B37, 05A15. Keywords: prime number, Catalan number, Fuss-Catalan number, generalized Fuss-Catalan number, Lobb number, ballot number.

(Concerned with sequences \underline{A000108}, \underline{A002026}, \underline{A002293}, \underline{A002294}, \underline{A002295}, \underline{A002296}, and \underline{A039599}.)

Received October 13 2017; revised version received February 19 2018. Published in Journal of Integer Sequences, February 23 2018.

Return to Journal of Integer Sequences home page.