On Divisibility of Narayana Numbers by Primes

Miklós Bóna Department of Mathematics University of Florida Gainesville, FL 32611 USA

                       bona@math.ufl.edu

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 USA

                      sagan@math.msu.edu

Abstract Using Kummer’s theorem, we give a necessary and sufficient condition for a Narayana number to be divisible by a given prime. We use this to derive certain properties of the Narayana triangle.

1 The main theorem

Let ℕ denote the nonnegative integers and let k, n ∈ ℕ. The Narayana numbers [10, A001263] can be defined as

N(n, k) = \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}

where 0 ≤ k < n. The Narayana numbers (in fact, a q-analogue of them) were first studied by MacMahon [6, Article 495] and were later rediscovered by Narayana [7]. They are closely related to the Catalan numbers [10, A000108]

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

and in fact ∑_{k} N(n, k) = C_{n}. The Narayana numbers can be arranged in a triangular array with N(n, k) in row n and column k so that the row sums are the Catalan numbers. Like the numbers C_{n}, the numbers N(n, k) have many combinatorial interpretations; see, for example, the article of Sulanke [11].

The main result of this note is a characterization of when N(n, k) is divisible by a given prime p. To state it, we need some notation. Let Δ_{p}(n) = (n_{i}) denote the sequence of digits of n in base p so that n = ∑_{i} n_{i}p^{i}. Similarly we define Δ_{p}(k) = (k_{i}). If we are considering k ≤ n then it will be convenient to extend the range of definition of (k_{i}) so that both sequences have the same length by setting k_{i} = 0 if p^{i} > k. The order of n modulo p is the largest power of p dividing n and will be denoted ω_{p}(n). As usual, k|n means that k divides n.

Kummer’s theorem [5] gives a useful way of finding the order of binomial coefficients. For example, Knuth and Wilf [4] used it to find the highest power of a prime which divides a generalized binomial coefficient.

Theorem 1.1 (Kummer) Let p be prime and let Δ_{p}(n) = (n_{i}), Δ_{p}(k) = (k_{i}). Then ω_{p}\binom{n}{k} is the number of carries in performing the addition Δ_{p}(k) + Δ_{p}(n − k). Equivalently, it is the number of indices i such that either k_{i} > n_{i} or there exists an index j < i with k_{j} > n_{j} and k_{j+1} = n_{j+1}, …, k_{i} = n_{i}.

Now everything is in place to state and prove our principal theorem.

Theorem 1.2 Let p be prime. Also let Δ_{p}(n) = (n_{i}), Δ_{p}(k) = (k_{i}) and ω = ω_{p}(n). Then p ∤ N(n, k) if and only if one of the two following conditions hold:

1. When p ∤ n we have

(a) k_{i} ≤ n_{i} for all i, and

(b) k_{j} < n_{j} where j is the first index with k_{j} ≠ p − 1 (if such an index exists).

2. When p | n we have

(a) k_{i} ≤ n_{i} for all i > ω, and

(b) k_{ω} < n_{ω}, and

