On the Divisibility of Generalized Central Trinomial Coefficients

Tony D. Noe 14025 NW Harvest Lane Portland, OR 97229 USA

                       noe@sspectra.com

Abstract We present several methods of computing sequences of generalized central trinomial coefficients. We generalize the Schur and Holt congruences for Legendre polynomials in order to prove divisibility properties of these sequences and a conjecture of Deutsch and Sagan.

1 Introduction

For integers a, b, c, we call the coefficient of x^{n} in the expression

(a + bx + cx^{2})^{n}  (1)

the generalized central trinomial coefficient, T_{n}. The sequences {T_{n}}_{n≥0} have combinatorial interpretations and, as shown in Table 1 at the end of this paper, appear frequently in Sloane’s On-Line Encyclopedia of Integer Sequences [6]. By using the binomial theorem twice and the identity \binom{n}{k}\binom{n−k}{n−2k} = \binom{2k}{k}\binom{n}{2k}, we obtain

T_{n} = ∑_{k=0}^{⌊n/2⌋} \binom{2k}{k}\binom{n}{2k}b^{n−2k}(ac)^{k}.  (2)

Assuming b is fixed, note that for any a and c having a fixed nonzero product, the sequences will be the same. Hence, we assume a = 1. Because b = 0 is a degenerate case and the absolute value of T_{n} is the same for b and −b, we can assume b > 0 for divisibility purposes.

As we will see below, an important quantity that determines many properties of the sequence is the the discriminant d = b^{2} − 4ac. There are an infinite number of pairs (b, c) that yield the same discriminant. Also, the discriminant is always of the form 4k or 4k + 1 for some integer k.

We begin by considering several ways of evaluating these sequences. We will see that the representation as values of Legendre polynomials is crucial in studying the divisibility of the sequences by primes.

2 Ordinary Generating Function

Using the solution to an exercise in [4, page 575], we compute the sequence from the ordinary generating function

\frac{1}{\sqrt{1 − 2bx + dx^{2}}} = ∑_{k=0}^{∞} T_{k}x^{k}.  (3)

Euler [3] found this generating function for the case a = b = c = 1.

Observe that when c is a perfect square, the quadratic in the radical factors into the product of two linear terms 1 − (b + 2\sqrt{c})x and 1 − (b − 2\sqrt{c})x having integer coefficients. This factorization allows us to represent equation (3) as the convolution of two sequences of the form

\frac{1}{\sqrt{1 − fx}} = ∑_{k=0}^{∞} \frac{1}{4^{k}} \binom{2k}{k}f^{k}

for constant f. For f = 1, see sequence \underline{A001790}. Forming the convolution, we obtain the interesting

T_{n} = \frac{1}{4^{n}} ∑_{k=0}^{n} \binom{2n − 2k}{n − k}\binom{2k}{k}f^{k}g^{n−k},

where f = b + 2\sqrt{c} and g = b − 2\sqrt{c} are not required to be integers.

3 Recursion Equation

The exercise in [4] states that the recurrence equation for the sequence is

T_{0} = 1, T_{1} = b, T_{n} = \frac{(2n − 1)bT_{n−1} − (n − 1)dT_{n−2}}{n} ,  (4)

which provides an efficient formula for computing T_{n}. Euler [3] found this recursion equation for the case a = b = c = 1. Observe that the recursion actually needs only T_{0} to start; T_{1} can be computed. The recursion also allows us to show that

T_{n+1} ≡ bT_{n} (mod n).

4 Exponential Generating Function

Using the infinite series expansion of the modified Bessel function of the first kind,

I_{0}(x) = ∑_{k=0}^{∞} \frac{(\frac{1}{4}x^{2})^{k}}{(k!)^{2}}

and the infinite series expansion of the exponential function, it is not hard to show that the sequence can be computed from the exponential generating function

e^{bx}I_{0}(2x\sqrt{c}) = ∑_{k=0}^{∞} \frac{T_{k}x^{k}}{k!} .

5 Legendre Polynomials

When the discriminant d is nonzero, the sequence can be defined in terms of the Legendre polynomials

T_{n} = d^{n/2} P_{n}(\frac{b}{\sqrt{d}}),  (5)

which is easy to derive from the generating function for Legendre polynomials

\frac{1}{\sqrt{1 − 2tx + t^{2}}} = ∑_{n=0}^{∞} P_{n}(x)t^{n}.

