Super FiboCatalan Numbers and Their Lucas Analogues

Kendra Killpatrick Natural Science Division Pepperdine University 24255 Pacific Coast Hwy Malibu, CA 90263 USA

           kendra.killpatrick@pepperdine.edu

Abstract

Catalan first observed that the numbers S(m, n), now called the super Catalan numbers, are integers, but there is still no known combinatorial interpretation for them in general. Interpretations have been given for the case m = 2 and for S(m, m + s) for 0 ≤ s ≤ 4. In this paper, we define the super FiboCatalan numbers S(m, n)_{F} and the generalized FiboCatalan numbers. In addition, we give Lucas analogues for both of these numbers and use a result of Sagan and Tirrell to prove that the Lucas analogues are polynomials with non-negative integer coefficients. This proves that the super FiboCatalan numbers and the generalized FiboCatalan numbers are integers.

1 Introduction

The well-known Fibonacci sequence is defined recursively by F_{n} = F_{n−1} + F_{n−2} with initial conditions F_{0} = 0 and F_{1} = 1. The nth Fibonacci number, F_{n}, counts the number of tilings of a strip of length n − 1 with squares of length 1 and dominoes of length 2.

A second famous sequence, the Catalan sequence, is defined recursively by C_{n} = C_{0}C_{n−1}+ C_{1}C_{n−2} + ⋯ + C_{n−2}C_{1} + C_{n−1}C_{0} with initial conditions C_{0} = 1 and C_{1} = 1. The Catalan numbers also have an explicit formula given by

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

Since the Catalan numbers,

\frac{(2n)!}{n!(n + 1)!},

are integers, one might wonder if the numbers

\frac{(2n)!}{n!(n + 2)!}

are integers. Interestingly, these numbers are not necessarily integers, but the numbers given by

6\frac{(2n)!}{n!(n + 2)!}

do form an integer sequence. These numbers are called super ballot numbers and the sequence appears in Sloane’s On-Line Encyclopedia of Integer Sequences (OEIS) [17] \underline{A007054}. In 1992, Gessel [10] showed that, in fact, the generalized Catalan numbers,

J_{r} \frac{(2n)!}{n!(n + r + 1)!},

are integers when J_{r} is chosen to be (2r + 1)!/r!. In 2005, Gessel and Xin [11] gave a combinatorial interpretation of these numbers for r = 1 and proved

6\frac{(2n)!}{n!(n + 2)!} = 4C_{n} − C_{n+1}.

Catalan [7] observed as far back as 1874 that the numbers

S(m, n) = \frac{(2m)!(2n)!}{m!n!(m + n)!}

are integers, but there is no known combinatorial interpretation for them in general. Gessel [10] called these numbers the super Catalan numbers since S(1, n)/2 gives the Catalan number C_{n}. Note that S(2, n)/2 = 6\frac{(2n)!}{n!(n+2)!}. Allen and Gheorghiciuc [3] have given a combinatorial interpretation for S(m, n) in the case m = 2 and Gheorghiciuc and Orelowitz [12] have given a combinatorial interpretation for T (m, n) = \frac{1}{2}S(m, n) for m = 3 and m = 4. Chen and Wang [8] have given an interpretation for S(m, m + s) for 0 ≤ s ≤ 4.

1.1 FiboCatalan numbers

The fibonomial coefficients, an analogue of the binomial coefficients, are defined as

\binom{n}{k}_{F} = \frac{F_{n}!}{F_{k}!F_{n−k}!}

where F_{n}! = F_{n}F_{n−1} ⋯ F_{2}F_{1}.

In 2008, Benjamin and Plott [4] gave a combinatorial proof that the fibonomial coefficients are integers using a notion of staggered tilings. In 2010, Sagan and Savage [15] gave a combinatorial interpretation of the coefficients in terms of tilings associated with paths in a k x (n − k) rectangle. The triangle of fibonomial coefficients appears in the OEIS [17] \underline{A010048}.

First given by Lou Shapiro, the FiboCatalan number C_{n,F} is defined as

C_{n,F} = \frac{1}{F_{n+1}} \binom{2n}{n}_{F} .

Shapiro posed the question about whether these numbers are integers and, if so, whether there is a combinatorial interpretation for them. The numbers are known to be integers, since

C_{n,F} = \binom{2n − 1}{n − 2}_{F} + \binom{2n − 1}{n − 1}_{F} .

