INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5(1) (2005), #A21

ON 2-ADIC ORDERS OF STIRLING NUMBERS OF THE SECOND KIND

Stefan De Wannemacker

Department of Mathematics, University College Dublin, Belfield, Dublin 4, Ireland

                           sdwannem@maths.ucd.ie

Received: 7/15/04, Revised: 8/11/05, Accepted: 9/26/05, Published: 10/4/05

Abstract

We prove that for any k = 1, …, 2^{n} the 2-adic order of the Stirling number S(2^{n}, k) of the second kind is exactly d(k) − 1, where d(k) denotes the number of 1’s among the binary digits of k. This confirms a conjecture of Lengyel.

1. Introduction

For a nonzero integer m, if 2^{h} is the highest power of two dividing m, then we say that the 2-adic order ρ_{2}(m) of m is h. In this paper ρ_{2}(·) is called the 2-adic valuation function. Legendre observed that if n ∈ ℕ = {0, 1, 2, … } then ρ_{2}(n!) = n − d(n), where d(n) is the number of 1’s in the binary representation of n, in other words d(n) = ∑_{λ=0}^{∞} ε_{λ}(n) if n = ∑_{λ=0}^{∞} ε_{λ}(n)2^{λ} with ε_{λ}(n) ∈ \{0, 1\}. Kummer proved that ρ_{2} (\binom{n}{k}) = d(k)+d(n−k)−d(n) whenever 0 ≤ k ≤ n. Let n ∈ ℕ. The Stirling numbers S(n, k) (k ∈ ℕ) of the second kind are given by

x^{n} = ∑_{k=0}^{∞} S(n, k)(x)_{k},

where (x)_{k} = x(x − 1)(x − 2) … (x − k + 1) for k ∈ ℕ \ {0} and (x)_{0} = 1. Actually S(n, k) is the number of ways in which it is possible to partition a set with n elements into exactly k nonempty subsets. For more details and basic results on Stirling numbers of the second kind we refer the reader to [2] and [4]. In this paper we study 2-adic orders of Stirling numbers of the second kind, and establish the following theorem which was conjectured by T.Lengyel [3] and verified by him in some special cases.

Theorem 1. Let n, k ∈ ℕ and 1 ≤ k ≤ 2^{n}. Then we have

ρ_{2}(S(2^{n}, k)) = d(k) − 1.

In the next section we reveal some useful properties of Stirling numbers of the second kind. We are going to prove Theorem 1 in Section 3 on the basis of Section 2.

2. Auxiliary results on Stirling numbers of the second kind

The following identity relates the Stirling numbers of the second kind S(n + m, ·) to S(n, ·) and S(m, ·).

Theorem 2. Let n, m, k ∈ ℕ such that 0 ≤ k ≤ n + m. Then

S(n + m, k) = ∑_{i=0}^{k} ∑_{j=i}^{k} \binom{j}{i}\frac{(k − i)!}{(k − j)!} S(n, k − i)S(m, j).

Proof. Let n, m ∈ ℕ. Then

x^{n+m} = x^{n}x^{m} = ∑_{r=0}^{n} S(n, r)(x)_{r} ∑_{j=0}^{m} S(m, j)(x)_{j}

= ∑_{r=0}^{n} S(n, r)(x)_{r} ∑_{j=0}^{m} j!S(m, j)\binom{x}{j}

= ∑_{r=0}^{n} S(n, r)(x)_{r} ∑_{j=0}^{m} j!S(m, j) ∑_{i=0}^{j} \binom{x − r}{i}\binom{r}{j − i}

(by the Chu-Vandermonde identity)

= ∑_{r=0}^{n} S(n, r) ∑_{j=0}^{m} S(m, j) ∑_{i=0}^{j} \frac{j!}{i!}\binom{r}{j − i}(x)_{r+i}

Thus, for any k = 0, 1, …, n + m we have

S(n + m, k) = ∑_{i=0}^{k} ∑_{j=i}^{k} \frac{j!}{i!}\binom{k − i}{j − i} S(n, k − i)S(m, j)

= ∑_{i=0}^{k} ∑_{j=i}^{k} \binom{j}{i}\frac{(k − i)!}{(k − j)!} S(n, k − i)S(m, j).

Remark: Stirling numbers of the second kind occur in a natural way while making calculations in the Witt ring (see [1] for further details). It was in this context that the previous identity arose.

Lemma 1. Let m, n ∈ ℕ. Then

d(m + n) ≤ d(m) + d(n)

and equality holds if and only if

∑_{λ=0}^{∞} ε_{λ}(m)ε_{λ}(n) = 0,

i.e., when m and n have no non-zero binary digit in common.