Note that in equation (5), after multiplying each term of the polynomial P_{n}(b/\sqrt{d}) by d^{n/2}, there will be no occurrences of \sqrt{d} because the degree of the polynomial is n and its terms have either all even or all odd exponents if n is even or odd, respectively.

The cases of d = 1 and d = 0 have particularly simple forms. When d = 1, which occurs when b = 2k + 1 and c = k(k + 1) for integer k ≥ 0, we obtain T_{n} = P_{n}(b). When d = 0, equation (1) can be written as (1 + bx/2)^{2n} and the sequence is

T_{n} = (\frac{b}{2})^{n}\binom{2n}{n}.  (6)

6 Schur and Holt Congruences

The remainder of this paper contains many polynomial congruences. A statement such as

a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0} ≡ 0 (mod p)

in the indeterminant x means that a_{k} ≡ 0 (mod p) for all k. The coefficients a_{k} are allowed to be fractions if the denominator is not divisible by p.

Papers by Carlitz [1] and Wahab [7] have congruences for Legendre polynomials modulo an odd prime p. In particular, Carlitz cites the congruence of Schur: if n is written in base p as

n = n_{0} + n_{1}p + n_{2}p^{2} + ⋯ + n_{r}p^{r} (0 ≤ n_{i} < p),  (7)

then

P_{n}(x) ≡ P_{n_{0}}(x) (P_{n_{1}}(x))^{p} (P_{n_{2}}(x))^{p^{2}} … (P_{n_{r}}(x))^{p^{r}} (mod p).  (8)

This beautiful congruence, which is reminiscent of Lucas’ theorem for binomial coefficients, is proved by Wahab [7, Theorem 6.1]. The congruence implies that the divisibility of P_{n}(x) by p is completely determined by the divisibility of P_{k}(x) by p for 0 ≤ k < p. We may use Fermat’s little theorem to write congruence (8) as

P_{n}(x) ≡ P_{n_{0}}(x) P_{n_{1}}(x^{p}) P_{n_{2}}(x^{p^{2}}) … P_{n_{r}}(x^{p^{r}}) (mod p).

If we replace x by an integer s > 0, then Schur’s congruence still holds and we use Fermat’s little theorem to obtain a congruence without exponents:

P_{n}(s) ≡ P_{n_{0}}(s) P_{n_{1}}(s) P_{n_{2}}(s) … P_{n_{r}}(s) (mod p).  (9)

Another result mentioned by Carlitz and Wahab is due to Holt [5]:

P_{k}(x) ≡ P_{p−k−1}(x) (mod p)  (10)

for k < p. A surprising implication of this congruence is that for (p − 1)/2 < k < p, the polynomial P_{k}(x) (mod p) has degree less than k. It also means, in conjunction with the Schur congruence (8), that the divisibility of P_{n}(x) by p is completely determined by the divisibility of P_{k}(x) by p for 0 ≤ k ≤ (p − 1)/2.

7 Scaled Legendre Polynomials

We would like to use the Schur and Holt congruences to prove divisibility properties of the sequence T_{n} using equation (5). However, the factor of d^{n/2} in that equation makes using the congruences dubious. To remedy this problem, we define a scaled Legendre polynomial having a parameter d:

Q_{n}(x, d) = d^{n/2} P_{n}(\frac{x}{\sqrt{d}}) = \frac{1}{2^{n}} ∑_{k=0}^{⌊n/2⌋}(−1)^{k}\binom{n}{k}\binom{2n − 2k}{n − 2k}d^{k}x^{n−2k},  (11)

which, except for the factor of d^{k} in the summation, is the same as the usual Legendre polynomial definition. The first few polynomials are Q_{0}(x, d) = 1, Q_{1}(x, d) = x, and Q_{2}(x, d) = \frac{1}{2}(3x^{2} − d). This formulation also allows the case of d = 0. Note that if we replace b by the indeterminant x in recursion equation (4), the scaled Legendre polynomials are generated. Equation (5) becomes

T_{n} = Q_{n}(b, d).

In the appendix we prove the Schur and Holt congruences for these scaled Legendre polynomials. Using the same reasoning as in the previous section, congruence (9) becomes

Q_{n}(s, d) ≡ Q_{n_{0}}(s, d) Q_{n_{1}}(s, d) Q_{n_{2}}(s, d) … Q_{n_{r}}(s, d) (mod p),  (12)

