Multinomial Catalan Numbers and Lucas Analogues

Joaquim Cera Da Conceiçao Normandie Université UNICAEN, CNRS Laboratoire de Mathématiques Nicolas Oresme 14000 Caen France

              joaquim.cera-daconceicao@unicaen.fr

Abstract We define a new generalization of Catalan numbers to multinomial coefficients. With arithmetic methods, we study their integrality and the integrality of their Lucasnomial generalization. We give a complete characterization of regular Lucas sequences for which they yield integers up to finitely many cases.

1 Introduction

The central binomial coefficient \binom{2n}{n} is well known to be divisible by n + 1, thus forming the integer sequence of Catalan numbers C(n). Indeed,

C(n) = \frac{1}{n + 1}\binom{2n}{n},

for all integers n ≥ 0. These numbers are of great interest since they appear in various contexts and have many combinatorial interpretations. Moreover, they have been generalized in several ways, such as the generalized Lucasnomial Fuss-Catalan numbers, defined by

\frac{U_{r}}{U_{(a−1)n+r}} \binom{an + r − 1}{n}_{U} := \frac{U_{r}}{U_{(a−1)n+r}} · \frac{U_{an+r−1} ⋯ U_{(a−1)n+r}}{U_{n} ⋯ U_{1}} ,

for all integers n ≥ 1, where a ≥ 2 and r ≥ 1 are fixed integers, U = (U_{n})_{n≥1} is a Lucas sequence and \binom{an+r−1}{n}_{U} is a generalized binomial coefficient with respect to U, which we call a Lucasnomial coefficient. They are a surprising example of a generalization which yields integers only. This was shown by Ballot [2, 4] in recent papers which are of relevance to our work. A Lucas sequence U is a second-order linear recurrence satisfying U_{0} = 0, U_{1} = 1 and U_{n+2} = P U_{n+1} − QU_{n} for all n ≥ 0, where P, Q are integers. Generalized binomial coefficients with respect to an integer sequence X = (X_{n})_{n≥0}, with X_{n} ≠ 0 for all n ≥ 1, are defined as follows:

\binom{m}{n}_{X} = \begin{cases}\frac{X_{m}X_{m−1}···X_{m−n+1}}{X_{n}X_{n−1}···X_{1}} , & if m ≥ n ≥ 1; \\ 1, & if n = 0; \\ 0, & otherwise. \end{cases}

In this paper, we prove the integrality of all but a finite number of terms of yet another generalization of Catalan numbers, namely the multinomial Catalan numbers. These are defined for all integers n ≥ 1 by

C_{l}(n) = \frac{1}{(n + 1)^{l}} \binom{(l + 1)n}{n}_{l} := \frac{1}{(n + 1)^{l}} \binom{(l + 1)n}{n, n, …, n},

where l is a positive integer and

\binom{a_{1} + a_{2} + ⋯ + a_{l+1}}{a_{1}, a_{2}, …, a_{l+1}} = \frac{(a_{1} + ⋯ + a_{l+1})!}{a_{1}! ⋯ a_{l+1}!}

are multinomial coefficients with positive integers a_{1}, …, a_{l+1}. It is called a central multinomial coefficient when all the a_{i}’s are equal. In particular, our study leads to the following generalization of the integrality of Catalan numbers:

Theorem 1. The numbers C_{l}(n) are integers for all n ≥ l.

The usual Catalan numbers correspond to l = 1. Proving Theorem 1 will require studying the p-adic valuation of multinomial coefficients, where p represents a prime number. Kummer [8] showed that in the binomial case, the p-adic valuation of \binom{m+n}{n} is equal to the number of carries in the base-p addition of m and n. From Kummer’s theorem, usually called Kummer’s rule, and the identity

\binom{a_{1} + a_{2} + ⋯ + a_{l+1}}{a_{1}, a_{2}, …, a_{l+1}} = ∏_{i=1}^{l+1} \binom{a_{1} + ⋯ + a_{i}}{a_{i}},  (1)

we obtain the following generalization of the Kummer rule:

Theorem 2 (Generalized Kummer rule). The p-adic valuation of the multinomial coefficient

\binom{a_{1} + a_{2} + ⋯ + a_{l+1}}{a_{1}, a_{2}, …, a_{l+1}},

is equal to the number of carries that occur when adding a_{1}, a_{2}, …, a_{l}, and a_{l+1} in base p. The number of carries is independent of the order of the summands and of the parenthesization of the sum.

Note that the identity (1) seems to indicate that we first add a_{1} + a_{2}, then (a_{1} + a_{2}) + a_{3}, etc., but the theorem states a stronger result. An expression a_{1} + a_{2} + ⋯ + a_{l+1} is said to be parenthesized when any pair of parentheses encloses exactly two summands. For instance, the expression ((a_{1} + a_{2}) + (a_{3} + a_{4})) is parenthesized, while ((a_{1} + a_{2} + a_{3}) + a_{4}) is not. The number of carries is associative, i.e., independent of the parenthesization of the sum a_{1} + ⋯ + a_{l+1}. Indeed, given a parenthesization where the last addition to perform is A + B, where A = a_{1} + ⋯ + a_{r} and B = a_{r+1} + ⋯ + a_{l+1} for some 1 ≤ r ≤ l, we have

M_{l+1} := \binom{a_{1} + a_{2} + ⋯ + a_{l+1}}{a_{1}, a_{2}, …, a_{l+1}} = \binom{A}{a_{1}, …, a_{r}}\binom{B}{a_{r+1}, …, a_{l+1}}\binom{A + B}{B}.

Thus, by an induction argument, one can write any multinomial coefficient as the product of binomial coefficients corresponding to each addition in the chosen parenthesization. Taking p-adic valuations in the final expression using the ordinary Kummer rule, we must find a total number of carries equal to v_{p}(M_{l+1}) for all parenthesizations. Moreover, for every permutation σ ∈ S_{l+1}, we have

\binom{a_{1} + a_{2} + ⋯ + a_{l+1}}{a_{1}, a_{2}, …, a_{l+1}} = \binom{a_{σ(1)} + a_{σ(2)} + ⋯ + a_{σ(l+1)}}{a_{σ(1)}, a_{σ(2)}, …, a_{σ(l+1)}},

hence the number of carries produced in the sum a_{σ(1)} + ⋯ + a_{σ(l+1)} is the same for all permutations σ ∈ S_{l+1}. Let us give an example of the need of parenthesizing. Adding four copies of a = (111)_{2} in base 2 in the parenthesized expression ((a + a) + (a + a)) yields 9 carries since we have

1^{1} 1^{1} 1^{1} 1 +  1 1 1 1 1 1 0 and 1^{1} 1^{1} 1^{1} 1 0 +  1 1 1 0 1 1 1 0 0 ,

and the first addition is performed twice. However, adding four copies of a in the nonparenthesized expression (a + a + a + a) yields only 3 carries. Indeed, we have

1^{1} 1^{1} 1^{1} 1 1
1 1 1
1 1 1
+  1 1 1
1 1 1 0 0

since at each position, the addition of four 1’s yields (100)_{2}, thus producing a carry two positions to the left. Therefore, it is important that additions be performed with parenthesization.

Section 2 is dedicated to lemmas on the number of carries that occur when adding numbers of the form p^{j} − 1 in base p, with j ≥ 1, and to one property of carries in arbitrary base-p additions.

In Section 3, we prove our main theorem on multinomial Catalan numbers, Theorem 10, which states that the numbers C_{l}(n) are non-integers for finitely many n ≥ 1. Moreover, we give a necessary condition on the form of integers n for which C_{l}(n) is a non-integer.

We differ introducing several definitions, properties, and results concerning Lucas sequences and Lucasnomial coefficients to the beginning of Section 4. In particular, we will recall the primitive divisor theorem and the classification of k-defective regular Lucas sequences given by Bilu, Hanrot, and Voutier [5], and a version of Kummer’s theorem suited for Lucasnomial coefficients [3].

Section 5 proves preliminary results on the l-Lucasnomial Catalan numbers

C_{U,l}(n) = \frac{1}{U_{n+1}^{l}} \binom{(l + 1)n}{n}_{U,l} := \frac{1}{U_{n+1}^{l}} \binom{(l + 1)n}{n, n, …, n}_{U},

where U is a Lucas sequence and \binom{(l+1)n}{n}_{U,l} is a generalized multinomial coefficient with respect to U, which we call an l-Lucasnomial coefficient. (They will be properly defined in Section 4.)

In Section 6, we proceed to find all pairs (U, l) such that the l-Lucasnomial Catalan numbers C_{U,l}(n) are integers for all but a finite number of integers n ≥ 1. It turns out that only a few pairs (U, l) yield only integers up to finitely many exceptions.

Throughout our paper, unless stated otherwise, the letters l and j stand for arbitrary fixed positive integers and the letter p represents a prime number. We write ℙ for the set of prime numbers. The p-adic valuation is denoted by v_{p}. For two integers a ≤ b, we define ⟦a, b⟧ as the intersection [a, b] ∩ ℤ. The number of carries in a parenthesized base-p addition of the positive integers a_{1}, …, a_{l+1} will be denoted by C_{p}(l; a_{1}, …, a_{l+1}). When a_{1} = a_{2} = ⋯ = a_{l+1}, the notation C_{p}(l; a_{1}) will be used instead.

2 Counting carries in base-p additions

In our paper and mostly in this section we use various notation for the p-ary expansion of an integer. For N an integer and a_{θ}, a_{θ−1}, …, a_{1}, a_{0} its p-ary digits, the base-p expansion of N will sometimes be written as