Proof. If m and n have no non-zero binary digit in common then it is obvious that d(m+n) = ∑ ε_{λ}(m + n) = ∑(ε_{λ}(m) + ε_{λ}(n)) = d(m) + d(n). On the other hand, suppose that m and n have a non-zero binary digit in common. Let us say that λ_{0} is the lowest natural number such that ε_{λ_{0}}(m) = ε_{λ_{0}}(n) = 1. Then it is clear that ε_{λ_{0}}(m + n) = 0 and 1 is added to ε_{λ_{0}+1}(m) + ε_{λ_{0}+1}(n) to obtain an expression for ε_{λ_{0}+1}(m + n). Anyhow, at least one non-zero binary digit is lost in d(m + n).

Remark: The case d(m+n) = d(m)+d(n)−1 occurs if and only if ε_{λ_{0}+1}(m) = ε_{λ_{0}+1}(n) = 0 with λ_{0} the unique natural number such that ε_{λ_{0}}(m) = ε_{λ_{0}}(n) = 1.

A new lower bound on the 2-adic order of Stirling numbers of the second kind can be obtained as follows.

Theorem 3. Let n, k ∈ ℕ and 0 ≤ k ≤ n. Then

ρ_{2} (S(n, k)) ≥ d(k) − d(n).

Proof. We use induction on n.

For n = 0, ρ_{2}(S(0, 0)) = ρ_{2}(1) ≥ d(0) − d(0).

Assume now that the above inequality is true for all i < n. We will prove the theorem for n. Observe that for k = 0 the result is obviously true. Let 1 ≤ k ≤ n. The Stirling numbers of the second kind satisfy the well-known ‘vertical’ recurrence relation

S(n, k) = ∑_{i=k−1}^{n−1} \binom{n − 1}{i}S(i, k − 1).

Combining this with the ‘triangular’ recurrence relation

S(n, k) = S(n − 1, k − 1) + kS(n − 1, k)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5(1) (2005), #A21 4

we obtain

kS(n, k) = ∑_{i=k−1}^{n−1} \binom{n}{i}S(i, k − 1).

Thus

ρ_{2}(kS(n, k)) = ρ_{2} ( ∑_{i=k−1}^{n−1} \binom{n}{i}S(i, k − 1))

≥ min_{k−1≤i≤n−1}\{ρ_{2} (\binom{n}{i}) + d(k − 1) − d(i)\}

(by the induction hypothesis)

= min_{k−1≤i≤n−1}{d(n − i) + d(k − 1) − d(n)}

(by the Kummer identity)

= d(k − 1) − d(n) + 1.

So,

ρ_{2}(S(n, k)) ≥ d(k − 1) − ρ_{2}(k) + 1 − d(n)
= d(k) − d(n).

3. Proof of Lengyel’s conjecture We use induction on n. For n = 0, ρ_{2}(S(1, 1)) = ρ_{2}(1) = 0 = d(1) − 1. We assume the theorem is true for all powers 2^{i} where i < n. We will prove that the theorem holds for 2^{n}. By Theorem 2

S(2^{n}, k) = ∑_{i=0}^{k} ∑_{j=i}^{k} \binom{j}{i}\frac{(k − i)!}{(k − j)!} S(2^{n−1}, k − i)S(2^{n−1}, j).  (1)

We will take a closer look at the 2-adic valuation of each term in this sum (1).

ρ_{2} (\binom{j}{i}\frac{(k − i)!}{(k − j)!} S(2^{n−1}, k − i)S(2^{n−1}, j))

= ρ_{2} (\binom{j}{i}) + ρ_{2}((k − i)!) − ρ_{2}((k − j)!) + ρ_{2}(S(2^{n−1}, k − i)) + ρ_{2}(S(2^{n−1}, j))

= ρ_{2} (\binom{j}{i}) + ρ_{2}((k − i)!) − ρ_{2}((k − j)!) + d(k − i) + d(j) − 2

(by the induction hypothesis)

= d(i) + d(j − i) − d(j) + (k − i) − d(k − i) − (k − j) + d(k − j) + d(k − i) + d(j) − 2

(by the Kummer and Legendre identities)

= d(i) + d(j − i) + j − i + d(k − j) − 2.

The inequality of Lemma 1 implies that

d(i) + d(j − i) + j − i + d(k − j) − 2 ≥ d(j) + j − i + d(k − j) − 2 ≥ d(k) − 2 + j − i.

Since j ≥ i, the 2-adic valuation of every term in the sum is at least d(k) − 2. To prove that the 2-adic valuation of the global sum (1) equals d(k) − 1 we will calculate the number of terms with 2-adic valuation d(k) − 2 and the number of terms with 2-adic valuation d(k)−1. These two results together will show that the 2-adic valuation of (1) equals d(k)−1.

For k = 1 the theorem holds since ρ_{2}(S(2^{n}, 1)) = ρ_{2}(1) = 0 = d(1) − 1, for all n ∈ ℕ. So assume k ≠ 1.

