An Elementary Proof of the Explicit Formula for the Möbius Number of the Odd Partition Poset

Kenneth M. Monks Department of Mathematics

Front Range Community College — Boulder County Campus 2190 Miller Drive Longmont, CO 80537 USA

             kenneth.monks@frontrange.edu

Abstract

The Möbius number of a finite poset is a very useful combinatorial invariant of the poset that generalizes the classical number-theoretic Möbius function. The Möbius number of the poset of partitions Π_{n} of a set with n elements is well-known. A related poset, the subposet consisting only of partitions that use odd part size or the maximum element {{1, 2, …, n}}, written Π_{n}^{odd}, arises in similar combinatorial settings. In this paper, we compute the Möbius numbers of all Π_{n}^{odd} as follows:

μ (Π_{n}^{odd}) = \begin{cases}(−1)^{(n−1)/2} ((n − 2)!!)^{2} , & if n is odd; \\ (−1)^{n/2}(n − 1) ((n − 3)!!)^{2} , & if n is even. \end{cases}

This result was first stated as known by Stanley and has since been proven by Sundaram and Wachs. They constructed versions of the formula above by respectively using symmetric function/representation theory and topological/simplicial complex techniques. In this paper, we provide a new proof using only elementary combinatorial techniques and the WZ algorithm.

1 Introduction and statement of main results

One of the most natural and well-studied posets is the poset Π_{n} of partitions of an n-element set ordered by refinement. A related object is the subposet of partitions of an n-element set using only odd-size parts and the maximum element {{1, 2, …, n}}. We call this the odd-partition poset and denote it Π_{n}^{odd}. For example, Figure 1 illustrates Π_{4}^{odd}.

Figure 1: The Hasse Diagram for Π_{4}^{odd}

This poset arose in the author’s PhD work when applying Shareshian’s techniques [6] to a problem of Stanley [8]. If P is a finite poset with minimum and maximum elements, the Möbius number μ(P) is a much sought-after combinatorial invariant of P (see Section 2 for a formal definition). Computing the Möbius numbers for some small values of n reveals the following pattern:

μ (Π_{1}^{odd}) = 1
μ (Π_{2}^{odd}) = −1
μ (Π_{3}^{odd}) = −1 · 1
μ (Π_{4}^{odd}) = −1 · 1 · −3
μ (Π_{5}^{odd}) = −1 · 1 · −3 · 3
μ (Π_{6}^{odd}) = −1 · 1 · −3 · 3 · −5
μ (Π_{7}^{odd}) = −1 · 1 · −3 · 3 · −5 · 5
μ (Π_{8}^{odd}) = −1 · 1 · −3 · 3 · −5 · 5 · −7
μ (Π_{9}^{odd}) = −1 · 1 · −3 · 3 · −5 · 5 · −7 · 7
μ (Π_{10}^{odd}) = −1 · 1 · −3 · 3 · −5 · 5 · −7 · 7 · −9
⋮

This pattern continues forever, which we state more formally below.

Theorem 1 (Stanley). Let Π_{n}^{odd} be the odd-partition poset of an n-element set. Then the Möbius number μ(Π_{n}^{odd}) is given by

μ(Π_{n}^{odd}) = \begin{cases}(−1)^{(n−1)/2} ((n − 2)!!)^{2} , & if n is odd; \\ (−1)^{n/2}(n − 1) ((n − 3)!!)^{2} , & if n is even \end{cases}

where k!! denotes the double-factorial, the product of all integers between 1 and k with the same parity as k.

This formula was stated as known by Stanley on page 291 of a paper of Calderbank, Hanlon, and Robinson [1] in 1986. However, no reference or proof is given. In 1994, Sundaram [9] built a representation-theoretic generalization of the result using symmetric function theory. In 2007, Wachs [10] demonstrated how shellability of simplicial complexes could be used to construct the formula (at least for n odd, given a correction of the indexing error on the formula for the arcsin power series coefficients). The result is on page 571 of the citation given and on page 75 of her website version of the same document.