[a_{θ}, a_{θ−1}, …, a_{1}, a_{0}]_{p}.

Other times, it will be represented explicitly as the sum

a_{0} + a_{1}p + ⋯ + a_{θ}p^{θ} = ∑_{i=0}^{θ} a_{i}p^{i}.

Given a positive integer m, we define the m-fold base-p addition of N as any parenthesized addition of m copies of N in base p. We proceed to prove two preliminary lemmas for the m-fold base-p additions of numbers of the form p^{j} − 1, j ≥ 1. This section ends with a general lemma on the number of carries in base-p additions. This lemma requires the use of the Legendre formula:

v_{p}(n!) = ∑_{j≥1} ⌊\frac{n}{p^{j}} ⌋,

valid for all n ≥ 0.

Lemma 3. Let m ∈ ⟦1, p⟧. The m-fold base-p addition of N = p^{j} − 1 generates (m − 1)j carries and the p-ary expansion of mN is

[(m − 1), \underbrace{(p − 1), …, (p − 1)}_{j − 1 times}, (p − m)]_{p}.

Proof. We prove the lemma by finite induction on m. For m = 1, there is nothing to prove. Thus assume the statement holds for m ∈ ⟦1, p − 1⟧ and let us show that it is true for m + 1. Let us choose a parenthesization so that the last base-p addition we perform is mN + N. By the induction hypothesis, (m − 1)j carries are produced to obtain mN and

mN = [(m − 1), \underbrace{(p − 1), …, (p − 1)}_{j − 1 times}, (p − m)]_{p}.

As p − m ≥ 1, adding the first digits of mN and N yields (p − m) + (p − 1) = p + (p − m − 1). Therefore, the first digit of (m+1)N is p−m−1 and one initial carry is produced. Moreover, the initial carry propagates and generates j − 1 further carries. As the first j digits of N are p − 1, the digits of (m + 1)N, from the second to the j-th, are p − 1. The last carry is added to the sum of the (j + 1)-st digits of mN and N and does not generate another carry as (m − 1) + 1 = m < p. Hence

(m + 1)N = [m, \underbrace{(p − 1), …, (p − 1)}_{j − 1 times}, (p − m − 1)]_{p},

and the addition did produce (m − 1)j + j = mj carries.

Remark 4. A similar result holds if we replace p^{j} − 1 by p^{s}(p^{j} − 1) for some s ≥ 1, since this will amount to shifting all operations s digits to the left, leaving s zero digits to the right.

Lemma 5. For all integers i ≥ 0, a p^{i}-fold base-p addition of p^{j} − 1 produces (p^{i} − 1)j carries.

Proof. Write N = p^{j} − 1. For i = 0, there is nothing to prove. Assume the statement is true for some i ≥ 0 and let us show it is true for i + 1. First, write

p^{i+1}N = ∑_{k=1}^{p^{i}} pN.  (2)

By Lemma 3, the p-fold base-p addition of N produces (p − 1)j carries, and this is done a total of p^{i} times on the right hand side of (2). Thus, p^{i}(p − 1)j carries are produced in this way. By Remark 4, the number of carries occurring in the p^{i}-fold addition of pN is the same as the number of carries produced in the p^{i}-fold base-p addition of N. By the induction hypothesis, this addition produces (p^{i} − 1)j carries. Therefore, the total number of carries counted is

p^{i}(p − 1)j + (p^{i} − 1)j = (p^{i+1} − 1)j,

and this completes the proof.

Theorem 6. Let m ∈ ⟦1, p^{j} −1⟧ and write m = p^{ν}M with p ∤ M. The m-fold base-p addition of N = p^{j} − 1 generates (m − 1)j carries and the p-ary expansion of MN is

[m_{θ}, …, m_{1}, (m_{0} − 1), \underbrace{(p − 1), …, (p − 1)}_{j − θ − 1 times}, (p − m_{θ} − 1), …, (p − m_{1} − 1), (p − m_{0})]_{p},

where M = [m_{θ}, …, m_{1}, m_{0}]_{p} with 0 ≤ θ < j and m_{θ} ≥ 1.

Proof. First, we assume ν = 0, i.e., m = M, and we proceed by induction of θ. If θ = 0, then M ∈ ⟦1, p − 1⟧ and the result follows from Lemma 3. As the result holds for j = 1, we may assume j ≥ 2. Assume the result holds for all t ≤ θ with θ ∈ ⟦0, j − 2⟧ and let us show it is true for θ + 1. Let M′ = M − m_{θ+1}p^{θ+1}, and write M′ = [m_{t}, …, m_{1}, m_{0}]_{p}, where t ≤ θ. In the addition

(∑_{i=1}^{M′} N) + ( ∑_{i=1}^{m_{θ+1}p^{θ+1}} N),

we let S_{1} and S_{2} represent respectively the first and the second sums above. Since t ≤ θ, exactly (M′ − 1)j carries are produced to obtain S_{1} by the induction hypothesis. Moreover, since

S_{2} = ∑_{i=1}^{m_{θ+1}} p^{θ+1}N,

using Lemma 5, followed by Lemma 3 and Remark 4, exactly

m_{θ+1}(p^{θ+1} − 1)j + (m_{θ+1} − 1)j = (m_{θ+1}p^{θ+1} − 1)j

carries are produced to obtain S_{2}. Thus, so far we have

(M′ − 1)j + (m_{θ+1}p^{θ+1} − 1)j = (M − 2)j

carries. It remains to show that j carries occur in the base-p addition S_{1} + S_{2}. Let us give the p-ary expansions of S_{1} and S_{2}. By the induction hypothesis, S_{1} is

[m_{t}, …, m_{1}, (m_{0} − 1), \underbrace{(p − 1), …, (p − 1)}_{j − t − 1 times}, (p − m_{t} − 1), …, (p − m_{1} − 1), (p − m_{0})]_{p}.

For S_{2}, we find that

S_{2} = [(m_{θ+1} − 1), \underbrace{(p − 1), …, (p − 1)}_{j − 1 times}, (p − m_{θ+1}), \underbrace{0, …, 0}_{θ + 1 times}]_{p},

by Lemma 3 and Remark 4. The first θ + 1 digits of S_{1} + S_{2} are those of S_{1} and no carry occurs. Next, adding the (θ + 2)-nd digits together, we have

(p − 1) + (p − m_{θ+1}) = p + (p − m_{θ+1} − 1),

so that the (θ + 2)-nd digit of S_{1} + S_{2} is (p − m_{θ+1} − 1) and a carry occurred. Since the j − 1 following digits of S_{2} are all equal to p − 1, the first carry generates j − 1 further carries. Moreover, this implies that the j − 1 digits of S_{1} + S_{2} starting from position θ + 3 are those of S_{1}. Since S_{1} has exactly t + j + 1 digits, there is no addition left to consider and the p-ary expansion of S_{1} + S_{2} is

[m_{θ+1}, …, m_{1}, (m_{0} − 1), \underbrace{(p − 1), …, (p − 1)}_{j − θ − 2 times}, (p − m_{θ+1} − 1), …, (p − m_{1} − 1), (p − m_{0})]_{p}.

Therefore, we counted exactly j carries in the addition S_{1}+S_{2}, making for a total of (M −1)j carries. This ends the proof for ν = 0. If ν ≥ 1, then the p-ary expansion of mN = p^{ν}MN is a ν-left shift of the digits of MN leaving ν zero digits to the right. As for the number of carries, note that

mN = ∑_{i=1}^{M} p^{ν}N,

where (M − 1)j carries are produced in the M-fold base-p addition of p^{ν}N by Remark 4 and the case ν = 0. Moreover, the p^{ν}-fold base-p addition of N produces exactly (p^{ν} −1)j carries by Lemma 5, so that a total of (M − 1)j + M(p^{ν} − 1)j = (m − 1)j carries are produced in the m-fold base-p addition of N.

Theorem 6 and Lemma 5 show a definite pattern in the number of carries of an m-fold base-p addition of N = p^{j} − 1 for all m ≤ p^{j}, but this pattern breaks up at m = p^{j} + 1. Indeed, we have

(m − 1)N = p^{j}N = [\underbrace{(p − 1), …, (p − 1)}_{j times}, \underbrace{0, …, 0}_{j times}]_{p}

by Theorem 6. Therefore, adding N to (m − 1)N produces no carry since N has exactly j digits. Thus the total number of carries in the m-fold base-p addition of N is equal to the number of carries in its (m − 1)-fold base-p addition, that is, (m − 2)j carries.

Lemma 7. Let a_{1}, …, a_{l+1} be positive integers and write a_{i} = A_{i}p^{j} +B_{i} with integers B_{i} < p^{j} and A_{i} ≥ 0 for all 1 ≤ i ≤ l + 1. Then

C_{p}(l; a_{1}, …, a_{l+1}) ≥ C_{p}(l; A_{1}, …, A_{l+1}) + C_{p}(l; B_{1}, …, B_{l+1}).

Proof. By Legendre’s formula, we have

v_{p}(\binom{a_{1} + ⋯ + a_{l+1}}{a_{1}, …, a_{l+1}}) = ∑_{i≥1}(⌊\frac{a_{1} + ⋯ + a_{l+1}}{p^{i}} ⌋ − ∑_{k=1}^{l+1} ⌊\frac{a_{k}}{p^{i}} ⌋).  (3)

When i ≤ j, we have

⌊\frac{a_{k}}{p^{i}} ⌋ = A_{k}p^{j−i} + ⌊\frac{B_{k}}{p^{i}} ⌋,  (4)