In 2020, Bennett, Carrillo, Machacek and Sagan [6] gave a combinatorial interpretation of the Lucas Catalan numbers which can be specialized to the FiboCatalan numbers. The FiboCatalan numbers appear in the OEIS [17] \underline{A003150}.

In this paper, we define the super FiboCatalan numbers

S(m, n)_{F} = \frac{F_{2m}!F_{2n}!}{F_{m}!F_{n}!F_{m+n}!}

and the generalized FiboCatalan numbers as

J_{r,F} \frac{F_{2n}!}{F_{n}!F_{n+r+1}!}

where J_{r,F} = F_{2r+1}!/F_{r}!. Note the following relationship between super FiboCatalan numbers and the generalized FiboCatalan numbers:

J_{m−1,F} \frac{F_{2n}!}{F_{n}!F_{n+m}!} = \frac{F_{2m−1}!F_{2n}!}{F_{m−1}!F_{n}!F_{n+m}!} = \frac{F_{m}}{F_{2m}} S(n, m)_{F} .

1.2 Lucas analogues

The Lucas polynomials {n} are defined in variables s and t as {0} = 0, {1} = 1 and for n ≥ 2 we have {n} = s{n − 1} + t{n − 2}. If s and t are set to be integers, then the sequence of numbers given by {n} is called a Lucas sequence. When s = t = 1, the resulting sequence is the Fibonacci sequence. The lucanomials, an analogue of the binomial coefficients, are then defined as

\left\{{n \atop k}\right\} = \frac{\{n\}!}{\{k\}!\{n − k\}!}

where {n}! = {n}{n − 1} ⋯ {2}{1}. The literature refers to these analogues as both lucanomials and Lucasnomials. We use the term lucanomial in this paper to remain consistent with the author’s previously published work. When s = t = 1, \left\{{n \atop k}\right\} gives the fibonomial coefficients \binom{n}{k}_{F}.

In 2020, Sagan and Tirrell [16] gave a new method of proving that lucanomials are polynomials with non-negative integer coefficients by defining a sequence of polynomials, P_{n}(s, t), called Lucas atoms, such that

{n} = ∏_{d|n} P_{d}(s, t).

Sagan and Tirrell [16, Thm. 1.1] then prove the following:

Theorem 1. Suppose f(s, t) = ∏_{i}{n_{i}} and g(s, t) = ∏_{j}{k_{j}} for certain n_{i}, k_{j} ∈ ℕ, and write their atomic decompositions as

f(s, t) = ∏_{d≥2} P_{d}(s, t)^{a_{d}} and g(s, t) = ∏_{d≥2} P_{d}(s, t)^{b_{d}}

for certain powers a_{d}, b_{d} ∈ ℕ. Then f(s, t)/g(s, t) is a polynomial if and only if a_{d} ≥ b_{d} for all d ≥ 2. Furthermore, in this case f(s, t)/g(s, t) has nonnegative integer coefficients.

Lucas atoms are irreducible polynomials and have been further studied by Alecci, Miska, Murru, and Romeo [1].

The Lucas analogue of the Catalan numbers is given by

C_{\{n\}} = \frac{1}{\{n + 1\}}\left\{{2n \atop n}\right\}.

More generally, given two positive integers a and b with gcd(a, b) = 1, the rational Catalan number is defined as

Cat(a, b) = \frac{1}{a + b}\binom{a + b}{a}.

In this expression, one can set a = n and b = n + 1 to obtain the usual Catalan numbers. The Lucas analogue of the rational Catalan numbers is then defined by

Cat\{a, b\} = \frac{1}{\{a + b\}}\left\{{a + b \atop a}\right\}.

The Algebraic Combinatorics Seminar at the Fields Institute [2] proved that the q-Fibonacci analogue of Cat(a, b) is a polynomial in q (a method which also works for the Lucas analogue) and in 2020, Sagan and Tirrell [16] proved that the Lucas analogue of the rational Catalan numbers is a polynomial with non-negative integer coefficients.

We can now define the Lucas analogue of the super FiboCatalan numbers as

S\{m, n\} = \frac{\{2m\}!\{2n\}!}{\{m\}!\{n\}!\{m + n\}!}

and the Lucas analogue of the generalized FiboCatalan numbers as

J_{\{r\}} \frac{\{2n\}!}{\{n\}!\{n + r + 1\}!}

where J_{\{r\}} = \frac{\{2r+1\}!}{\{r\}!}.