In this paper, we provide an original and elementary combinatorial proof using only generating functions, induction, the Wilf-Zeilberger Algorithm, and techniques from undergraduate calculus and differential equations.

The absolute value of this sequence appears in The On-Line Encyclopedia of Integer Sequences as sequence \underline{A000246} [7] in a variety of combinatorial settings.

2 Definitions and background material

The following definitions generalize the classical number-theoretic Möbius function to any poset.

Definition 2. Let P be a poset. Let the Möbius function of P be

μ_{P} : {(x, y) ∈ P × P : x ≤ y} → ℤ

defined recursively as follows:

∑_{z∈[x,y]}μ_{P} (x, z) = \begin{cases}1, & if x = y; \\ 0, & otherwise. \end{cases}

Definition 3. Let P be a poset with a minimum element 0_{P} and a maximum element 1_{P}. Then the Möbius number of P is μ(P) = μ_{P} (0_{P} , 1_{P}).

For convenience, we assume from here on that every poset has a minimum element and a maximum element. Also we frequently identify the Möbius number of an element p ∈ P with the Möbius number of the subposet of P consisting of all elements less than or equal to p.

The following well-known result will be used heavily in Section 3.1, so we state it explicitly. See Stanley’s text [8] for a proof.

Lemma 4. [8, Proposition 3.8.2] Given posets P and Q with (x, y) ≤_{P ×Q} (x′, y′) , we have that

μ_{P ×Q} ((x, y) , (x′, y′)) = μ_{P} (x, x′) μ_{Q} (y, y′)

and in particular

μ(P × Q) = μ(P) · μ(Q).

3 Proofs

Remark 5. For positive natural numbers n, the poset Π_{n}^{odd} is not a lattice if and only if n ≥ 6.

Proof. For n ≤ 5, there are no chains of length greater than 3, since

1 = 1
2 = 1 + 1
3 = 1 + 1 + 1
4 = 3 + 1 = 1 + 1 + 1 + 1
5 = 3 + 1 + 1 = 1 + 1 + 1 + 1 + 1

show all partition types for such n. In these cases, maximal chains consist of only the minimum, the maximum, and if n = 4 or 5, one element inbetween. Thus, the join of every pair of distinct nonminimal elements is the maximum element, and the meet of every pair of distinct nonmaximal elements is the minimum element.

If n = 6, the partitions

{{1}, {2}, {3}, {4, 5, 6}}

and

{{1}, {2}, {4}, {3, 5, 6}}

have two least upper bounds, namely

{{1}, {2, 3, 4, 5, 6}}

and

{{2}, {1, 3, 4, 5, 6}},

so Π_{6}^{odd} is not a lattice. For any n > 6, we can construct a similar pair of elements in Π_{n}^{odd} that lacks a unique least upper bound by adding singletons to each of the above partitions.

Because of this, the frequently used and very powerful lattice-theoretic tools such as Crapo’s Compliment Theorem [2] are only applicable for finitely many of our posets of interest. We proceed instead with bare-knuckled enumerative combinatorics. The proof follows in four steps:

1. In Section 3.1, we write down a true but unwieldy recurrence relation for the Möbius numbers of the odd-partition posets based on Definition 2. This will be easy to verify but essentially impossible to work with since it will involve sums indexed over integer partitions with odd part size.

2. In Section 3.2, we emulate the product formula for the partition generating function to build two generating functions. We will show these two generating functions are equal if and only if Theorem 1 is true. The generating functions graciously handle the messiness of the sums from Section 3.1 for us.

3. In Section 3.3, we write down an initial value problem and show that it has a unique solution.

4. In Section 3.4, we show the two generating functions are in fact equal by verifying that they both solve the initial value problem. The crucial step in this verification is done via induction using the brilliant and powerful Zeilberger-Wilf Algorithm [3].

For notational convenience, let