and

⌊\frac{a_{1} + ⋯ + a_{l+1}}{p^{i}} ⌋ = ∑_{k=1}^{l+1} A_{k}p^{j−i} + ⌊\frac{B_{1} + ⋯ + B_{l+1}}{p^{i}} ⌋.  (5)

When i > j, using the identity ⌊x + y⌋ = ⌊x⌋ + ⌊y⌋ + ⌊{x} + {y}⌋ valid for all x, y ∈ ℝ, we obtain

⌊\frac{a_{k}}{p^{i}} ⌋ = ⌊\frac{A_{k}}{p^{i−j}} ⌋ + ⌊\frac{B_{k}}{p^{i}} ⌋ + ⌊\{\frac{A_{k}}{p^{i−j}} \} + \{\frac{B_{k}}{p^{i}} \}⌋.

Let A_{k} = [d_{θ}, …, d_{1}, d_{0}]_{p}. Then

\{\frac{A_{k}}{p^{i−j}} \} = \{\frac{d_{0} + ⋯ + d_{i−j−1}p^{i−j−1}}{p^{i−j}} \} ≤ 1 − \frac{1}{p^{i−j}} ,

since d_{i} ≤ p − 1 for all 0 ≤ i ≤ θ. With the same method, we obtain

\{\frac{B_{k}}{p^{i}} \} ≤ \frac{1}{p^{i−j}} − \frac{1}{p^{i}} .

Hence

⌊\frac{a_{k}}{p^{i}} ⌋ = ⌊\frac{A_{k}}{p^{i−j}} ⌋ + ⌊\frac{B_{k}}{p^{i}} ⌋ = ⌊\frac{A_{k}}{p^{i−j}} ⌋.  (6)

With the assumption i > j, and using again the identity ⌊x + y⌋ = ⌊x⌋ + ⌊y⌋ + ⌊{x} + {y}⌋, we have

⌊\frac{a_{1} + ⋯ + a_{l+1}}{p^{i}} ⌋ ≥ ⌊\frac{A_{1} + ⋯ + A_{l+1}}{p^{i−j}} ⌋ + ⌊\frac{B_{1} + ⋯ + B_{l+1}}{p^{i}} ⌋.  (7)

Putting together (3), (4), (5), (6) and (7), we find that the p-adic valuation of \binom{a_{1}+···+a_{l+1}}{a_{1},...,a_{l+1}} is at least equal to

S := ∑_{1≤i≤j}(⌊\frac{B_{1} + ⋯ + B_{l+1}}{p^{i}} ⌋ − ∑_{k=1}^{l+1} ⌊\frac{B_{k}}{p^{i}} ⌋)

+ ∑_{i>j}(⌊\frac{A_{1} + ⋯ + A_{l+1}}{p^{i−j}} ⌋ + ⌊\frac{B_{1} + ⋯ + B_{l+1}}{p^{i}} ⌋ − ∑_{k=1}^{l+1}(⌊\frac{A_{k}}{p^{i−j}} ⌋ + ⌊\frac{B_{k}}{p^{i}} ⌋)).

But, by Legendre’s formula, S is equal to

v_{p}(\binom{A_{1} + ⋯ + A_{l+1}}{A_{1}, …, A_{l+1}}) + v_{p}(\binom{B_{1} + ⋯ + B_{l+1}}{B_{1}, …, B_{l+1}}),

and the result follows from Kummer’s theorem.

Finally, note that to prove these results and the facts given in the introduction, the primality of p is needed. Indeed, Legendre’s formula and Kummer’s theorem have been widely used, and they both require that p be a prime.

3 Integrality of multinomial Catalan numbers

Our proof of the integrality of multinomial Catalan numbers amounts to checking that the p-adic valuation of C_{l}(n) is non-negative for all primes p. We end up proving that C_{l}(n) is not an integer for only a finite number of integers n ≥ 1. For these finitely many exceptional numbers, we give a necessary condition they must satisfy. The proof has two main steps. In the theorem below, we first show that C_{l}(n) has a negative p-adic valuation only when p ≤ p^{v_{p}(n+1)} ≤ l. Then, we prove that for all pairs (n, p) such that p ≤ p^{v_{p}(n+1)} ≤ l and v_{p}(C_{l}(n)) < 0, the integer n + 1 must be a power of p. In particular, this shows that any exceptional number n satisfies n + 1 ≤ l, thus ensuring they are finitely many.

Theorem 8. The number C_{l}(n) is an integer if v_{p}(n+1) ≥ log_{p} (l + 1) for all primes p such that p ≤ l and p | n + 1.

Proof. Since multinomial coefficients are integers, v_{p}(C_{l}(n)) ≥ 0 for every p ∤ n + 1. Hence, assume p | n + 1 and let j = v_{p}(n + 1). It suffices to show that the p-adic valuation of the central multinomial coefficient is greater than or equal to lj. Let λ ≥ 1 be the unique integer such that n + 1 = λp^{j}. Then

n = (λ − 1)p^{j} + ∑_{i=0}^{j−1}(p − 1)p^{i} := (λ − 1)p^{j} + N.

By Kummer’s rule, the valuation of the multinomial coefficient is obtained by counting the number of carries in the (l + 1)-fold base-p addition of n. On the one hand, if p ≥ l + 1 then Lemma 3 ensures that exactly lj carries are produced in the (l + 1)-fold base-p addition of N. Hence, by Lemma 7, there are at least lj carries in the (l + 1)-fold base-p addition of n. On the other hand, if p ≤ l and j ≥ log_{p} (l + 1) then l ≤ p^{j} − 1, and Theorem 6 and Lemma 5 ensure that at least lj carries are produced in the (l + 1)-fold base-p addition of n.

Note that Theorem 8 is enough to recover the integrality of the usual Catalan numbers since there is no prime less than l = 1. However, for higher values of l there are still infinitely many n ≥ 1 to study. For instance, when l = 2, the integrality of C_{l}(n) for positive integers n ≡ 1 (mod 4) is not settled by Theorem 8.

Lemma 9. Suppose C_{l}(n) is not an integer. Then n + 1 is a prime power and l + 1 has at least two non-zero digits in base n + 1.

Proof. Since C_{l}(n) is not an integer, by Theorem 8, there exists a prime number p ≤ l such that v_{p}(C_{l}(n)) < 0 and n + 1 = λp^{j} for some integers 1 ≤ j < log_{p} (l + 1) and λ ≥ 1, p ∤ λ. By contradiction, assume that λ ≥ 2. First write

n = (λ − 1)p^{j} + ∑_{i=0}^{j−1}(p − 1)p^{i} := (λ − 1)p^{j} + N.

Since l + 1 > p^{j}, we may write

l + 1 = ∑_{k=ν}^{θ} a_{k}p^{kj},

in base p^{j}, where θ ≥ ν ≥ 0 and 0 ≤ a_{k} < p^{j} with a_{ν}, a_{θ} > 0. In the decomposition

∑_{i=1}^{l+1} N = ∑_{\begin{matrix}k=ν \\ a_{k}≠0 \end{matrix}}^{θ} ∑_{i=1}^{a_{k}p^{kj}} N = ∑_{\begin{matrix}k=ν \\ a_{k}≠0 \end{matrix}}^{θ} ∑_{i=1}^{a_{k}} ∑_{s=1}^{p^{kj}} N,

we count the carries produced in the two inner sums using Lemma 5 and Theorem 6, and obtain

∑_{\begin{matrix}k=ν \\ a_{k}≠0 \end{matrix}}^{θ} (a_{k}(p^{kj} − 1)j + (a_{k} − 1)j) = ∑_{\begin{matrix}k=ν \\ a_{k}≠0 \end{matrix}}^{θ}(a_{k}p^{kj} − 1)j = (l + 1)j − ηj  (8)

carries, where η is the number of non-zero p^{j}-ary digits of l + 1. Note that if l + 1 had only one non-zero p^{j}-ary digit, then we would have lj carries and C_{l}(n) would have a non-negative p-adic valuation, which is a contradiction. Hence l + 1 has at least two non-zero digits in base p^{j}. Since λ ≥ 2, we know that (λ − 1)p^{j} has at least one non-zero p-ary digit, say b. Therefore, at least one carry occurs when adding ⌈p/b⌉ copies of (λ − 1)p^{j} together. By euclidean division, write l + 1 = Qp^{j} + R, where 0 ≤ R < p^{j} and Q ≥ 1. Then, there are at least ⌊(l + 1)/p⌋ = Qp^{j−1} + ⌊R/p⌋ carries produced in the (l + 1)-fold base-p addition of (λ − 1)p^{j}. In particular, Q is either equal to

∑_{k=ν}^{θ} a_{k}p^{(k−1)j} or to ∑_{k=1}^{θ} a_{k}p^{(k−1)j},

depending on whether ν > 0 or ν = 0 respectively. In both cases, since l + 1 has at least two non-zero digits in base p^{j}, we have Q ≥ p^{(θ−1)j} and Qp^{j−1} ≥ p^{θj−1} ≥ θj for every θ, j ≥ 1. This, together with (8) and Lemma 7, yields that at least

(l + 1)j − ηj + Qp^{j−1} ≥ lj + (θ − η + 1)j ≥ lj

carries are produced in the (l + 1)-fold base-p addition of n. Indeed, θ + 1 is the number of base-p^{j} digits of l + 1. Thus, θ + 1 ≥ η, the number of non-zero base-p^{j} digits of l + 1. This means that v_{p}(C_{l}(n)) ≥ 0, which is a contradiction. Hence λ = 1, n + 1 = p^{j}, and l + 1 has at least two non-zero digits in base n + 1.