In Section 2 of this paper, we prove that the Lucas analogues of the super FiboCatalan numbers and the generalized FiboCatalan numbers are polynomials with non-negative integer coefficients. In addition, this proves that the super FiboCatalan numbers and the generalized FiboCatalan numbers are positive integers. In Section 3, we give a new identity involving both Fibonacci and FiboCatalan numbers and use it to provide an alternate proof that the generalized FiboCatalan numbers for r = 1 are always positive integers.

2 Results for the Lucas analogues

Following the Sagan and Tirrell [16] exposition, given a product f(s, t) of Lucas polynomials, let

log_{d} f(s, t) = the power of P_{d}(s, t) in its Lucas factorization.

Then Sagan and Tirrell [16, Lemma 3.1] prove the following:

Lemma 2. For d ≥ 2 we have

log_{d}{n}! = ⌊n/d⌋.

Furthermore, for integers m, n, d

⌊m/d⌋ + ⌊n/d⌋ ≤ ⌊(m + n)/d⌋.

Applying this Lemma to the Lucas analogues of the super FiboCatalan numbers, we have the following theorems:

Theorem 3. The Lucas analogues of the super FiboCatalan numbers,

S\{m, n\} = \frac{\{2m\}!\{2n\}!}{\{m\}!\{n\}!\{m + n\}!},

are polynomials with non-negative integer coefficients.

Proof. Applying the previous lemma gives, for d ≥ 2,

log_{d}({m}!{n}!{m + n}!) = ⌊m/d⌋ + ⌊n/d⌋ + ⌊(m + n)/d⌋

and

log_{d}({2m}!{2n}!) = ⌊2m/d⌋ + ⌊2n/d⌋.

By the Division Algorithm, let m = kd + r for 0 ≤ r < d and n = ld + s for 0 ≤ s < d. Then we can proceed by cases.

Case 1: Let r < d/2 and s < d/2. Then ⌊m/d⌋ = k, ⌊n/d⌋ = l and ⌊(m + n)/d⌋ = k + l. In this case, ⌊2m/d⌋ = 2k and ⌊2n/d⌋ = 2l; thus

log_{d}({m}!{n}!{m + n}!) = ⌊m/d⌋ + ⌊n/d⌋ + ⌊(m + n)/d⌋
= k + l + (k + l) = 2k + 2l
= ⌊2m/d⌋ + ⌊2n/d⌋
= log_{d}({2m}!{2n}!).

Case 2: Without loss of generality, let d/2 ≤ r < d and s < d/2. Then ⌊m/d⌋ = k, ⌊n/d⌋ = l and ⌊(m + n)/d⌋ ≤ k + l + 1. In this case, ⌊2m/d⌋ = 2k + 1 and ⌊2n/d⌋ = 2l; thus

log_{d}({m}!{n}!{m + n}!) = ⌊m/d⌋ + ⌊n/d⌋ + ⌊(m + n)/d⌋
≤ k + l + (k + l + 1)
= 2k + 1 + 2l
= ⌊2m/d⌋ + ⌊2n/d⌋
= log_{d}({2m}!{2n}!).

Case 3: Let d/2 ≤ r < d and d/2 ≤ s < d. Then ⌊m/d⌋ = k, ⌊n/d⌋ = l and ⌊(m+n)/d⌋ = k + l + 1. In this case, ⌊2m/d⌋ = 2k + 1 and ⌊2n/d⌋ = 2l + 1; thus

log_{d}({m}!{n}!{m + n}!) = ⌊m/d⌋ + ⌊n/d⌋ + ⌊(m + n)/d⌋
= k + l + (k + l + 1)
= 2k + 2l + 1 ≤ (2k + 1) + (2l + 1)
= ⌊2m/d⌋ + ⌊2n/d⌋
= log_{d}({2m}!{2n}!).

Theorem 4. The Lucas analogues of the generalized FiboCatalan numbers,

J_{\{r\}} \frac{\{2n\}!}{\{n\}!\{n + r + 1\}!}

where J_{\{r\}} = \frac{\{2r+1\}!}{\{r\}!}, are polynomials with non-negative integer coefficients.

log_{d}({r}!{n}!{n + r + 1}!) = ⌊r/d⌋ + ⌊n/d⌋ + ⌊(n + r + 1)/d⌋

and

log_{d}({(2r + 1)}!{2n}!) = ⌊(2r + 1)/d⌋ + ⌊2n/d⌋.