a_{n} = \begin{cases}(−1)^{(n−1)/2} ((n − 2)!!)^{2} , & if n is odd; \\ (−1)^{n/2}(n − 1) ((n − 3)!!)^{2} , & if n is even. \end{cases}

That is, a_{n} is the name we are giving to the numbers themselves. We will proceed to show that these numbers are in fact the Möbius numbers of the posets.

3.1 Recurrence for the Möbius numbers

Let λ ⊢ n. That is, λ is a partition of the integer n. If B a partition of the set {1, 2, ⋯, n} such that the multiset of sizes of parts of B is λ, we say B has type λ. For our purposes, we require λ uses only parts that have odd size or size n. Define k = (n − 2)/2 if n is even and k = (n−3)/2 if n is odd, so that 2k +1 is always the largest odd natural number strictly less than n. Let m_{i} = m_{i}(λ) be the multiplicity of parts of size i in λ. This allows us to express λ in frequency notation as λ = (1^{m_{1}}3^{m_{3}}5^{m_{5}} ⋯ (2k + 1)^{m_{2k+1}}n^{m_{n}}). That is, λ is a partition of n with m_{1} parts of size 1, m_{3} parts of size 3, and so on. Notice that in the odd partition poset, the set partitions must be of this type. Additionally m_{n} can only be 0 or 1, and if it is 1 then all other m_{i} are 0.

We now use the orbit-stabilizer theorem to count the number of set partitions of an n-element set with a fixed type λ = (1^{m_{1}}3^{m_{3}}5^{m_{5}} ⋯ (2k + 1)^{m_{2k+1}}n^{m_{n}}). We have the n! elements of S_{n} acting pointwise on the elements of the set {1, 2, …, n}. Notice that any two set partitions with type λ are in the same orbit under S_{n}, so counting these amounts to just determining the size of the orbit. The stabilizer of a set partition with type λ will be a direct product of imprimitive wreath products of symmetric groups: while preserving the partition we can permute within any one of the parts or we can permute parts of the same size. Thus, the stabilizer is

⨂_{i∈{1,3,5,...,2k+1}} S_{i} ≀ S_{m_{i}}

which has order

∏_{i∈{1,3,5,...,2k+1}} m_{i}! · i!^{m_{i}}.

By the orbit-stabilizer theorem, we see that Π_{n}^{odd} has

\frac{n!}{∏_{i∈\{1,3,5,...,2k+1\}} m_{i}! · i!^{m_{i}}}

set partitions of type λ.

For fear of something relatively simple becoming obfuscated by excessive notation, we give an example. The set {1, 2, 3, 4, 5, 6, 7, 8} has many partitions of the type (1^{2}3^{2}) in Π_{8}^{odd}. That is, we have set partitions with two parts of size 1 and two parts of size 3. We wish to count how many such partitions it has. Letting S_{8} act on the points 1 through 8, we have 8! total group elements acting. We now count how many fix such a partition. We have one copy of S_{3} acting on each part of size 3. We have an S_{2} that swaps the parts of size 3, and another S_{2} that swaps the parts of size 1. All in all, this gives \frac{8!}{3!^{2}·2·2} partitions with type (1^{2}3^{2}).

Next observe that any two partitions of the same type will have the same Möbius number. If we are given two partitions of the same type, the posets lying underneath them will be isomorphic, as the S_{n} action described above is order preserving.

Suppose a set partition P has type λ = {n_{1}, n_{2}, ⋯, n_{m}} (written as a multiset). Then the subposet consisting of all elements of Π_{n}^{odd} less than or equal to P is isomorphic to the product poset of Π_{n_{1}}^{odd}, Π_{n_{2}}^{odd}, …, Π_{n_{m}}^{odd}. Therefore, by Lemma 4 we have

μ(P) = ∏_{i∈{1,2,...,m}} μ(Π_{n_{i}}^{odd}).