Theorem 10. There are at most finitely many integers n ≥ 1 such that C_{l}(n) is not an integer. Such integers must be of the form

n = p^{j} − 1,

with p^{j} ≤ l and l ≠ ap^{kj} − 1 for every k ≥ 1 and a ∈ ⟦1, p − 1⟧.

Proof. By Theorem 8 and Lemma 9, if there exists n ≥ 1 such that C_{l}(n) is not an integer then n = p^{j} − 1, with p ≤ l and 1 ≤ j < log_{p} (l + 1), that is p^{j} ≤ l. Moreover, Lemma 9 ensures that l + 1 has at least two p^{j}-ary digits. In other words, l + 1 is not of the form ap^{kj} with k ≥ 1 and a ∈ ⟦1, p − 1⟧.

Remark 11. These integers are not necessarily counterexamples. Indeed, if l = 3 and n = 1, then n has the form given in Theorem 10, but C_{3}(1) = 3.

Corollary 12. The multinomial Catalan numbers C_{l}(n) are integers for all n ≥ l.

This last corollary is a direct generalization of the integrality of the usual Catalan numbers, which we may recover by taking l = 1. Also note that if l is a prime, then C_{l}(l − 1) is not an integer and l − 1 is then the largest counterexample.

4 Preliminaries to the Lucasnomial case

We highlight some useful properties and results concerning Lucas sequences. Most of them can be found in the work of Ballot [2, 3, 4] or in the book of Williams [9]. Recall that a Lucas sequence U = U(P, Q) = (U_{n})_{n≥0} is a second-order linear recurrence with initial conditions U_{0} = 0 and U_{1} = 1, which satisfies

U_{n+2} = P U_{n+1} − QU_{n},

for all n ≥ 0, where P and Q are non-zero integers. Also, we define Δ = P^{2} − 4Q the discriminant of U(P, Q), that is, the discriminant of the characteristic polynomial of U. Given the definition, all terms of a Lucas sequence are integers. Moreover, a Lucas sequence has many divisibility properties. In particular, U is a divisibility sequence, i.e., for all m, n ≥ 0, we have

m | n ⟹ U_{m} | U_{n}.

We say that U is non-degenerate if U_{n} ≠ 0 for all n ≥ 1. A way of checking the nondegeneracy of U is to show that U_{12} ≠ 0, which is a sufficient condition. If U is nondegenerate and gcd (P, Q) = 1, we say that U is a regular Lucas sequence. Such a sequence is a strong divisibility sequence, i.e., it satisfies

gcd (U_{m}, U_{n}) = |U_{gcd (m,n)}|,

for all m, n ≥ 0. If U is regular and Δ = 0, we find that U is either the sequence of nonnegative integers or defined by U_{n} = (−1)^{n−1}n. Throughout the paper, we assume that U is a Δ-regular Lucas sequence, that is, a regular Lucas sequence such that Δ ≠ 0. The second part of our paper is dedicated to studying the divisibility of the l-Lucasnomial coefficient

\binom{(l + 1)n}{n, …, n}_{U} := \binom{(l + 1)n}{n}_{U,l},

by U_{n+1}^{l}, for all n ≥ 0. Let n!_{U} represent the generalized factorial with respect to U, i.e., n!_{U} = U_{n}U_{n−1} ⋯ U_{1} for all n ≥ 1 and 0!_{U} = 1. Here, l-Lucasnomial coefficients are defined by the formula

\binom{a_{1} + ⋯ + a_{l+1}}{a_{1}, …, a_{l+1}}_{U} := \frac{(a_{1} + ⋯ + a_{l+1})!_{U}}{a_{1}!_{U} ⋯ a_{l+1}!_{U}} ,

where the a_{i}’s are non-negative integers. Moreover, we make the assumption that P > 0 because

U(−P, Q) = (−1)^{n−1}U(P, Q),

for all n ≥ 0, implies that the l-Lucasnomial coefficients with respect to U(P, Q) and U(−P, Q) are the same up to their sign.

We start by stating and proving different facts about Lucas sequences and l-Lucasnomials. These include prime divisibility properties of U. We define the rank of appearance ρ = ρ_{U}(p) of a prime p in U to be the least positive integer n such that p | U_{n}. The condition p ∤ Q guaranties the existence of ρ. Furthermore, the regularity of U implies that p divides some term of U of positive index if and only if p ∤ Q. From now on, p represents a prime not dividing Q of rank ρ. The following proposition lists interesting and useful properties of the rank:

Proposition 13. Let U(P, Q) be a non-degenerate Lucas sequence. Then, for all positive integers m and n, we have

1. ρ | p − (\frac{Δ}{p}) if p > 2, ρ_{U}(2) = 2 if 2 | Δ and ρ_{U}(2) = 3 if 2 ∤ Δ;

2. p | U_{n} if and only if ρ | n;

3. v_{p}(U_{ρm}) = v_{p}(U_{ρ}) + x + δ_{x}, where (\frac{∗}{∗}) is the Legendre symbol, x = v_{p}(m),

δ := v_{p}(\frac{P^{2} − 3Q}{2}) · [p = 2] · [2 ∤ P],

and δ_{x} = δ · [x > 0].

Let P be a statement. In Proposition 13, we used the notation [P]. It is called the Iverson symbol and is defined by

[P] = \begin{cases}1, & if P is true; \\ 0, & if not. \end{cases}

In order to decide the integrality of l-Lucasnomial Catalan numbers, we approach the problem p-adically just as we did for the usual multinomial Catalan numbers. We proceed to state a Lucasnomial version of Kummer’s theorem [3].

Theorem 14 (Kummer’s rule for Lucasnomials). Let U(P, Q) be a non-degenerate Lucas sequence and m and n be positive integers. Then, the p-adic valuation of the Lucasnomial coefficient \binom{m+n}{n}_{U} is equal to v_{p}(U_{ρ}) when the proposition

P : \{\frac{m}{ρ}\} + \{\frac{n}{ρ}\} ≥ 1,

is true, plus the number of carries in the base-p parenthesized addition

⌊\frac{m}{ρ}⌋ + ⌊\frac{n}{ρ}⌋ + [P],

plus δ when a carry occurs from the first to the second digit, where δ is the integer defined in Proposition 13.

Note that this result can be generalized to other kinds of sequences [7] using a method similar to the classical Kummer case. For l-Lucasnomials, we will not use a Lucasnomial version of Theorem 2, but only the following corollary:

Corollary 15. The p-adic valuation of the l-Lucasnomial coefficient \binom{a_{1}+···+a_{l+1}}{a_{1},...,a_{l+1}}_{U} is equal to the sum

∑_{i=1}^{l} v_{p}(\binom{a_{1} + ⋯ + a_{i+1}}{a_{i+1}}_{U}),

where the a_{i}’s are positive integers.

Proof. It suffices to note that for every l ≥ 2, we have

\binom{a_{1} + ⋯ + a_{l+1}}{a_{1}, …, a_{l+1}}_{U} = \frac{(a_{1} + ⋯ + a_{l+1})!_{U}}{a_{1}!_{U} ⋯ a_{l+1}!_{U}}

= \frac{(a_{1} + ⋯ + a_{l+1})!_{U}}{a_{l+1}!_{U} · (a_{1} + ⋯ + a_{l})!_{U}} · \frac{(a_{1} + ⋯ + a_{l})!_{U}}{a_{1}!_{U} ⋯ a_{l}!_{U}}

= \binom{a_{1} + ⋯ + a_{l+1}}{a_{l+1}}_{U} · \binom{a_{1} + ⋯ + a_{l}}{a_{1}, …, a_{l}}_{U}.

Applying this recurrence relation (l − 1)-times, we obtain

\binom{a_{1} + ⋯ + a_{l+1}}{a_{1}, …, a_{l+1}}_{U} = ∏_{i=1}^{l} \binom{a_{1} + ⋯ + a_{i+1}}{a_{i+1}}_{U},

and the result follows by taking p-adic valuations.

Throughout the rest of the paper, given U and l, the sequence C_{U,l} = (C_{U,l}(n))_{n≥1} is called a multi-Catalan sequence if for all but finitely many integers n ≥ 1, the numbers

C_{U,l}(n) = \frac{1}{U_{n+1}^{l}} \binom{(l + 1)n}{n}_{U,l}

are integers. As stated briefly in the introduction, only a few pairs (U, l) satisfy this condition. To find infinite families of integers n ≥ 1 such that C_{U,l}(n) does not belong to ℤ, we mostly rely on a result of Bilu, Hanrot, and Voutier [5] on Δ-regular Lucas sequences. For k ≥ 1 an integer, we say that U is k-defective if U_{k} has no primitive prime divisor, i.e., there is no prime p ∤ Δ of rank k in U. They proved the following theorem:

Theorem 16 (Primitive divisor theorem). The sequence U is not n-defective for all n > 30.

In addition to this strong result, all n-defective Δ-regular Lucas sequences have been found for every positive integer n ≤ 30, we list them in Table 1. We proceed to prove two preliminary lemmas that determine the p-adic valuation of some Lucasnomial coefficients.

Lemma 17. Let n = λρp^{j} − 1, p ∤ λ, j ≥ 0, and i ∈ ⟦1, ρ⟧. Then

v_{p}(\binom{(i + 1)n}{n}_{U}) = j + δ_{j} + v_{p}(U_{ρ}) · [i < ρ] + v_{p}(Λ_{i}) · [j > 0 or i < ρ] + c_{i},