By the Division Algorithm, let r = kd + t for 0 ≤ t < d and n = ld + s for 0 ≤ s < d. Then we can again proceed by cases.

Case 1: Let t < d/2 and s < d/2. Then ⌊r/d⌋ = k, ⌊n/d⌋ = l and ⌊(n+r+1)/d⌋ = k+l+1. In this case, ⌊(2r + 1)/d⌋ = 2k + 1 and ⌊2n/d⌋ = 2l; thus

log_{d}({r}!{n}!{n + r + 1}!) = ⌊r/d⌋ + ⌊n/d⌋ + ⌊(n + r + 1)/d⌋
= k + l + (k + l + 1) = 2k + 2l + 1
= ⌊(2r + 1)/d⌋ + ⌊2n/d⌋
= log_{d}({(2r + 1)}!{2n}!).

Case 2: Without loss of generality, let d/2 ≤ t < d and s < d/2. Then ⌊r/d⌋ = k, ⌊n/d⌋ = l and ⌊(n + r + 1)/d⌋ ≤ k + l + 2. In this case, ⌊(2r + 1)/d⌋ = 2k + 2 and ⌊2n/d⌋ = 2l; thus

log_{d}({r}!{n}!{(2r + 1)}!) = ⌊r/d⌋ + ⌊n/d⌋ + ⌊(n + r + 1)/d⌋
≤ k + l + (k + l + 2)
= 2k + 2l + 2
= ⌊(2r + 1)/d⌋ + ⌊2n/d⌋
= log_{d}({(2r + 1)}!{2n}!).

Case 3: Let d/2 ≤ t < d and d/2 ≤ s < d. Then ⌊r/d⌋ = k, ⌊n/d⌋ = l and ⌊(n + r + 1)/d⌋ = k + l + 2. In this case, ⌊(2r + 1)/d⌋ = 2k + 2 and ⌊2n/d⌋ = 2l + 1; thus

log_{d}({r}!{n}!{(2r + 1)}!) = ⌊r/d⌋ + ⌊n/d⌋ + ⌊(n + r + 1)/d⌋
= k + l + (k + l + 2)
= 2k + 2l + 2 < (2k + 2) + (2l + 1)
= ⌊(2r + 1)/d⌋ + ⌊2n/d⌋
= log_{d}({(2r + 1)}!{2n}!).

Since we can recover the super FiboCatalan numbers and the generalized FiboCatalan numbers by setting s = t = 1 in the Lucas analogues for these numbers, we have the following results:

Corollary 5. The super FiboCatalan numbers

S(m, n)_{F} = \frac{F_{2m}!F_{2n}!}{F_{m}!F_{n}!F_{m+n}!}

and the generalized FiboCatalan numbers

J_{r,F} \frac{F_{2n}!}{F_{n}!F_{n+r+1}!}

where J_{r,F} = F_{2r+1}!/F_{r}! are positive integers.

3 An identity and an alternate proof

Some of the special cases of the super FiboCatalan numbers and the generalized FiboCatalan numbers reveal interesting relationships. For example, when m = 1, the super FiboCatalan numbers reduce to the FiboCatalan numbers.

S(1, n)_{F} = \frac{F_{2}!F_{(2n)}!}{F_{1}!F_{n}!F_{(n+1)}!} = \frac{1}{F_{n+1}} \frac{F_{2n}!}{F_{n}!F_{n}!} = C_{n,F}

When m = 2, we have

S(2, n)_{F} = \frac{F_{4}!F_{2n}!}{F_{2}!F_{n}!F_{(n+2)}!} = \frac{6F_{2n}!}{F_{n}!F_{(n+2)}!}.

When n = m, we have

S(m, m)_{F} = \frac{F_{2m}!F_{2m}!}{F_{m}!F_{m}!F_{2m}!} = \binom{2m}{m}_{F}

and when n = m + 1, we have

S(m, m + 1)_{F} = \frac{F_{2m}!F_{2m+2}!}{F_{m}!F_{m+1}!F_{2m+1}!} = \frac{F_{2m+2}F_{2m}!}{F_{m+1}!F_{m}!} = F_{2m+2}C_{m,F} .

The generalized FiboCatalan number for r = 0 is equal to S(1, n)_{F}, which is equal to C_{n,F}:

J_{0,F} \frac{F_{2n}!}{F_{n}!F_{n+0+1}!} = \frac{F_{1}!}{F_{0}!} \frac{F_{2n}!}{F_{n}!F_{n+1}!} = C_{n,F} = S(1, n)_{F} .

The generalized FiboCatalan number for r = 1 is given by

J_{1,F} \frac{F_{2n}!}{F_{n}!F_{n+1+1}!} = \frac{F_{3}!}{F_{1}!} \frac{F_{2n}!}{F_{n}!F_{n+2}!} = 2\frac{F_{2n}!}{F_{n}!F_{n+2}!} = \frac{1}{3}S(2, n)_{F} .

In this section, we prove a new identity involving Fibonacci and FiboCatalan numbers and use it to provide an alternate proof that the generalized FiboCatalan numbers for r = 1 are positive integers.

Lemma 6.

F_{2n}F_{n+2} − F_{2n+2}F_{n} = (−1)^{n}F_{n}.

Proof. This is a fairly well-known result for the Fibonacci numbers and the proof is a straightforward tail-swapping argument similar to those found in Benjamin and Quinn [5, p. 8]. For a more algebraic argument, see a result of Garrett [9, Thm. 1.2].

Theorem 7.

F_{2n+1}F_{2n}C_{n,F} − F_{n+1}F_{n}C_{n+1,F} = (−1)^{n}F_{n}F_{2n+1} \frac{F_{2n}!}{F_{n+2}!F_{n}!}.  (1)

Proof.

F_{2n+1}F_{2n}C_{n,F} − F_{n+1}F_{n}C_{n+1,F} = \frac{F_{2n+1}F_{2n}F_{2n}!}{F_{n+1}F_{n}!F_{n}!} − \frac{F_{n+1}F_{n}F_{2n+2}!}{F_{n+2}F_{n+1}!F_{n+1}!}

= F_{2n+1}F_{2n}F_{n+2} \frac{F_{2n}!}{F_{n+2}!F_{n}!}

− F_{2n+2}F_{2n+1}F_{n} \frac{F_{2n}!}{F_{n+2}!F_{n}!}

= F_{2n+1}[F_{2n}F_{n+2} − F_{2n+2}F_{n}]\frac{F_{2n}!}{F_{n+2}!F_{n}!}

= F_{2n+1}(−1)^{n}F_{n} \frac{F_{2n}!}{F_{n+2}!F_{n}!}

Corollary 8. For n ≥ 1,

F_{2n+1} \frac{F_{2n}!}{F_{n+2}!F_{n}!} = \frac{1}{F_{n+2}} \binom{2n + 1}{n}_{F}

is an integer.

Proof. A common Fibonacci identity states F_{2n} = F_{n}F_{n+1} + F_{n}F_{n−1}, and thus the left side of Equation (1) from Theorem 7 is equal to

F_{2n+1}[F_{n}F_{n+1} + F_{n}F_{n−1}]C_{n,F} − F_{n+1}F_{n}C_{n+1,F}

and is therefore divisible by F_{n}. Using this expression as the left side and dividing both sides of Equation (1) by F_{n} gives

F_{2n+1}F_{n+1}C_{n,F} + F_{2n+1}F_{n−1}C_{n,F} − F_{n+1}C_{n+1,F} = (−1)^{n}F_{2n+1} \frac{F_{2n}!}{F_{n+2}!F_{n}!}

= (−1)^{n} \frac{1}{F_{n+2}} \binom{2n + 1}{n}_{F} .

Since the left side of this equation is clearly an integer, we have the result.

Note that the usual binomial expression

\frac{1}{n + 2}\binom{2n + 1}{n}

is not always an integer since this number is a fraction when n = 2, for example. The sequence of numbers given by

\frac{1}{F_{n+1}} \binom{2n − 1}{n − 1}_{F}

appears in the OEIS [17] \underline{A277202} as the ratio of the FiboCatalan numbers and the Lucas numbers.

We can also rewrite the expression on the right side of Equation (1) as follows:

(−1)^{n}F_{2n+1} \frac{F_{2n}!}{F_{n+2}!F_{n}!} = (−1)^{n}F_{2n+1} \frac{1}{F_{n+2}} C_{n,F} .