Case 1 : d(i) + d(j − i) + j − i + d(k − j) − 2 = d(k) − 2.

Since d(i) + d(j − i) + d(k − j) ≥ d(k) and j ≥ i, this situation can occur only when j = i and d(i) + d(k − i) = d(k). By Lemma 1 this holds only when i and k − i have no non-zero binary digit in common, or equivalently, when ε_{λ}(i) + ε_{λ}(k − i) = ε_{λ}(k), for all λ ∈ ℕ. If ε_{λ}(k) = 1 (this occurs d(k) times), the possible values for ε_{λ}(i) are 0 and 1. If ε_{λ}(k) = 0, then ε_{λ}(i) = 0 as well. So, for a given k, there are 2^{d(k)} possibilities for i = j. We need to modify this number of possibilities since it includes the non-occurring situations i = j = 0 and i = j = k. This means we have 2^{d(k)} − 2 terms in (1) with 2-adic valuation d(k) − 2. In the case where d(k) = 1, i.e. k = 2^{m}, there are no terms satisfying the condition. When d(k) > 1, these 2^{d(k)} − 2 terms contribute, in total, M2^{d(k)−1} to (1). We will show that M is odd. Let O(i) be the odd part of S(2^{n−1}, i). Consider the sum in this case

\begin{matrix}∑_{{i=1 \atop d(i)+d(k−i)=d(k)}}^{k−1} S(2^{n−1}, k − i)S(2^{n−1}, i) \\ = ∑_{{i=1 \atop d(i)+d(k−i)=d(k)}}^{k−1} O(k − i)O(i)2^{d(k)−2}. \end{matrix}

The latter expression is invariant under switching i and k − i and since i = k/2 (in the case k even) never occurs (d(k/2) + d(k/2) = 2d(k) ≠ d(k)) we obtain

∑_{i=1 ; {d(i)+d(k−i)=d(k) \atop i<k/2}}^{k−1} O(k − i)O(i)2^{d(k)−1}.

This last expression consists of an odd number, 2^{d(k)−1} − 1, of terms, so it contributes, in total, M2^{d(k)−1} to (1), where M is odd.

Case 2 : d(i) + d(j − i) + j − i + d(k − j) − 2 = d(k) − 1.

Since d(i) + d(j − i) + d(k − j) ≥ d(k) and j ≥ i, this situation can occur only when j = i + 1 and d(i) + d(k − i − 1) = d(k) − 1 or when j = i and d(i) + d(k − i) = d(k) + 1.

Case 2.1 : d(i) + d(k − i − 1) = d(k) − 1 and j = i + 1.

Since d(k −1) ≤ d(i)+d(k −i−1) = d(k)−1, k must be odd. We have d(i)+d((k −1)−i) = d(k − 1). As in Case 1, there are 2^{d(k−1)} possible values for i (the case i = k doesn’t occur and the case i = 0 and j = 1 is allowed). This is an even number of terms since k ≠ 1.

Case 2.2 : d(i) + d(k − i) = d(k) + 1 and j = i.

By Lemma 1 this can occur only when there is just one value of λ ∈ ℕ for which ε_{λ}(i) = ε_{λ}(k−i) = 1. Moreover one must have ε_{λ+1}(i) = ε_{λ+1}(k−i) = 0. This implies that ε_{λ}(k) = 0 and ε_{λ+1}(k) = 1. Following the same reasoning as in Case 1 with the remaining d(k) − 1 non-zero binary digits of k, we have 2^{d(k)−1} possibilities for i (the cases i = 0 and i = k don’t occur). So there are 2^{d(k)−1} terms in (1) which come under Case 2.2 (and thus have 2-adic valuation d(k) − 1). When d(k) = 1, this number is 1, otherwise it is even.

After considering all the possible cases and counting the number of terms with 2-adic valuation d(k) − 2 and 2-adic valuation d(k) − 1, we can conclude that ρ_{2}(S(2^{n}, k)) = d(k) − 1.

An overview of all the cases is given in the following table.

Case 1

coefficient of 2d(k)−2

Case 2.1

coefficient of 2d(k)−1

Case 2.2

coefficient of 2d(k)−1

coefficient of 2^{d(k)−1}

d(k) = 1 (k ≠ 1)  0  0  odd  odd
d(k) > 1 & k odd  2 x odd  even  even  odd
d(k) > 1 & k even  2 x odd  0  even  odd

References

[1] S. De Wannemacker, Polynomials annihilating the Witt ring and 2-adic valuation of Stirling numbers, Math. Nachr. (to appear).

[2] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, a foundation for computer science, Addison Wesley, 1989.

[3] T. Lengyel, On the divisibility by 2 of the Stirling numbers of the second kind, The Fibonacci Quarterly 32, 1994, pp. 194–201.

[4] L. Comtet, Advanced Combinatorics, D. Reidel, 1974.