which can be used with s = b to obtain the important congruence

T_{n} ≡ T_{n_{0}} T_{n_{1}} T_{n_{2}} … T_{n_{r}} (mod p).  (13)

Let u = (p − 1)/2 − k for k < p. Then, assuming p ∤ d, Holt’s congruence (10) becomes

d^{u} Q_{k}(x, d) ≡ Q_{p−k−1}(x, d) (mod p)

for scaled Legendre polynomials, which leads to

d^{u} T_{k} ≡ T_{p−k−1} (mod p).  (14)

8 Divisibility Properties

The divisibility properties of these sequences are quite interesting. However, as shown in equation (6), the case d = 0 concerns essentially just the central binomial coefficients, whose divisibility is handled by Kummer’s theorem [2, Theorem 5.12].

In the following theorems, we assume that {T_{n}}_{n≥0} is a sequence of generalized central trinomial coefficients with b > 0 and discriminant d ≠ 0. For specific integer n > 0 and prime p, let (n)_{p} = (n_{i}) denote the base p representation of n, as in equation (7). We begin with the case p = 2, which cannot be handled with Legendre polynomials due to the powers of 2 in their denominators.

Theorem 8.1. If p = 2, then T_{n} ≡ b (mod p).

Proof. In the sum in equation (2), the k = 0 term is b^{n}; the other terms are 0 (mod 2) because \binom{2k}{k} is even for k > 0. The theorem follows from b^{n} ≡ b (mod 2) for n > 0.

When p is an odd prime there are four cases to consider: whether or not p | b and whether or not p | d. We do not treat the case of p ∤ bd except in the general case treated by Theorem 8.5. The following three theorems cover the three remaining cases. The easiest case is p dividing both b and d, which we treat first.

Theorem 8.2. If p is an odd prime with p | b and p | d, then p | T_{n}.

Proof. Because d = b^{2} − 4c, p | b and p | d imply p | c. Then, using equation (2), it is easy to see that p divides every term of the sum. Hence, p | T_{n}.

Theorem 8.3. Let p be an odd prime with p | b and p ∤ d. Then the following are true: (1) if n_{i} is odd for some 0 ≤ i ≤ r, then p | T_{n},

(2) if n_{i} is even and n_{i} ≤ (p − 1)/2 for all 0 ≤ i ≤ r, then p ∤ T_{n},

(3) if p | T_{n}, then either n_{i} is odd or n_{i} > (p − 1)/2 for some 0 ≤ i ≤ r.

Proof. Part 1: Using equation (2), b is a factor in every term of the sum when n is odd. Hence, because p | b, we obtain p | T_{n} for odd n. By congruence (13), this divisibility extends to all n such that n_{i} is odd for some 0 ≤ i ≤ r.

Part 2: If n_{i} is even for all i, then n is even. For even n, the last term of equation (2) is \binom{2n}{n}c^{n/2}; all the other terms are divisible by p because those terms have a factor of b, which p divides. Note that d = b^{2} − 4c, p | b, and p ∤ d imply p ∤ c. Because we assume n_{i} ≤ (p − 1)/2 for all i, there are no carries when n is added to n in base p. Hence, by Kummer’s theorem, p ∤ \binom{2n}{n}. Thus, p does not divide \binom{2n}{n}c^{n/2} and we obtain p ∤ T_{n}.

Part 3: this is just the contrapositive of part 2.

Theorem 8.4. Let p be an odd prime with p ∤ b and p | d, then p | T_{n} if and only if (p + 1)/2 ≤ n_{i} ≤ p − 1 for some 0 ≤ i ≤ r.

Proof. From congruence (13), we see that p | T_{n} iff p | T_{n_{i}} for some 0 ≤ i ≤ r. Hence, we assume that n < p. Recall that T_{n} = Q_{n}(b, d). We see from equation (11), that all the terms of Q_{n}(b, d) except the first are divisible by p because p | d. The coefficient of the first term is \binom{2n}{n}b^{n}/2^{n}. Assuming (p + 1)/2 ≤ n ≤ p − 1, the sum n + n has a carry in base p. Therefore, Kummer’s theorem implies that p divides \binom{2n}{n}. We conclude that p | T_{n}. For the converse, we prove the contrapositive. Assume 0 ≤ n ≤ (p − 1)/2. The coefficient of the first term of equation (11) is \binom{2n}{n}b^{n}/2^{n}, which is not divisible by p because 2n and b are not divisible by p. Hence, p ∤ T_{n}.