(c) k_{0} = k_{1} = … = k_{ω−1} = \{ \begin{matrix}0 & if p | k; \\ p − 1 & if p ∤ k. \end{matrix}

Proof First suppose that p is not a divisor of n. Then p does not divide N(n, k) if and only if p divides neither \binom{n}{k} nor \binom{n}{k+1}. By Kummer’s theorem this is equivalent to k_{i} ≤ n_{i} and (k + 1)_{i} ≤ n_{i} for all i. However, if j is the first index with k_{j} ≠ p − 1, then we have

(k + 1)_{i} = \{ \begin{matrix}0 & if i < j; \\ (k)_{i} + 1 & if i = j; \\ (k)_{i} & if i > j. \end{matrix}

So these conditions can be distilled down to insisting that k_{j} < n_{j} in addition to k_{i} ≤ n_{i} for all other i.

Now consider what happens when p divides n. Suppose first that p also divides k. So (n)_{i} = 0 for i < ω, which is a nonempty set of indices, and (k + 1)_{0} = 1. It follows there are at least ω carries in computing Δ_{p}(k + 1) + Δ_{p}(n − k − 1). By Kummer’s theorem again, ω_{p}\binom{n}{k+1} ≥ ω. So p does not divide N(n, k) if and only if it does not divide \binom{n}{k} and ω_{p}\binom{n}{k+1} = ω. Applying Kummer’s theorem once more shows that this will happen exactly when k_{i} ≤ n_{i} for all i with k_{ω} < n_{ω}. So in particular k_{i} = 0 for i < ω since then n_{i} = 0. This completes the case when p divides both n and k.

Finally, suppose p | n but p ∤ k. Arguing as in the previous paragraph, we see that p is not a divisor of N(n, k) if and only if ω_{p}\binom{n}{k} = ω and p does not divide \binom{n}{k+1}. But if p is not a divisor of \binom{n}{k+1} then, using Kummer’s theorem, we must have (k + 1)_{i} = 0 for i < ω. So (k)_{i} = p − 1 for i < ω. Conditions 2(b) and (c) also follow as before. This completes the demonstration of the theorem.

2 Applications

It is well known that C_{n} is odd if and only if n = 2^{m} − 1 for some m. For a combinatorial proof of this which in fact establishes ω_{2}(C_{n}), see the article of Deutsch and Sagan [2]. Analogously, all the entries of the nth row of the Narayana triangle are odd. This is a special case of the following result.

Corollary 2.1 Let p be prime and let n = p^{m} − 1 for some m ∈ ℕ. Then for all k, 0 ≤ k ≤ n − 1, we have p ∤ N(n, k).

Proof By Theorem 1.2 we just need to verify that 1(a) and (b) hold for all k. However, they must be true because n_{i} = p − 1 for all i.

We clearly can not have a row of the Narayana triangle where every element is divisible by p since N(n, 0) = N(n, n − 1) = 1 for all n. But we can ensure that every entry except the first and last is a multiple of p.

Corollary 2.2 Let p be prime and let n = p^{m} for some m ∈ ℕ. Then p | N(n, k) for 1 ≤ k ≤ n − 2.

Proof Suppose that n = p^{m} and that p does not divide N(n, k). If p divides k, then condition 2(c) forces k = 0. If p does not divide k, then the same condition forces k = n − 1. So these are the only two numbers not divisible by p in the nth row of Narayana’s triangle.

3 Comments and Questions

I. Clearly one could use the same techniques presented here to determine ω_{p}(N(n, k)). However, the cases become complicated enough that it is unclear whether this would be an interesting thing to do.

II. The characterization in Theorem 1.2 is involved enough that it may be hopeless to ask for a combinatorial proof. However, there should be a combinatorial way to derive the simpler statements in Corollaries 2.1 and 2.2, although we have not been able to do so.

As has already been mentioned, the order ω_{2}(C_{n}) can be established by combinatorial means, specifically through the use of group actions. Unfortunately, the action used by Deutsch and Sagan [2] is not sufficiently refined to preserve the objects counted by N(n, k). For more information about how such methods can be used to prove congruences, the reader can consult Sagan’s article [8] which also contains a survey of the literature.

Deutsch [1], Eğecioğlu [3], and Simion and Ullman [9] have all found combinatorial ways to explain the fact that C_{n} is odd if and only if n = 2^{m} − 1 for some m. Perhaps one or more of the viewpoints in these papers could be adapted to the Narayana numbers.

Acknowledgment. We would like to thank Robert Sulanke for valuable references and discussions, and to Neil White for bringing the problem to our attention.

References

[1] E. Deutsch, An involution on Dyck paths and its consequences, Discrete Math. 204 (1999), 163–166.

[2] E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, preprint, available at http://www.math.msu.edu/∼sagan/.

[3] Ö. Eğecioğlu, The parity of the Catalan numbers via lattice paths, Fibonacci Quart. 21 (1983) 65–66.

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

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

[6] P. A. MacMahon, Combinatorial Analysis, Vols. 1 and 2, Cambridge University Press, 1915,1916; reprinted by Chelsea, 1960.

[7] T. V. Narayana, Sur les treillis formés par les partitions d’une unties et leurs applications à la théorie des probabilités, C. R. Acad. Sci. Paris 240 (1955), 1188–1189.

[8] B. E. Sagan, Congruences via Abelian groups, J. Number Theory 20 (1985), 210–237.

[9] R. Simion and D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991), 193–206.

[10] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences,” available at http://www.research.att.com/∼njas/sequences/.

[11] R. A. Sulanke, The Narayana distribution, J. Statist. Plann. Inference 101 (2002), 311–326.

2000 Mathematics Subject Classification: Primary 11B50; Secondary 05A10, 11A07, 11B64. Keywords: divisibility, Narayana numbers.

(Concerned with sequences \underline{A001263} and \underline{A000108}.)

Received April 7 2005; revised version received April 14 2005. Published in Journal of Integer Sequences, May 15 2005.

Return to Journal of Integer Sequences home page.