It is well known that gcd(F_{n}, F_{m}) = F_{gcd(m,n)}. Thus gcd(F_{2n+1}, F_{n+2}) = F_{gcd(2n+1,n+2)}. We know gcd(2n+1, n+2) = 1 or 3. If gcd(2n+1, n+2) = 1, then gcd(F_{2n+1}, F_{n+2}) = F_{1} = 1 and so F_{n+2} divides C_{n,F}. If gcd(2n + 1, n + 2) = 3, then gcd(F_{2n+1}, F_{n+2}) = F_{3} = 2 and so F_{n+2} divides 2C_{n,F}.

Corollary 9. For n ≥ 1, the generalized FiboCatalan numbers for r = 1,

\frac{2F_{2n}!}{F_{n+2}!F_{n}!} = \frac{1}{F_{n+2}} 2C_{n,F} ,

are positive integers.

The sequence of numbers generated by \frac{(2F_{2n}!)}{(F_{n+2}!F_{n}!)} has been submitted to the OEIS [17] \underline{A372949}.

4 The Lucas analogues of the generalized FiboCatalan numbers

We have similar relationships and results for the Lucas analogues of the super FiboCatalan numbers and the generalized FiboCatalan numbers. When m = 1, the Lucas analogues of the super FiboCatalan numbers reduce to {2} times the Lucas analogues of the FiboCatalan numbers.

S\{1, n\} = \frac{\{2\}!\{2n\}!}{\{1\}!\{n\}!\{n + 1\}!} = \frac{\{2\}}{\{n + 1\}} \frac{\{2n\}!}{\{n\}!\{n\}!} = \{2\}C_{\{n\}}.

When m = 2, we have

S\{2, n\} = \frac{\{4\}!\{2n\}!}{\{2\}!\{n\}!\{n + 2\}!} = \{4\}\{3\}\frac{\{2n\}!}{\{n\}!\{n + 2\}!}.

The Lucas analogue of the generalized FiboCatalan number for r = 0 is equal to C_{{n}} which is equal to \frac{1}{\{2\}}S\{1, n\}:

J_{\{0\}} \frac{\{2n\}!}{\{n\}!\{n + 0 + 1\}!} = \frac{\{1\}!}{\{0\}!} \frac{\{2n\}!}{\{n\}!\{n + 1\}!} = C_{\{n\}} = \frac{1}{\{2\}} S\{1, n\}.

When m = n, we have

S\{m, m\} = \frac{\{2m\}!\{2m\}!}{\{m\}!\{m\}!\{2m\}!} = \left\{{2m \atop m}\right\}

and when n = m + 1, we have

S\{m, m + 1\} = \frac{\{2m\}!\{2m + 2\}!}{\{m\}!\{m + 1\}!\{2m + 1\}!} = \frac{\{2m + 2\}\{2m\}!}{\{m + 1\}!\}m\}!} = \{2m + 2\}C_{\{m\}}.

The Lucas analogue of the generalized FiboCatalan number for r = 1 is as follows:

J_{\{1\}} \frac{\{2n\}!}{\{n\}!\{n + 1 + 1\}!} = \frac{\{3\}!}{\{1\}!} \frac{\{2n\}!}{\{n\}!\{n + 2\}!}

= \{3\}!\frac{\{2n\}!}{\{n\}!\{n + 2\}!} = \frac{\{2\}}{\{4\}}S(2, n)_{F} .

Lemma 10.

{2n}{n + 2} − {2n + 2}{n} = (−1)^{n}{2}t^{n}{n}.

Proof. This proof follows the same tail-swapping argument as the argument for the Fibo-Catalan case.

Theorem 11.

{2n + 1}{2n}C_{{n}} − {n + 1}{n}C_{{n+1}}  (2)
= (−1)^{n}t^{n}\{2\}\{n\}\{2n + 1\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!}  (3)
= (−1)^{n}t^{n}\{s\}\left\{{2n + 1 \atop n + 2}\right\}.  (4)

Proof.

{2n + 1}{2n}C_{{n}} − {n + 1}{n}C_{{n+1}}

= \frac{\{2n + 1\}\{2n\}\{2n\}!}{\{n + 1\}\{n\}!\{n\}!} − \frac{\{n + 1\}\{n\}\{2n + 2\}!}{\{n + 2\}\{n + 1\}!\{n + 1\}!}