The next theorem generalizes Deutsch and Sagan [2, Corollary 4.8], which they prove for the case a = b = c = 1.

Theorem 8.5. Let p be a prime. Then p | T_{n} if and only if p | T_{n_{i}} for some 0 ≤ i ≤ r.

Proof. For p = 2, n_{i} is either 0 or 1, and at least one n_{i} is 1 because n > 0. Using Theorem 8.1, we conclude p | T_{n} if and only if p | T_{1}. For odd prime p, the theorem follows from congruence (13).

For the case a = b = c = 1, Deutsch and Sagan [2, Conjecture 5.8] and David W. Wilson conjecture that, for n < p, p divides T_{n} if and only if p divides T_{n−p−1}. The next theorem proves and generalizes the conjecture.

Theorem 8.6. Let p be an odd prime with p ∤ d and n < p. Then p | T_{n} if and only if p | T_{p−n−1}.

Proof. Due to symmetry, we may assume n < (p − 1)/2. Assuming p | T_{n}, congruence (14) yields 0 ≡ T_{p−n−1} (mod p), which means p | T_{p−n−1}. Conversely, assuming p | T_{p−n−1}, congruence (14) yields d^{u}T_{n} ≡ 0 (mod p), which means p | T_{n} if p ∤ d.

The following three theorems compute the values of T_{p}, T_{p−1}, and T_{p−2} (mod p). We see that if p ∤ bd, then p does not divide T_{p}, T_{p−1}, and T_{p−2}. Theorem 8.8 is a rare instance in which Legendre polynomials and the Legendre symbol appear together.

Theorem 8.7. If p is a prime, then T_{p} ≡ b (mod p)

Proof. The theorem follows from equation (2), the fact that \binom{p}{2k} ≡ 0 (mod p) for all indices k > 0, and Fermat’s little theorem.

Theorem 8.8. For odd prime p,

T_{p−1} ≡ d^{(p−1)/2} P_{p−1}(\frac{b}{\sqrt{d}}) ≡ (\frac{d}{p}) (mod p),

where (\frac{d}{p}) is the Legendre symbol.

Proof. The first congruence is equation (5). By congruence (14) and the fact that T_{0} = 1, we obtain T_{p−1} ≡ d^{(p−1)/2} T_{0} ≡ d^{(p−1)/2} (mod p). By Euler’s criterion, (\frac{d}{p}) ≡ d^{(p−1)/2} (mod p). Hence, T_{p−1} ≡ (\frac{d}{p}) (mod p).

Theorem 8.9. For odd prime p,

T_{p−2} ≡ bd^{(p−3)/2} (mod p).

Proof. If p = 3, then T_{1} = b. If p ≥ 5 and p | d, then clearly T_{p−2} ≡ 0 (mod p) by Theorems 8.2 and 8.4. If p ∤ d, then the theorem follows from T_{1} = b and congruence (14).

9 Appendix

Here we prove the generalization of the Schur congruence (8) and Holt congruence (10) for the scaled Legendre polynomials Q(x, d) defined by (11). In several cases, the parameter d forces the proofs to be somewhat different than the ones by Holt [5] and Wahab [7]. In all cases, p is an odd prime and all congruences are modulo p. We use Q_{n} as shorthand for the polynomial Q_{n}(x, d). As mentioned above, Q_{n} satisfies the recursion equation

nQ_{n} = (2n − 1)xQ_{n−1} − (n − 1)dQ_{n−2}  (15)

starting with Q_{0} = 1. Note that because all the denominators in Q_{n} are powers of 2, which are relatively prime to p, we replace equation (15) by the congruence

nQ_{n} ≡ (2n − 1)xQ_{n−1} − (n − 1)dQ_{n−2}.  (16)

We begin by proving four lemmas that are stated, but not proved in Wahab [7, Lemma 6.2]. The first proof is almost identical to Holt’s proof.

Lemma 9.1. If 0 ≤ r < p, then Q_{kp+r} ≡ Q_{r}Q_{kp}.

Proof. The case r = 0 is obvious, so assume 0 < r < p. Letting n = kp+r in congruence (16), we obtain