At this point, writing down the recurrence relation for the Möbius numbers amounts to just putting all the above pieces together. Definition 2 implies that the Möbius number of Π_{n}^{odd} is the negation of the sum of the Möbius numbers of all smaller partitions in Π_{n}^{odd}. We can group these smaller elements according to partition type. By the above arguments, for each type, we know how many elements there are with that type and what the Möbius number is as a product of smaller Möbius numbers. Summing over all valid partitions gives us our recurrence, stated below.

Lemma 6. Let P be the set of all types of partitions that occur in Π_{n}^{odd} except for the trivial partition consisting of just 1 part of size n. Abbreviate μ_{i} = μ(Π_{i}^{odd}). Then

μ_{n} = − ∑_{λ∈P} ∏_{i∈\{1,3,5,...,2k+1\}} \frac{n!μ_{i}^{m_{i}}}{m_{i}! · i!^{m_{i}}}

where λ = (1^{m_{1}}3^{m_{3}}5^{m_{5}} ⋯ (2k + 1)^{m_{2k+1}}).

3.2 Building the generating functions

Recall our notational shortcut, μ_{i} = μ(Π_{i}^{odd}). Also, recall the following infinite product formula for the generating function for partitions of sets:

∏_{n∈ℕ} \frac{1}{1 − t^{n}} = ∏_{n∈ℕ} ∑_{i=0}^{∞} t^{n·i}.

We observe that by slightly modifying the right-hand side of that infinite product, we can get expressions very similar to what we have in Lemma 6. First, we throw out any even n, since these are not part sizes that will come up in the odd partition poset except for maximal elements, which we will handle separately. Secondly, the term t^{n·i} should be multiplied by \frac{μ_{n}^{i}}{i!n!^{i}} to give the Möbius numbers and the orbit-stabilizer counts that occur in Lemma 6. Thus, by applying that recurrence in each degree, we have that

∏_{n odd} ∑_{i=0}^{∞} \frac{μ_{n}^{i}}{i!n!^{i}} t^{n·i} = 1 + t − \frac{μ_{2}}{2!} t^{2} − \frac{μ_{4}}{4!} t^{4} − \frac{μ_{6}}{6!} t^{6} − \frac{μ_{8}}{8!} t^{8} − · · · .

On the other hand, we can use the power series expansion for the exponential function to do a different manipulation to the same series. This produces the following equality:

∏_{n odd} ∑_{i=0}^{∞} \frac{μ_{n}^{i}}{i!n!^{i}} t^{n·i} = ∏_{n odd} e^{\frac{μn}{n!} t^{n}} = e^{μ_{1}t+ \frac{μ_{3}}{3!} t^{3}+ \frac{μ_{5}}{5!} t^{5}+ \frac{μ_{7}}{7!} t^{7}+···}.

These two expressions for the same power series provide us with our fundamental strategy for proving that the Möbius numbers μ_{i} really are the numbers a_{i} as we claim. We simply write down the same two expressions with a_{i} instead of μ_{i}. They are equal if and only if for all i, we have a_{i} = μ_{i}. In the next lemma, we state this approach more formally.

Lemma 7. Let

L(t) = e^{a_{1}t+ \frac{a_{3}}{3!} t^{3}+ \frac{a_{5}}{5!} t^{5}+ \frac{a_{7}}{7!} t^{7}+···}

and let

R(t) = 1 + t − \frac{a_{2}}{2!} t^{2} − \frac{a_{4}}{4!} t^{4} − \frac{a_{6}}{6!} t^{6} − \frac{a_{8}}{8!} t^{8} − · · · .

Then L(t) = R(t) is equivalent to Theorem 1.

3.3 The initial value problem

We now define an initial value problem, intentionally writing down the initial value problem solved by L(t) as defined in Lemma 7 simply using the chain rule and the derivative of the exponential.

\frac{dy}{dt} = y · (a_{1} + \frac{a_{3}}{2!} t^{2} + \frac{a_{5}}{4!} t^{4} + \frac{a_{7}}{6!} t^{6} + ⋯)  (∗)
y(0) = 1

We would like to claim that the initial value problem (∗) has a unique solution. To do this we show the following:

Lemma 8. The series a_{1} + \frac{a_{3}}{2!} t^{2} + \frac{a_{5}}{4!} t^{4} + \frac{a_{7}}{6!} t^{6} + ⋯ converges absolutely for −1 < t < 1.

Proof. Applying the standard ratio test for convergence of power series from an undergraduate calculus course yields the desired result. See for example page 66 of Rudin [5].

Clearly all involved functions are differentiable and have continuous partial derivatives. Thus, the standard theorem on uniqueness of solutions to an initial value problem from an undergraduate differential equations course (for example see Polking [4]) applies.

Lemma 9. The initial value problem (∗) has a unique solution.

3.4 Verifying the generating functions both solve the initial value problem

The fact that L(t) satisfies the initial value problem is clear. To show that R(t) also satisfies the initial value problem, we trivially check that the initial condition holds. We then plug R(t) into both sides of the differential equation. Basic algebra shows that all terms of odd degree match. The terms of even degree are not so obvious. To show that the coefficients match on the terms of even degree is equivalent to verifying the following identity for all even n:

O_{n} = ∑_{k∈\{2,4,...,n\}} O_{n−k}O_{k−1}\binom{n}{k}

where O_{n} is defined to be |a_{n}|. To solve this sum, we use the Wilf-Zeilberger Algorithm [3] devised for verifying such hypergeometric identities. To do this, we reformulate our sum by defining P_{n} = O_{2n} and using the fact that O_{2k−1} = \frac{O_{2k}}{2k−1}. Thus our sum becomes

1 = ∑_{k} \frac{P_{n−k}P_{k}\binom{2n}{2k}}{(2k − 1)P_{n}}

so that we are summing over all k and proving the identity for all n rather than just for even n. We then plug in the right-hand side into Gosper’s Algorithm [3] (as implemented in Maple) to get the proof certificate. The proof certificate (R(n, k) in their notation) is the function

\frac{(−2n − 1 + 2k)(k − 1)k}{(2n + 1)(k − n − 1)n} .

Following the proof on page 25 of A=B [3] verifies the identity. Thus, the proof of Theorem 1 is complete.

4 Acknowledgements

Many thanks to Alexander Hulpke, Tim Penttila, Bill Cherowitzo, and my family for their many helpful discussions throughout the course of this research. Thanks also to the referee for a very thoughtful and helpful review.

References

[1] A. R. Calderbank, P. Hanlon, and R. W. Robinson, Partitions into even and odd block size and some unusual characters of the symmetric groups, Proc. London Math. Soc. 53 (1986), 288–320.

[2] H. Crapo, The Möbius function of a lattice, J. Comb. Theory 1 (1966), 126–131.

[3] M. Petkovšek, H. S. Wilf, D. Zeilberger, A = B, A. K. Peters Ltd., 1996.

[4] J. Polking, A. Boggess, and D. Arnold, Differential Equations, 2nd edition, Prentice Hall, 2005.

[5] W. Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-Hill Book Co., International Series in Pure and Applied Mathematics, 1976.

[6] J. Shareshian, On the Möbius number of the subgroup lattice of the symmetric group, J. Comb. Theory, Ser. A 78 (1997), 236–267.

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

   at https://oeis.org.

[8] R. Stanley, Enumerative Combinatorics, Cambridge University Press, 1997.

[9] S. Sundaram, The homology representations of the symmetric group on Cohen-Macaulay subposets of the partition lattice, Adv. Math. 104 (1994), 225–296.

[10] M. Wachs, Poset topology: tools and applications, in Geometric Combinatorics, IAS/Park City Mathematics Series, Vol. 13, American Mathematical Society, 2007, pp. 497–615.

2010 Mathematics Subject Classification: Primary 06A07; Secondary 05E45. Keywords: Möbius number, partition, poset.

(Concerned with sequence \underline{A000246}.)

Received April 18 2018; revised version received October 16 2018. Published in Journal of Integer Sequences, December 13 2018.

Return to Journal of Integer Sequences home page.