where c_{i} is the number of carries produced in the base-p addition of (λ − 1) and (λi − 1), and Λ_{i} = λ(i + 1) − 1.

Proof. First, write

\frac{n}{ρ} = λp^{j} − 1 + \frac{ρ − 1}{ρ} := (λ − 1)p^{j} + N + \frac{ρ − 1}{ρ},

where N = ∑_{k=0}^{j−1}(p − 1)p^{k}. Note that

\frac{in}{ρ} = (λi − 1)p^{j} + N + \frac{ρ − i}{ρ},

for every 1 ≤ i ≤ ρ. Let us apply Kummer’s rule for Lucasnomials. When adding the fractional parts, we obtain

\{\frac{n}{ρ}\} + \{\frac{in}{ρ}\} = \frac{2ρ − i − 1}{ρ} = \begin{cases}1 + \frac{ρ−i−1}{ρ}, & if 1 ≤ i < ρ; \\ \frac{ρ−1}{ρ}, & if i = ρ. \end{cases}

Thus, when i < ρ, a carry with weight v_{p}(U_{ρ}) occurs across the radix point. Given the digits of N, this carry generates at least j other carries with total weight j + δ_{j}. When i = ρ, no carry occurs across the radix point, but if j > 0 then the first digits of the integer parts, ⌊n/ρ⌋ and ⌊in/ρ⌋, being p − 1 and p − 1, we obtain one carry with weight 1 + δ_{j}, which generates at least j − 1 more carries. Therefore, we are left with counting carries produced in the parenthesized base-p addition

(λi − 1)p^{j} + (λ − 1)p^{j} + [j > 0 or i < ρ] · p^{j},

or equivalently, counting carries in the addition (λi − 1)p^{j} + (λ − 1)p^{j}, plus the number of carries in the addition (λ(i + 1) − 2)p^{j} + p^{j} when i < ρ or j > 0. The latter produces exactly v_{p}(Λ_{i}) carries.

Lemma 18. Let n = λρp^{j}−1, p ∤ λ, j ≥ 0, and i ∈ ⟦ρ+1, 2ρ⟧. Put Λ_{i,j} = λ(i+1)−1−[j = 0]. If ρ < i < 2ρ, then

v_{p}(\binom{(i + 1)n}{n}_{U}) = j + δ_{j} + v_{p}(U_{ρ}) + v_{p}(Λ_{i,j}) + c_{i},

with c_{i} the number of carries produced in the base-p addition of (λ−1) and (λi−1−[j = 0]). If i = 2ρ, then

v_{p}(\binom{(i + 1)n}{n}_{U}) = c_{i} + \begin{cases}j + v_{p}(Λ_{i,j}) · [j > 0], & if p > 2; \\ j + v_{2}(Λ_{i,j}) − 1, & if p = 2 and j > 1; \\ 0, & if p = 2 and j ∈ \{0, 1\}, \end{cases}

with c_{i} the number of carries produced in the base-p addition of (λ−1) and (λi−1−[j = 0]).

Proof. Write i = ρ+t, with 1 ≤ t ≤ ρ, so that with the notation used in the proof of Lemma 17, we have

\frac{n}{ρ} = (λ − 1)p^{j} + N + \frac{ρ − 1}{ρ},

and

\frac{in}{ρ} = n + \frac{tn}{ρ} = \frac{ρ − t}{ρ} + \begin{cases}(λi − 1)p^{j} + M, & if j > 0; \\ (λi − 2), & if j = 0, \end{cases}

where

M = (p − 2) + [j ≥ 2] · ∑_{k=1}^{j−1}(p − 1)p^{k}.

Note that adding the fractional parts of n/ρ and in/ρ, we obtain

\{\frac{n}{ρ}\} + \{\frac{in}{ρ}\} = \frac{2ρ − t − 1}{ρ} = \begin{cases}1 + \frac{ρ−t−1}{ρ}, & if 1 ≤ t < ρ; \\ \frac{ρ−1}{ρ}, & if t = ρ. \end{cases}  (9)

First, assume that j = 0. By (9), a carry with weight v_{p}(U_{ρ}) occurs across the radix point if and only if i < 2ρ, and we are left with counting carries produced in the parenthesized base-p addition

(λi − 2) + (λ − 1) + [i < 2ρ],

that is, the carries in the addition of (λi − 2) and (λ − 1), plus the number of carries in the addition of (λ(i + 1) − 3) and [i < 2ρ]. The latter addition produces exactly v_{p}(Λ_{i,0}) carries. Now, assume that j ≥ 1. Then, by (9), we have one carry across the radix point with weight v_{p}(U_{ρ}) when i < 2ρ, which generates, given the p-ary digits of N, at least j other carries with total weight j + δ_{j}. When i = 2ρ, there is no carry across the radix point, but the addition of the first digits of N and M yields

(p − 1) + (p − 2) = \begin{cases}p + (p − 3), & if p ≥ 3; \\ p − 1, & if p = 2, \end{cases}

thus generating at least j − 1 other carries when p ≥ 3, but no carry when p = 2. If p = 2 and j ≥ 2, then adding the second digits of the integer parts always produces one carry, which generates at least j − 2 further carries. Therefore, whether i < 2ρ, or i = 2ρ with p ≥ 3 or p = 2, we are left with counting carries in the parenthesized addition

(λi − 1)p^{j} + (λ − 1)p^{j} + \begin{cases}0, & if i = 2ρ, p = 2 and j = 1; \\ p^{j}, & otherwise, \end{cases}

and we conclude the proof in the same way we did in Lemma 17.

5 First consequences

In this section, we give some consequences of Lemmas 17 and 18. The theorem below acts as an l-Lucasnomial-Catalan-number version of Theorem 8. Most of the other results highlight infinite families of integers n ≥ 1 such that C_{U,l}(n) is, or is not, an integer.

Theorem 19. Let p ∤ Q satisfy ρ_{U}(p) > l. Then v_{p}(C_{U,l}(n)) ≥ 0 for all n ≥ 1.

Proof. Let p be such a prime. If p ∤ U_{n+1}, then it suffices to show that the l-Lucasnomial coefficient has non-negative valuation. Corollary 15 and [2, (11) and the comment below] ensure this is the case. Assume p | U_{n+1} and write n = λρp^{j} − 1 for some λ ≥ 1 with p ∤ λ. Since ρ = ρ_{U}(p) > l, by Lemma 17, Corollary 15, and Proposition 13, we have

v_{p}(\binom{(l + 1)n}{n}_{U,l}) = ∑_{i=1}^{l} v_{p}(\binom{(i + 1)n}{n}_{U}) ≥ l(j + δ_{j} + v_{p}(U_{ρ})) = v_{p}(U_{n+1}^{l}),

that is, v_{p}(C_{U,l}(n)) ≥ 0.

l

The integrality of Lucasnomial Catalan numbers, proved in a paper of Ekhad [6], is recovered for l = 1. Indeed, p ∤ Q and ρ_{U}(p) ≥ 2 imply that v_{p}(C_{U,1}(n)) ≥ 0 for all n ≥ 1 by Theorem 19. But the regularity of U ensures that these primes are exactly those that divide U at some term. Therefore, we conclude that C_{U,1}(n) is always an integer.

Lemma 20. If there exists a prime number p > l, p ∤ Q, of rank l in U, then C_{U,l}(lp^{j} − 1) is not an integer for all j ≥ 0.

Proof. Since p > l = ρ_{U}(p), we have l ≤ p − 1 and p > 2. Putting n = lp^{j} − 1, by Lemma 17 and Corollary 15, we obtain

v_{p}(\binom{(l + 1)n}{n}_{U,l}) = ∑_{i=1}^{l} v_{p}(\binom{(i + 1)n}{n}_{U})

= lj + (l − 1)v_{p}(U_{l}) + [j > 0] · v_{p}(l) + ∑_{i=1}^{l−1} v_{p}(i)

= lj + (l − 1)v_{p}(U_{l}),

where the last equality comes from p > l ≥ i. Since the valuation of the multinomial coefficient is less than v_{p}(U_{n+1}^{l}) = l(v_{p}(U_{l}) + j), we obtain C_{U,l}(lp^{j} − 1) ∉ ℤ.

Proposition 21. Assume p > 3 and ρ_{U}(p) = p + 1. If there exists a prime q ∤ Q of rank p in U, then C_{U,p+1}(pq^{j} − 1) is not an integer for all j ≥ 0.

Proof. Put n = pq^{j} − 1 and l = p + 1. Since ρ_{U}(q) = p and ρ_{U}(p) = p + 1, we know that p and q are distinct primes. Moreover, q > 2 since otherwise p = ρ_{U}(q) would be equal to either 2 or 3, which contradicts the assumption p > 3. By Lemmas 17 and 18, and Corollary 15, we have

v_{q}(\binom{(l + 1)n}{n}_{U,l}) = lj + (l − 1)v_{q}(U_{p}) + ∑_{i=1}^{p−1} v_{q}(i) + v_{q}(p + 1 − [j = 0]),

for every prime q > 2. Since p is the rank of q in U, we have p | q ± 1 by Proposition 13, and we have v_{q}(p) = 0 and v_{q}(i) = 0 for all 1 ≤ i < p − 1. Next, we determine whether q | p ± 1. Solving p | q ± 1 and q | p ± 1 for primes p > 3 and q > 2 yields no solution. Hence

v_{q}(\binom{(l + 1)n}{n}_{U,l}) = lj + (l − 1)v_{q}(U_{p}),