rQ_{kp+r} ≡ (2r − 1)xQ_{kp+r−1} − (r − 1)dQ_{kp+r−2}.

Observe that with r = 1 we obtain

Q_{kp+1} ≡ xQ_{kp} ≡ Q_{1}Q_{kp}

because Q_{1} = x. Similarly, with r = 2 we have

2Q_{kp+2} ≡ 3xQ_{kp+1} − dQ_{kp} ≡ (3x^{2} − d)Q_{kp} ≡ 2Q_{2}Q_{kp},

which allows us to conclude that Q_{kp+2} ≡ Q_{2}Q_{kp}. Assuming

Q_{kp+r−1} ≡ Q_{r−1}Q_{kp} and Q_{kp+r−2} ≡ Q_{r−2}Q_{kp},

the general case is

rQ_{kp+r} ≡ (2r − 1)Q_{kp+r−1} − (r − 1)dQ_{kp+r−2} ≡ [(2r − 1)Q_{r−1} − (r − 1)dQ_{r−2}]Q_{kp}. However, the bracketed expression is merely the right-hand-side of (16) with n = r. Hence,

rQ_{kp+r} ≡ rQ_{r}Q_{kp}.

Because 0 < r < p, r is relatively prime to p, and we conclude Q_{kp+r} ≡ Q_{r}Q_{kp}.

The next lemma shows the effect of the parameter d in the scaled Legendre polynomials. The parameter d also forces the proof to be slightly different than Holt’s proof. Lemma 9.2. If 1 ≤ r < p and p ∤ d, then d^{r−1}Q_{kp−r} ≡ Q_{r−1}Q_{kp−1}. Proof. The case r = 1 is obvious. Letting n = kp − r + 1 in congruence (16), we obtain

(−r + 1)Q_{kp−r+1} ≡ (−2r + 1)xQ_{kp−r} + rdQ_{kp−r−1},

which is rearranged to yield

rdQ_{kp−r−1} ≡ (2r − 1)xQ_{kp−r} − (r − 1)Q_{kp−r+1}.  (17)

With r = 1 we obtain, using Q_{1} = x,

dQ_{kp−2} ≡ xQ_{kp−1} ≡ Q_{1}Q_{kp−1}.

Similarly, with r = 2 we have

2dQ_{kp−3} ≡ 3xQ_{kp−2} − Q_{kp−1}.

Multiplying by d, and using the result with r = 1, gives us

2d^{2}Q_{kp−3} ≡ 3x^{2}Q_{kp−1} − dQ_{kp−1} ≡ (3x^{2} − d)Q_{kp−1} ≡ 2Q_{2}Q_{kp−1},

and we conclude that d^{2}Q_{kp−3} ≡ Q_{2}Q_{kp−1}. For the case r ≥ 3, we assume

d^{r−2}Q_{kp−r+1} ≡ Q_{r−2}Q_{kp−1} and d^{r−3}Q_{kp−r+2} ≡ Q_{r−3}Q_{kp−1},  (18)

and substitute r − 1 for r in the general case (17), to obtain

(r − 1)dQ_{kp−r} ≡ (2r − 3)xQ_{kp−r+1} − (r − 2)Q_{kp−r+2}.

Multiplying by d^{r−2}, and using the assumptions (18), gives us

d^{r−1}(r − 1)Q_{kp−r} ≡ [(2r − 3)xQ_{r−2} − (r − 2)dQ_{r−3}]Q_{kp−1}.

However, the bracketed expression is merely the right-hand-side of (16) for n = r−1. Hence,

d^{r−1}(r − 1)Q_{kp−r} ≡ (r − 1)Q_{r−1}Q_{kp−1}

For r ≠ 1, r − 1 is relatively prime to p, and we conclude d^{r−1}Q_{kp−r} ≡ Q_{r−1}Q_{kp−1}.

Although the statement of the next lemma is the same as Holt’s, the proof is different.

Lemma 9.3. If 0 ≤ r < p, then Q_{p+r} ≡ x^{p}Q_{r}.

Proof. By Lemma 9.1, we have Q_{p+r} ≡ Q_{r}Q_{p}. From the definition of Q_{p} in equation (11), it is obvious that p divides every term of the sum except the first. The remaining term is \binom{2p}{p}x^{p}/2^{p}. Hence, Q_{p} ≡ Ax^{p} for some constant A that is the solution to the congruence 2^{p}A ≡ \binom{2p}{p}. By Fermat’s little theorem, 2^{p} ≡ 2. Also, \binom{2p}{p} ≡ \binom{2}{1} = 2. We conclude that A ≡ 1, proving the lemma.