= \{2n + 1\}\{2n\}\{n + 2\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

− \{2n + 2\}\{2n + 1\}\{n\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

= \{2n + 1\}[\{2n\}\{n + 2\} − \{2n + 2\}\{n\}]\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

= \{2n + 1\}(−1)^{n}st^{n}\{n\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

= (−1)^{n}t^{n}\{2n + 1\}\{2\}\{n\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

Corollary 12. For n ≥ 1,

\{2n + 1\}\{2\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!} = \{2\}\frac{1}{\{n + 2\}}\left\{{2n + 1 \atop n}\right\}

is a polynomial with non-negative integer coefficients. Proof. It is well known that {2n} = {n}{n + 1} + t{n}{n − 1}, and thus Equation (2) from Theorem 11 is equal to

{2n + 1}[{n}{n + 1} + t{n}{n − 1}]C_{{n}} − {n + 1}{n}C_{{n+1}}

and is therefore divisible by {n}. Dividing both Equation (2) and Equation (3) by {n} gives

{2n + 1}{n + 1}C_{{n}} + t{2n + 1}{n − 1}C_{{n}} − {n + 1}C_{{n+1}}

= (−1)^{n}t^{n}\{2n + 1\}\{2\}\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

= (−1)^{n}t^{n}\{2\}\frac{1}{\{n + 2\}}\left\{{2n + 1 \atop n}\right\}.

Since the left side of this equation is a polynomial with integer coefficients, we have that

(−1)^{n}t^{n}\{2\}\frac{1}{\{n + 2\}}\left\{{2n + 1 \atop n}\right\}

is a polynomial with integer coefficients; thus,

t^{n}\{2\}\frac{1}{\{n + 2\}}\left\{{2n + 1 \atop n}\right\}

is a polynomial with non-negative integer coefficients. The lucanomial

\left\{{2n + 1 \atop n}\right\}

is a polynomial with non-negative integer coefficients. Using the facts that {n + 2} can be written as a product of irreducible Lucas atoms [16] and that t^{k} is not a Lucas atom for any k ≥ 1, we have that

\{2\}\frac{1}{\{n + 2\}}\left\{{2n + 1 \atop n}\right\} = \{2n + 1\}\frac{1}{\{n + 2\}}\{2\}C_{\{n\}}

is a polynomial with non-negative integer coefficients.

Writing {2n + 1} and {n + 2} in terms of Lucas atoms, we have

{2n + 1} = ∏_{d|2n+1} P_{d}(s, t) and {n + 2} = ∏_{d|n+2} P_{d}(s, t).

We know gcd(2n + 1, n + 2) = 1 or 3. If gcd(2n + 1, n + 2) = 1, then {n + 2} divides {2}C_{{n}}. If gcd(2n + 1, n + 2) = 3, then {n + 2} divides {3}{2}C_{{n}}, thus

\{3\}!\frac{\{2n\}!}{\{n + 2\}!\{n\}!}

is a polynomial with non-negative integer coefficients (i.e., the generalized FiboCatalan number for r = 1 is a polynomial with non-negative integer coefficients).

5 k-divisible lucanomials

Given an integer k ≥ 1, let

{n : k}! = {k}{2k} ⋯ {nk}.

The k-divisible lucanomial is defined as

\left\{{n : k \atop m : k}\right\} = \frac{\{n : k\}!}{\{m : k\}!\{n − m : k\}!}.

The natural analogues of the super Catalan numbers for the k-divisible lucanomials are then

S\{m, n : k\} = \frac{\{2m : k\}!\{2n : k\}!}{\{m : k\}!\{n : k\}!\{n + m : k\}!}.

Theorem 13. The k-divisible lucanomial analogues of the super Catalan numbers are polynomials with non-negative integer coefficients.

Proof. To begin, we note that P_{d} | {lk} when d | lk. Let g = gcd(d, k). Then k = gm_{1} for some positive integer m_{1} and d = gm_{2} for some positive integer m_{2} where gcd(m_{1}, m_{2}) = 1. Then lk = lgm_{1} and d = gm_{2}. Thus d | lk when gm_{2} | lgm_{1}, or when m_{2} | lm_{1}. Since gcd(m_{1}, m_{2}) = 1, then m_{2} | lm_{1} only when m_{2} | l. Thus the Lucas atom P_{d} divides terms at intervals of length m_{2} = d/ gcd(d, k) in {n : k}!. Let M_{d,k} = d/ gcd(d, k). Then

log_{d}{n : k}! = ⌊n/M_{d,k}⌋.

The proof now proceeds by using the Division Algorithm and cases as in the proof of the similar result for the lucanomials, so we omit the details here.

6 Open problems

The problem of finding a combinatorial interpretation of the super FiboCatalan numbers remains an interesting open problem yet will likely prove challenging given that there is a combinatorial interpretation for the super Catalan numbers in only a handful of cases.

In addition, the super Catalan numbers satisfy a number of interesting binomial identities, such as this identity of von Szily [10, p. 11]:

S(m, n) = ∑_{k∈ℤ}(−1)^{k}\binom{2m}{m + k}\binom{2n}{n + k}.

Mikić [13] recently proved the following alternating convolution formula for the super Catalan numbers:

∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}S(k, l)S(2n − k, l) = S(n, l)S(n + l, n)

for all non-negative integers n and l. Mikić [14] also proved a similar identity for the Catalan numbers:

∑_{k=0}^{2n}(−1)^{k}\binom{2n}{k}C_{k}C_{2n−k} = C_{n}\binom{2n}{n}.

We conjecture that many of these identities have analogues for the super FiboCatalan numbers and are interested in exploring these analogues in further research.

7 Acknowledgments

The author would like to thank Bruce Sagan and the participants of the MSU Combinatorics seminar for their interest in this topic and for their helpful comments on related problems.

References

[1] G. Alecci, P. Miska, N. Murru, and G. Romeo, On alternative definition of Lucas atoms and their p-adic valuations, arxiv preprint arXiv:2308.10216 [math.CO], 2023. Available

at http://arxiv.org/abs/2308.10216.

[2] F. Aliniaeifard, N. Bergeron, C. Ceballos, T. Denton, and S. Li Xiao, Algebraic Combinatorics Seminar, Fields Institute, 2013–2015, http://garsia.math.yorku.ca/

fieldseminar/.

[3] E. Allen and I. Gheorghiciuc, A weighted interpretation for the super Catalan numbers, J. Integer Sequences 17 (2014), Article 14.10.7.

[4] A. Benjamin and S. Plott, A combinatorial approach to Fibonomial coefficients, Fibonacci Quart. 46/47 (2008/2009), 7–9.

[5] A. Benjamin and J. Quinn, Proofs That Really Count, Mathematical Association of America, 2003.

[6] C. Bennett, J. Carrillo, J. Machacek, and B. Sagan, Combinatorial interpretations of Lucas analogues of binomial coefficients and Catalan numbers, Ann. Comb. 24 (2020), 503–530.

[7] E. Catalan, Question 1135, Nouvelles Annales de Mathématiques (2) 13 (1874), 207.

[8] X. Chen and J. Wang, The super Catalan numbers S(m, m+s) for s ≤ 4, arxiv preprint arXiv:1208.4196 [math.CO], 2012. Available at http://arxiv.org/abs/1208.4196.

[9] K. Garrett, A determinant identity that implies Rogers-Ramanujan, Electron. J. Combin. 12 (2005), #R35.

[10] I. Gessel, Super ballot numbers, J. Symbolic. Comput. 14 (1992), 179–194.

[11] I. Gessel and G. Xin, A combinatorial interpretation of the numbers 6(2n)!/n!(n + 2)!, J. Integer Sequences 8 (2005), Article 5.2.3.

[12] I. Gheorghiciuc and G. Orelowitz, Super-Catalan numbers of the third and fourth kind, arxiv preprint arXiv:2008.00133 [math.CO], 2020. Available at http://arxiv.

org/abs/2008.00133.

[13] J. Mikić, On a new alternating convolution formula for the super Catalan numbers, arxiv preprint arXiv:2110.04805 [math.CO], 2021. Available at http://arxiv.org/

abs/2110.04805.

[14] J. Mikić, Two new identities involving the Catalan numbers and sign-reversing involutions, J. Integer Sequences 23 (2020), Article 20.1.6.

[15] B. Sagan and C. Savage, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, Integers 10 (2010), A52, 697–703.

[16] B. Sagan and J. Tirrell, Lucas atoms, Adv. Math. 374 (2020), 107387.

[17] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

    at https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A10, Secondary 05A15. Keywords: FiboCatalan number, super Catalan number, fibonomial, lucanomial.

(Concerned with sequences \underline{A003150}, \underline{A007054}, \underline{A010048}, \underline{A277202}, and \underline{A372949}.)

Received May 2 2024; revised versions received June 20 2024; April 29 2025. Published in Journal of Integer Sequences, September 22 2025.

Return to Journal of Integer Sequences home page.