which, after comparing with v_{q}(U_{n+1}^{l}) = l(j + v_{q}(U_{p})), proves the result.

Theorem 22. Assume C_{U,l} = (C_{U,l}(n))_{n≥1} is a multi-Catalan sequence, l ≥ 2. Then

(1) If l − 1 ∉ ℙ or l − 1 ∈ ℙ of rank ρ ≠ l in U, then U is l-defective,

(2) If l − 1 ∈ ℙ_{>3} of rank l in U, then U is (l − 1)-defective.

Proof. Assume U is not l-defective. Then there exists a prime p ∤ ΔQ of rank l in U and by Lemma 20, we must have p ≤ l. Moreover, p ∤ Δ implies that p ≠ l. However, by Proposition 13 we have l | p ± 1, thus l must be equal to p + 1. The first point is done since we obtained a contradiction. For the second point, Proposition 21 ensures that U is (l − 1)-defective.

Lemma 23. If there exists an odd prime p ∤ Q of rank ρ in U with ρ ≤ l ≤ min (2ρ, p − 1), then C_{U,l}(ρp^{j} − 1) is non-integral for all j ≥ 1.

Proof. Write l = ρ + t with 0 ≤ t ≤ ρ and put n = ρp^{j} − 1. Using Lemmas 17 and 18, Corollary 15, and since p > 2 and j > 0, we obtain

v_{p}(\binom{(l + 1)n}{n}_{U,l}) = lj + (l − 1)v_{p}(U_{ρ}) + ∑_{\begin{matrix}i=1 \\ i≠ρ \end{matrix}}^{l} v_{p}(i),

when l < 2ρ, and

v_{p}(\binom{(l + 1)n}{n}_{U,l}) = lj + (l − 2)v_{p}(U_{ρ}) + ∑_{\begin{matrix}i=1 \\ i≠ρ \end{matrix}}^{l} v_{p}(i),

when l = 2ρ. Therefore, from the inequality l < p, we obtain

v_{p}(\binom{(l + 1)n}{n}_{U,l}) = lj + (l − 1 − [l = 2ρ])v_{p}(U_{ρ}),

which is less than v_{p}(U_{n+1}^{l}) = l(j + v_{p}(U_{ρ})).

Until now, almost all results presented in this section are used to disprove the integrality of C_{U,l} sequences. However, some exceptional pairs (U, l) will later be found. Therefore, we state a final lemma to help us prove that C_{U,l} is a multi-Catalan sequence for these exceptional cases.

Lemma 24. Let n = λρp^{j} − 1 for some j ≥ 0 and λ ≥ 1, p ∤ λ. Assume ρ = p − (\frac{Δ}{p}), v_{p}(U_{ρ}) = 1 and

max(ρ, p) ≤ l < 2ρ.

Then v_{p}(C_{U,l}(n)) ≥ 0, except for n = ρ − 1 and ρ = p = l, or ρ = p − 1 and l = p.

Proof. Assume j > 0. Then, by Lemmas 17 and 18, Corollary 15, and the assumption v_{p}(U_{ρ}) = 1, we have

v_{p}(\binom{(l + 1)n}{n}_{U,l}) ≥ l(j + δ_{j}) + (l − 1) + ∑_{i=1}^{l} v_{p}(Λ_{i}),

where Λ_{i} = λ(i + 1) − 1 for all 1 ≤ i ≤ l. Since l ≥ p, there exists 1 ≤ i ≤ l such that λ(i + 1) ≡ 1 (mod p). Therefore,

v_{p}(\binom{(l + 1)n}{n}_{U,l}) ≥ l(j + δ_{j} + 1) = v_{p}(U_{n+1}^{l}).

Now, assume j = 0. Then, using Lemmas 17 and 18, and Corollary 15, we obtain

v_{p}(\binom{(l + 1)n}{n}_{U,l}) ≥ (l − 1) + ∑_{i=1}^{ρ−1} v_{p}(Λ_{i}) + [l > ρ] · ∑_{i=ρ+1}^{l} v_{p}(Λ_{i,0}).

Let 1 ≤ μ ≤ p − 1 be such that μλ ≡ 1 (mod p) and assume λ ≢ 1 (mod p). Thus μ ≥ 2, and taking i = μ − 1 < ρ yields

λ(i + 1) ≡ 1 (mod p),

and it follows that v_{p}(C_{U,l}(λρ−1)) ≥ 0. Next, assume that p | λ−1 and λ ≥ 2. Let s, λ_{s} ≥ 1 and b ≥ 0 be integers such that λ = 1 + λ_{s}p^{s} + bp^{s+1} and λ_{s} < p. Put

i = \begin{cases}⌊p/λ_{s}⌋, & if λ_{s} > 1; \\ p − 1, & if λ_{s} = 1, \end{cases}

and let us count the number of carries produced in the base-p addition (λ − 1) + (λi − 1). Since 1 ≤ i ≤ p − 1, we have

(iλ − 1) = (i − 1) + iλ_{s}p^{s} + dp^{s+1},

for some integer d ≥ 0 and with iλ_{s} < p. Adding the s-th digits of (λ − 1) and (λi − 1) in base p yields a carry since λ_{s} + iλ_{s} = (i + 1)λ_{s} ≥ p. By Lemmas 7 and 17,

v_{p}(\binom{(l + 1)n}{n}_{U,l}) ≥ l = v_{p}(U_{n+1}^{l}).

The only remaining case is n = ρ − 1, for which we have

v_{p}(\binom{(l + 1)n}{n}_{U,l}) = (l − 1) + ∑_{i=1}^{ρ−1} v_{p}(i) + [l > ρ] · ∑_{i=ρ+1}^{l} v_{p}(i − 1).  (10)

The p-adic valuation in (10) is equal to l − 1 when ρ = p = l, or ρ = p − 1 and l = ρ + 1, and is at least equal to l = v_{p}(U_{n+1}^{l}) otherwise.

6 Multi-Catalan sequences

We are now ready to prove the main results on l-Lucasnomial Catalan numbers. First, we prove the integrality of all but a finite number of terms of C_{U,l} when (U, l) is an exceptional pair displayed in Table 3. Then, we proceed to show that for every other pair, there exists an infinite family of integers n ≥ 1 such that C_{U,l}(n) does not belong to ℤ.

Lemma 25. Assume l ≥ 2 and let (U, l) be a pair in Table 3. Then the numbers

C_{U,l}(n) = \frac{1}{U_{n+1}^{l}} \binom{(l + 1)n}{n}_{U,l},

are integers for all n ≥ 1, except for

n = \begin{cases}p − 1, & if p | Δ and l = p; \\ p − 2, & if ρ_{U}(p) = p − 1 and l = p; \\ 5, & if U = U(1, −1) and l = 6. \end{cases}

In particular, C_{U,l}(n) is an integer for every n ≥ l.

Proof. By Theorem 19, v_{p}(C_{U,l}(n)) ≥ 0 for every prime p ∤ Q with rank ρ > l in U. For every pair (U, l) in Table 3, except (U(1, −1), 6) and (U(1, 2), 8), we look at the first terms of U, up to U_{l}, and check that all prime factors of those terms satisfy the hypotheses of Lemma 24. It follows that v_{p}(C_{U,l}(n)) ≥ 0 for every prime p ∤ Q of rank ρ ≤ l in U and every n ≥ 1, except for the few exceptions stated in Lemma 24. Since U is regular, p ∤ Q is equivalent to p | U_{m}, for some m ≥ 1. Hence, for all but finitely many n ≥ 1, we have v_{p}(C_{U,l}(n)) ≥ 0 for all primes. Let l = 6 and U = U(1, −1). The above method works for every prime but 2. Indeed, the first terms of U up to U_{6} are

0, 1, 1, 2, 3, 5, and 8,

and we see that ρ = ρ_{U}(2) = 3 and l = 2ρ, thus Lemma 24 does not apply. Since there is nothing to prove when 2 ∤ U_{n+1}, assume that 2 | U_{n+1} and write n + 1 = λρ2^{j} for some j ≥ 0 and λ ≥ 1, with 2 ∤ λ. By Lemmas 17 and 18, and Corollary 15, we have

v_{2}(\binom{7n}{n}_{U,6}) ≥ (l − 2) + v_{2}(3λ − 1) + v_{2}(6λ − 2) ≥ l = v_{p}(U_{n+1}^{l}),

when j = 0, where we used 2 ∤ λ, v_{2}(U_{3}) = 1, and δ_{0} = 0. When j > 0, we have

v_{2}(\binom{7n}{n}_{U,6}) = 5j + 9 + ∑_{i=1}^{5} v_{2}(λ(i + 1) − 1) + [j > 1](j + v_{2}(7λ − 1) − 1) + ∑_{i=1}^{6} c_{i}, (11)

where we used that 2 ∤ λ, v_{2}(U_{3}) = 1, and δ_{j} = 1 and where c_{i} is the number of carries in the base-p addition of (λ − 1) and (λi − 1). When j ≥ 2, we have

v_{2}(\binom{7n}{n}_{U,6}) = 6j + 8 + v_{2}(3λ − 1) + v_{2}(5λ − 1) + v_{2}(7λ − 1) + ∑_{i=1}^{6} c_{i},

which is at least equal to 6(j + 2) = v_{2}(U_{n+1}^{6}) since 2 ∤ λ and we either have v_{2}(3λ − 1) ≥ 2 or v_{2}(5λ − 1) ≥ 2, depending on the value of λ mod 4. When j = 1 and λ = 1, that is, when n = 5, we find

v_{2}(\binom{7n}{n}_{U,6}) = 17 < v_{2}(U_{6}^{6}) = 18,