The following lemma is a generalization of Holt’s congruence mentioned earlier in this paper. Its statement and proof are different than Holt’s version.

Lemma 9.4. If 0 ≤ r < p and p ∤ d, then Q_{p−r−1} ≡ d^{u}Q_{r}, where u = (p − 1)/2 − r.

Proof. Letting k = 1 and substituting r + 1 for r in Lemma 9.2, we have

d^{r}Q_{p−r−1} ≡ Q_{r}Q_{p−1}.  (19)

From the definition of Q_{p−1} in equation (11), we use Kummer’s theorem to show that p divides every term of the sum except the last. The remaining term is the constant

\frac{(−1)^{m}}{2^{p−1}} \binom{p − 1}{m}d^{m},

where m = (p − 1)/2. But \binom{p−1}{m} ≡ (−1)^{m} for any m, making the constant d^{m}/2^{p−1}. Calling this constant A and using Fermat’s little theorem as in the previous lemma, we obtain A ≡ d^{(p−1)/2}. Thus, equation (19) becomes

d^{r}Q_{p−r−1} ≡ d^{(p−1)/2}Q_{r}.

Dividing by d^{r} proves the lemma.

The following lemma is proved by Wahab for the usual Legendre polynomials.

Lemma 9.5. Q_{kp} ≡ (Q_{k})^{p}.

Proof. By the definition of scaled Legendre polynomials (11),

2^{kp}Q_{kp}(x, d) = ∑_{j=0}^{⌊kp/2⌋}(−1)^{j}\binom{kp}{j}\binom{2kp − 2j}{kp − 2j}d^{j}x^{kp−2j}.

However, \binom{kp}{j} ≡ 0 for j ≠ ip and \binom{kp}{ip} ≡ \binom{k}{i}. Consequently,

2^{kp}Q_{kp}(x, d) ≡ ∑_{i=0}^{⌊k/2⌋}(−1)^{ip}\binom{k}{i}\binom{2k − 2i}{k − 2i}d^{ip}x^{kp−2ip}.

Using Fermat’s little theorem several times, we obtain

2^{kp}Q_{kp}(x, d) ≡ 2^{k}Q_{k}(x^{p}, d) ≡ 2^{kp}(Q_{k}(x, d))^{p}.

Dividing by 2^{kp} proves the lemma.

The following theorem proves Schur’s congruence for scaled Legendre polynomials. The proof is identical to Wahab’s for the usual Legendre polynomials.

Theorem 9.1. If n = n_{0} + n_{1}p + n_{2}p^{2} + ⋯ + n_{r}p^{r}, with 0 ≤ n_{i} < p, then

Q_{n} ≡ Q_{n_{0}} (Q_{n_{1}})^{p} (Q_{n_{2}})^{p^{2}} … (Q_{n_{r}})^{p^{r}}.

Proof. Induction on n is used. The statement is true for 0 ≤ n < p. By Lemma 9.1,

Q_{n} ≡ Q_{n_{0}} Q_{n_{1}p+n_{2}p^{2}+···+n_{r}p^{r}}.

By Lemma 9.5,

Q_{n} ≡ Q_{n_{0}} (Q_{n_{1}+n_{2}p+···+n_{r}p^{r−1}})^{p}.

By the inductive assumption,

Q_{n} ≡ Q_{n_{0}} [Q_{n_{1}} (Q_{n_{2}})^{p} ⋯ (Q_{n_{r}})^{p^{r−1}}]^{p}.

Hence,

Q_{n} ≡ Q_{n_{0}} (Q_{n_{1}})^{p} (Q_{n_{2}})^{p^{2}} ⋯ (Q_{n_{r}})^{p^{r}}.

10 Acknowledgment

The author thanks Bruce E. Sagan for his valuable comments. The author also thanks the referee for carefully reading this paper and making many helpful comments.

References

[1] Leonard Carlitz, Congruences properties of the polynomials of Hermite, Laguerre and Legendre, Math. Zeitschr. 59 (1954), 474–483.

[2] Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215.

[3] Leonhard Euler, Observationes analyticae, Novi Commentarii Acad. Sci. Imper. Petropolitanae 11 (1765) 1767, 124–143. Reprinted in Opera Omnia, Series I, vol. 15, 50–69.

[4] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1994, 2nd edition.

[5] J. B. Holt, On the irreducibility of Legendre polynomials, II, Proc. London Math. Soc. (2), 12 (1913), 126–132.

[6] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at www.research.att.com/∼njas/sequences.

[7] J. H. Wahab, New cases of irreducibility for Legendre polynomials, Duke Math J. 19 (1952), 165–176.

a b c  d A-number Comments
1 1 1 -3 \underline{A002426} central trinomial coefficients
1 1 2 -7 \underline{A084601}
1 1 3 -11 \underline{A084603}
1 1 4 -15 \underline{A084605}
1 1 5 -19 \underline{A098264}
1 1 6 -23 \underline{A098265}
1 1 8 -31 \underline{A098329}
1 1 12 -47 \underline{A098439}
1 1 15 -59 \underline{A098440}
1 1 16 -63 \underline{A098441}
1 1 24 -95 \underline{A098442}
1 1 -1  5 \underline{A098331}
1 1 -2  9 \underline{A098332}
1 1 -3 13 \underline{A098333}
1 1 -4 17 \underline{A098334}
1 2 1  0 \underline{A000984} binomial(2n, n)
1 2 2 -4 \underline{A006139}
1 2 3 -8 \underline{A084609}
1 2 4 -12 \underline{A098453}
1 2 5 -16 \underline{A084770}
1 2 -1  8 \underline{A098335}
1 2 -2 12 \underline{A098336}
1 2 -3 16 \underline{A012000} 4^{n}P_{n}(1/2)
1 2 -4 20 \underline{A098337}
1 3 1  5 \underline{A026375}
1 3 2  1 \underline{A001850} P_{n}(3), central Delannoy numbers
1 3 5 -11 \underline{A098444}
1 3 -1 13 \underline{A098338}
1 3 -2 17 \underline{A098339}
1 3 -3 21 \underline{A098340}
1 3 -4 25 \underline{A098341}
1 4 1 12 \underline{A081671}
1 4 2  8 \underline{A080609}
1 4 3  4 \underline{A069835} 2^{n}P_{n}(2)
1 4 4  0 \underline{A059304} 2^{n} binomial(2n, n)
1 4 5 -4 \underline{A098443}
1 4 6 -8 \underline{A106258}
1 5 1 21 \underline{A098409}
1 5 4  9 \underline{A084771}
1 5 6  1 \underline{A006442} P_{n}(5)
1 6 1 32 \underline{A098410}
1 6 9  0 \underline{A098658} 3^{n} binomial(2n, n)
1 7 1 45 \underline{A104454}
1 7 12  1 \underline{A084768} P_{n}(7)
1 8 16  0 \underline{A098430} 4^{n} binomial(2n, n)
1 9 20  1 \underline{A084769} P_{n}(9)

Table 1: Generalized Central Trinomial Coefficients 2000 Mathematics Subject Classification: Primary 05A19; Secondary 11B07. Keywords: central trinomial coefficient, Legendre polynomials, divisibility, congruences.

(Concerned with sequences \underline{A000984}, \underline{A001790}, \underline{A001850}, \underline{A002426}, \underline{A006139}, \underline{A006442}, \underline{A012000}, \underline{A026375}, \underline{A059304}, \underline{A069835}, \underline{A080609}, \underline{A081671}, \underline{A084601}, \underline{A084603}, \underline{A084605}, \underline{A084609}, \underline{A084768}, \underline{A084769}, \underline{A084770}, \underline{A084771}, \underline{A098264}, \underline{A098265}, \underline{A098329}, \underline{A098331}, \underline{A098332}, \underline{A098333}, \underline{A098334}, \underline{A098335}, \underline{A098336}, \underline{A098337}, \underline{A098338}, \underline{A098339}, \underline{A098340}, \underline{A098341}, \underline{A098409}, \underline{A098410}, \underline{A098430}, \underline{A098439}, \underline{A098440}, \underline{A098441}, \underline{A098442}, \underline{A098443}, \underline{A098444}, \underline{A098453}, \underline{A098658}, \underline{A104454}, and \underline{A106258}.)

Received December 2 2005; revised version received June 28 2006. Published in Journal of Integer Sequences, July 5 2006.

Return to Journal of Integer Sequences home page.