so that C_{U,6}(5) ∉ ℤ. Next, assume j = 1 and λ ≥ 3. We may write

λ = 1 + 2^{s} + b2^{s+1},

for some integers s ≥ 1 and b ≥ 0. When i = 1, adding (λ − 1) to (λi − 1) produces at least one carry from the addition of the s-th digits. Hence

v_{2}(\binom{7n}{n}_{U,6}) ≥ 5j + 10 + v_{2}(3λ − 1) + v_{2}(5λ − 1) ≥ 18 = v_{2}(U_{6}^{6}),

by (11). That makes the case U = U(1, −1) and l = 6 complete. Let l = 8 and U = U(1, 2). Here, the method used at the beginning of the proof in the general case works for every prime but 3. Indeed, the first terms up to U_{8} are

0, 1, 1, −1, −3, −1, 5, 7, and − 3,

and we see that ρ = ρ_{U}(3) = 4 and l = 2ρ, thus Lemma 24 does not apply. Again by Lemmas 17 and 18, and Corollary 15, we have

v_{3}(\binom{9n}{n}_{U,8}) ≥ 8j + 6 + [j > 0] · (v_{3}(Λ_{4}) + v_{3}(Λ_{8,j})) + ∑_{i=1}^{3} v_{3}(Λ_{i}) + ∑_{i=5}^{7} v_{3}(Λ_{i,j}).

Let μ ∈ {1, 2} be such that μλ ≡ 1 (mod 3) and put i = 1 when μ = 2, and i = 3 when μ = 1. In addition, put i_{1} = i + 3 when j > 0, and i_{1} = i + 4 when j = 0. Hence

v_{3}(Λ_{i}) ≥ 1 and v_{3}(Λ_{i_{1},j}) ≥ 1,

and we obtain v_{3}(\binom{9n}{n}_{U,8}) ≥ 8(j + 1) = v_{3}(U_{n+1}^{8}) for all such n ≥ 1.

Lemma 26. The two sequences U(1, −1) and U(1, 2) are the only Δ-regular Lucas sequences such that the numbers

C_{U,6}(n) = \frac{1}{U_{n+1}^{6}} \binom{7n}{n}_{U,6},

are integers for all n ≥ 1, except n = 5 when U = U(1, −1).

Proof. Let C_{U,6} be a multi-Catalan sequence and note that

U_{6} = U_{2}U_{3}(P^{2} − 3Q).  (12)

By Theorem 22, either U is 6-defective or, when ρ_{U}(5) = 6, U is 5-defective. From (12), having ρ_{U}(5) = 6 implies that 5 | P^{2} −3Q. Testing the seven 5-defective sequences displayed in Table 1, we find that only U(1, 2) satisfies this divisibility relation. By Lemma 25, we know that C_{U,6} is multi-Catalan for U(1, 2). Therefore, any other U such that C_{U,6} is multi-Catalan must be 6-defective. For the four families of 6-defective sequences, we work on U_{3} to find multi-Catalan sequences. First, by Lemma 23, U_{3} may only have 2, 3 or 5 as prime divisors and, since gcd (U_{2}, U_{3}) = 1 by regularity, these would be primitive prime divisors of rank 3. Moreover, 5 is actually not a divisor of U_{3}. Indeed, if it were the case, then we would have ρ_{U}(5) = 3 and

v_{5}(\binom{7(5^{j}ρ − 1)}{5^{j}ρ − 1}_{U,6}) = 6j + 4v_{5}(U_{3}) + 1 < 6(j + v_{5}(U_{3})) = v_{5}(U_{5^{j}ρ}^{6}),

for all j ≥ 0, by Lemmas 17 and 18. Hence, C_{U,6}(5^{j}ρ − 1) is non-integral for all j ≥ 0, contradicting our hypothesis. Therefore, U_{3} = ±2^{a}3^{b} for some a, b ≥ 0. If b ≥ 1 then 3 has rank 3 in U and, by Lemmas 17 and 18,

v_{3}(\binom{7(3^{j+1} − 1)}{3^{j+1} − 1}_{U,6}) = 6j + 4b + 2,

for every j ≥ 1, which is greater than or equal to v_{p}(U_{3^{j+1}}^{6}) = 6(j + b) if and only if b = 1. Hence b ∈ {0, 1}. Let us now study the four families.

(1) Let Q = (P^{2} − 1)/3 with 3 ∤ P ≥ 4. Note that U_{3} = (2P^{2} + 1)/3 is an odd integer, so a = 0. Hence either U_{3} = ±1 or U_{3} = ±3, and it follows that P^{2} ∈ {−5, −2, 1, 4}. But P is an integer greater than or equal to 4, so there is no solution.

(2) Let Q = (P^{2} ± 3)/3 with 3 | P. Note that from

U_{3} = \frac{2P^{2} ± 3}{3} = ±2^{a}3^{b},

we obtain ±3 = ±2^{a}3^{b+1} − 2P^{2}. Since 2 and 9 do not divide 3, a and b must be equal to zero. It follows that P^{2} ∈ {−3, 0, 3}, giving no solution since P is a non-zero integer.

(3) Let Q = (P^{2} − (−2)^{i})/3 with P ≡ ±1 (mod 6), i ≥ 1 and (P, i) ≠ (1, 1). Since 2 ∤ P Q, we see that ρ_{U}(2) = 3. Furthermore, note that

δ = v_{2}(\frac{P^{2} − 3Q}{2}) = v_{2}(\frac{(−2)^{i}}{2} ) = i − 1,

and

v_{2}(\binom{7(3 · 2^{j} − 1)}{3 · 2^{j} − 1}_{U,6}) = 6j + 5δ + 4a + 3,  (13)

for every j ≥ 1. For 6j +5δ+4a+3 in (13) to be at least equal to v_{2}(U_{3·2^{j}}^{6}) = 6(j +δ+a), the inequality δ + 2a ≤ 3 must be satisfied. Since a ≥ 1, we have a = 1 and i ∈ {1, 2} as the only solutions. If i = 1, then

U_{3} = \frac{2P^{2} − 2}{3} = ±2 · 3^{b},

i.e., P^{2} = 1 ± 3^{b+1}. Thus, P^{2} ∈ {−8, −2, 4, 10} and P = ±2. However, P is congruent to ±1 modulo 6, so there is no solution in the case i = 1. If i = 2, then, by the same method, P^{2} = −2 ± 3^{b+1}. Hence P^{2} ∈ {−11, −5, 1, 7} and we find the Fibonacci sequences U(±1, −1) as candidates. These are two of the exceptions in Lemma 25.

(4) Let Q = (P^{2} ± 3 · 2^{i})/3 with P ≡ 3 (mod 6) and i ≥ 1. Then

U_{3} = \frac{2P^{2} ± 3 · 2^{i}}{3} = ±2^{a}3^{b},

and, using the previous method, we find a = 1 and i ∈ {1, 2}. But 9 | P^{2}, so that b = 0. Solving for P and i, we find that P = ±3 and i = 2. Hence,

Q = \frac{P^{2} + 3 · 2^{i}}{3} = 7.

However, for the sequences U(±3, 7), we have ρ_{U}(59) = 5 ≤ 6 < min (2 · 5, 59) = 10. By Lemma 23, C_{U,6} is not a multi-Catalan sequence for U(±3, 7).

Theorem 27. Assume l ≥ 2. There are no Δ-regular Lucas sequences U with C_{U,l} multi-Catalan other than the exceptions of Lemma 25.

Proof. If l > 30, then by Theorem 22 the sequence C_{U,l} is multi-Catalan only if U is either l or (l − 1)-defective. The primitive divisor theorem ensures that this is not the case for l > 31. For l = 31, U must only be l-defective, thus the same conclusion holds.

Let 5 ≤ l ≤ 30 be an integer not equal to 6. Using both points of Theorem 22 and inspecting Table 1, we find that the only possible sequences U are those in line l of Table 1 if l ∈ {5, 7, 10, 12, 13, 18, 30}, in line 13 if l = 14 and in lines 7 or 8 if l = 8. We start with l = 30, where U = U(1, 2) is the only candidate. Note that the prime 271 has rank ρ = 17 in U(1, 2). Since ρ ≤ l = 30 < min (2ρ, 271), Lemma 23 ensures that C_{U,30} is not multi-Catalan. The same method applies to every other case, except for the exceptions of Lemma 25. Table 2 lists some possible choices for p and ρ_{U}(p) in each case.

We now study the remaining cases, that is, l = 2, 3, 4 or 6, but the case l = 6 has already been studied in Lemma 26.

(1) Let l = 4. Assume C_{U,4} is a multi-Catalan sequence. By Lemma 23, only the primes 2 and 3 may have rank lower than or equal to 4 in U. Let p ∈ {2, 3} and assume ρ = ρ_{U}(p) = 2. By Lemmas 17 and 18, and Corollary 15, we have

v_{p}(\binom{5n}{n}_{U,4}) = 4j + 2v_{p}(P) + \begin{cases}1, & if p = 3; \\ 3, & if p = 2, \end{cases}

for every n ≥ 1 of the form n = ρp^{j} − 1, j ≥ 0. Note that δ_{j} does not appear here since δ_{j} = 0 for j ≥ 0 when ρ_{U}(2) = 2. Since v_{p}(U_{n+1}^{4}) = 4j + 4v_{p}(P), we must have P = ±1 or P = ±2, otherwise C_{U,4}(ρp^{j} − 1) is not integral for all j ≥ 0. If 3 has rank ρ = 4, then

v_{3}(\binom{5n}{n}_{U,4}) = 4j + 3v_{p}(U_{4}) + 1,

for every n ≥ 1 of the form n = 3^{j}ρ − 1, j ≥ 0. Since v_{3}(U_{n+1}^{4}) = 4j + 4v_{p}(U_{4}) and U_{4} = U_{2}(P^{2} − 2Q), it follows that P^{2} − 2Q = ±1 or ±3. Hence

Q = \frac{P^{2} ± 1}{2} or Q = \frac{P^{2} ± 3}{2},

and in particular P = ±1. Therefore, (P, Q) ∈ {(±1, 0), (±1, 1), (±1, 2), (±1, −1)}. Since Q ≠ 0 and U(±1, 1) is a degenerate Lucas sequence with U_{3} = 0, we have (P, Q) = (±1, 2) or (±1, −1), which are exceptions found in Lemma 25.

(2) Let l = 3. Following the method we used for l = 4, we find that the only primes susceptible of having rank 2 or 3 are the primes 2 and 3. By Lemmas 17 and 18, Corollary 15 and the assumption that p ∈ {2, 3} has rank 2 in U, we have

v_{p}(\binom{4n}{n}_{U,3}) = 3j + 2v_{p}(P) + 1,

for every n ≥ 1 of the form n = ρp^{j} − 1, j ≥ 0. Assuming ρ_{U}(p) = 3, we obtain

v_{p}(\binom{4n}{n}_{U,3}) = 3(j + δ_{j}) + 2v_{p}(U_{3}) + 1,

for every n ≥ 1 of the form n = ρp^{j} − 1, with j ≥ 0. Therefore, U_{2} and U_{3} are coprime divisors of 6, positive or negative, where the coprimality is a consequence of the regularity of U. The pair (U_{2}, U_{3}) is then one of the following:

(1, ±1), (1, ±2), (1, ±3), (1, ±6),
(2, ±1), (2, ±3), (3, ±1), (3, ±2), (6, ±1),

assuming P > 0. Since U_{3} = P^{2} − Q, we find (P, Q) to be equal to either (1, 0), (2, 1), or one of the pairs displayed in line 5 of Table 3. However, Q ≠ 0 and U(2, 1) is not Δregular. Hence (P, Q) is in line 5 of Table 3, that is, U(P, Q) is an exception mentioned in Lemma 25.

(3) Let l = 2. By the same method, only 2 may have rank 2 in U. In that case, putting n = ρ2^{j} − 1, we obtain

v_{2}(\binom{3n}{n}_{U,2}) = 2j + v_{p}(P) + 1,

by Lemmas 17 and 18, and Corollary 15. It follows that (P, Q) is either equal to (±2, Q) or to (±1, Q), with Q ≠ 1, since (±1, 1) is a degenerate Lucas sequence. Hence U(P, Q) is an exception mentioned in Lemma 25.

Although C_{U,l} has infinitely many non-integer terms for many pairs (U, l), one can show that the set of n ≥ 1 for which C_{U,2}(n) is an integer has asymptotic density 1. This can potentially be done by following the method used by Ballot [2, Lemma 36]. We state this as a conjecture which we leave as an open problem.

Conjecture 28. Let l ≥ 1 be an integer and U a Δ-regular Lucas sequence. Then the numbers C_{U,l}(n) are integers for almost all n ≥ 1.

However, some adjustments need to be made in the case l = 2 to the proof given by Ballot. These adjustments can be made to prove the conjecture for small values of l, but we think that a different method is required to prove the general case.

7 Appendix

In this appendix section, we display tables that are used in various proofs. The first table below lists n-defective Δ-regular Lucas sequences U(P, Q), with P > 0 and Q ≠ 0, for n ≥ 2. It was put together by Ballot [2], but was first given in different tables [1, 5], where the parametrization was done in terms of P and Δ instead. Note that the parameter i is an integer.

n  (P, Q) with P > 0 and (P, Q) ≠ (2, 1)
2 (1, Q) with Q ≠ 1; (2^{i}, Q) with Q odd, i ≥ 1 and (Q, i) ≠ (1, 1)
3  (P, P^{2} ± 1); (P, P^{2} ± 3^{i}) with 3 ∤ P and i ≥ 0
4  (P, (P^{2} ± 1)/2) with P > 1 odd; (2i, 2i^{2} ± 1) with i ≥ 1
5  (1, −1) (1, 2) (1, 3) (1, 4) (2, 11) (12, 55) (12, 377)

(P, (P^{2} − 1)/3) with 3 ∤ P ≥ 4; (P, (P^{2} ± 3)/3) with 3 | P;

6 (P, (P^{2} − (−2)^{i})/3) with P ≡ ±1 (mod 6), i ≥ 1 and (P, i) ≠ (1, 1);
(P, (P^{2} ± 3 · 2^{i})/3) with P ≡ 3 (mod 6) and i ≥ 1
7  (1, 2) (1, 5)
8  (1, 2) (2, 7)
10  (2, 3) (5, 7) (5, 18)
12  (1, −1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 15)
13  (1, 2)
18  (1, 2)
30  (1, 2)

Table 1: List of all n-defective and Δ-regular Lucas sequences, n ≥ 2.

Let l ≥ 1 be an integer and U = U(P, Q), P > 0, a Lucas sequence. Given a pair (U, l), our second table provides possible choices for a prime p ∤ Q and its rank ρ_{U}(p) that validates the proof of Theorem 27 through the use of Lemma 23. For instance, when U = U(1, 4) and l = 5, we find that (p, ρ_{U}(p)) = (7, 4). By Lemma 23, since ρ_{U}(7) ≤ 5 ≤ min (2ρ_{U}(7), 6) = 6, the numbers C_{U,5}(4 · 7^{j} − 1) are not integers for all j ≥ 1.

Note that the first column displays pairs (P, Q) for Lucas sequences U = U(P, Q), with P > 0, and that the first line displays values of l. An empty cell means that it is not needed to apply Lemma 23 for the corresponding pair (U, l), thus no prime is provided.

U \ l  5  7  8  10  12  13  14  18
(1, 2)  (17, 9) (17, 9) (17, 9) (31, 16)
(1, 5) (11, 5) (11, 5) (71, 9)
(1, 4) (7, 4)  (43, 11)
(1, 3)  (23, 11)
(1, −1)  (89, 11)
(2, 15)  (43, 11)
(2, 3)  (73, 9)
(5, 18)  (31, 8)
(5, 7)  (19, 9)
(2, 7)  (17, 6)
(2, 11) (7, 3)
(2, 55) (17, 3)
(2, 277) (31, 3)

Table 2: Choices of (p, ρ_{U}(p)) for a successful application of Lemma 23, U = U(P, Q), P > 0.

Our last table lists all pairs (U, l), with l ≥ 2 and U a Δ-regular Lucas sequence, such that the numbers

C_{U,l}(n) = \frac{1}{U_{n+1}^{l}} \binom{(l + 1)n}{n, …, n}_{U}

are integers for all but finitely many n ≥ 1.

l  (P, Q) with P > 0
2  (1, Q) with Q ≠ 1; (2, Q) with Q ≠ 1 odd
(1, −5) (1, −2) (1, −1) (1, 2) (1, 3) (1, 4)
3  (1, 7) (2, 3) (2, 5) (2, 7) (3, 7) (3, 8)
(3, 10) (3, 11) (6, 35) (6, 37)
4  (1, −1) (1, 2)
5  (1, −1) (1, 2) (1, 3)
6  (1, −1) (1, 2)
7  (1, 2)
8  (1, 2)

Table 3: List of all multi-Catalan Δ-regular Lucas sequences, l ≥ 2.

8 Acknowledgments

We thank the referee for his or her positive report. We are grateful to Christian Ballot for his mathematical advice and writing commentaries.

References

[1] M. Abouzaid, Les nombres de Lucas et Lehmer sans diviseur primitif, J. Théor. Nombres Bordeaux 18 (2006), 299–313.

[2] C. Ballot, Lucasnomial Fuss-Catalan numbers and related divisibility questions, J. Integer Sequences 21 (2018), Article 18.6.5.

[3] C. Ballot, Divisibility of Fibonomials and Lucasnomials via a general Kummer rule, Fibonacci Quart. 53 (2015), 194–205.

[4] C. Ballot, Divisibility of the middle Lucasnomial coefficient, Fibonacci Quart. 55 (2017), 297–308.

[5] Y. Bilu, G. Hanrot, and P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers. With an appendix by M. Mignotte, J. Reine Angew. Math. 539 (2001), 75–122.

[6] S. B. Ekhad, The Sagan-Savage Lucas-Catalan polynomials have positive coefficients, Arxiv preprint arXiv:1101.4060 [math.CO], 2011. Available at http://arxiv.org/abs/

   1101.4060.

[7] D. Knuth and H. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math. 396 (1989), 212–219.

[8] E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93–146.

[9] H. C. Williams, Édouard Lucas and Primality Testing, Wiley, 1998.

2020 Mathematics Subject Classification: Primary 05A10; Secondary 11B65, 11B39. Keywords: generalized binomial coefficient, multinomial coefficient, Lucasnomial, generalized Catalan number, Lucas sequence, carry, Kummer’s rule, integrality, divisibility.

(Concerned with sequences \underline{A000108}, \underline{A003150}, \underline{A361028}, \underline{A361033}.)

Received July 19 2023; revised versions received July 24 2023; December 15 2023; December 19 2023. Published in Journal of Integer Sequences, December 29 2023.

Return to Journal of Integer Sequences home page.