\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
An Elementary Proof of the Explicit Formula\\
for the M\"obius Number \\
\vskip .13in
of the Odd Partition Poset
}
\vskip 1cm
\large
Kenneth M. Monks \\
Department of Mathematics \\
Front Range Community College --- Boulder County Campus \\
2190 Miller Drive \\
Longmont, CO 80537 \\
USA \\
\href{mailto:kenneth.monks@frontrange.edu}{\tt kenneth.monks@frontrange.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
The M\"obius number of a finite poset is a very useful combinatorial invariant of the poset that generalizes the classical number-theoretic M\"obius function. The M\"obius number of the poset of partitions $\Pi_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,\ldots,n\}\}$, written $\Pi^{\rm odd}_n$, arises in similar combinatorial settings. In this paper, we compute the M\"obius numbers of all $\Pi^{\rm odd}_n$ as follows:
$$ \mu \left(\Pi_n^{\textrm{odd}}\right)=
\begin{cases}
(-1)^{(n-1)/2}\left((n-2)!!\right)^2, & \text{if $n$ is odd;}\\
(-1)^{n/2}(n-1)\left((n-3)!!\right)^2, & \text{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.
\end{abstract}
\section{Introduction and statement of main results}
One of the most natural and well-studied posets is the poset $\Pi_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,\ldots,n\}\}$. We call this the \emph{odd-partition poset} and denote it $\Pi_n^{\textrm{odd}}$. For example, Figure \ref{PiOdd4} illustrates $\Pi_4^{\textrm{odd}}$.
\begin{figure}[h]
\begin{center}
\includegraphics[scale=.4]{monks12fig.eps}
\end{center}
\caption{The Hasse Diagram for $\Pi_4^{\textrm{odd}}$}\label{PiOdd4}
\end{figure}
This poset arose in the author's PhD work when applying Shareshian's techniques \cite{shareshian}
to a problem of Stanley \cite{Stanley}. If $P$ is a finite poset with minimum and maximum elements, the M\"{o}bius number $\mu(P)$ is a much sought-after combinatorial invariant of $P$ (see Section \ref{back} for a formal definition). Computing the M\"{o}bius numbers for some small values of $n$ reveals the following pattern:
\vspace{.05in}
\begin{tabular}{l c l}
$\mu\left(\Pi_1^{\textrm{odd}}\right) $ &$ = $& $1$ \\
$\mu\left(\Pi_2^{\textrm{odd}}\right) $ & $=$ & $-1$ \\
$\mu\left(\Pi_3^{\textrm{odd}}\right) $ & $=$ & $-1\cdot 1 $\\
$\mu\left(\Pi_4^{\textrm{odd}}\right) $ & $=$ & $-1\cdot 1 \cdot -3 $ \\
$\mu\left(\Pi_5^{\textrm{odd}}\right) $ & $=$ & $ -1\cdot 1 \cdot -3 \cdot 3 $ \\
$\mu\left(\Pi_6^{\textrm{odd}}\right)$ & $=$& $-1\cdot 1 \cdot -3 \cdot 3 \cdot -5 $ \\
$\mu\left(\Pi_7^{\textrm{odd}}\right)$ & $=$ & $ -1\cdot 1 \cdot -3 \cdot 3 \cdot -5 \cdot 5 $ \\
$\mu\left(\Pi_8^{\textrm{odd}}\right)$ & $=$ & $ -1\cdot 1 \cdot -3 \cdot 3 \cdot -5 \cdot 5 \cdot -7 $ \\
$\mu\left(\Pi_9^{\textrm{odd}}\right)$ & $=$ & $-1\cdot 1 \cdot -3 \cdot 3 \cdot -5 \cdot 5 \cdot -7 \cdot 7 $ \\
$\mu\left(\Pi_{10}^{\textrm{odd}}\right)$ & $=$ & $ -1\cdot 1 \cdot -3 \cdot 3 \cdot -5 \cdot 5 \cdot -7 \cdot 7 \cdot -9 $ \\
& \vdots &
\end{tabular}
\vspace{.05in}
This pattern continues forever, which we state more formally below.
\begin{theorem}[Stanley]\label{main}
Let $\Pi_n^{\textrm{odd}}$ be the odd-partition poset of an $n$-element set. Then the M\"{o}bius number $\mu(\Pi_n^{\textrm{odd}})$ is given by
$$ \mu (\Pi_n^{\textrm{odd}})=
\begin{cases}
(-1)^{(n-1)/2}\left((n-2)!!\right)^2, & \text{if $n$ is odd;}\\
(-1)^{n/2}(n-1)\left((n-3)!!\right)^2, & \text{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$.
\end{theorem}
This formula was stated as known by Stanley on page 291 of a paper of Calderbank, Hanlon, and Robinson \cite{Calderbank} in 1986. However, no reference or proof is given. In 1994, Sundaram \cite{Sundaram} built a representation-theoretic generalization of the result using symmetric function theory. In 2007, Wachs \cite{Wachs} 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 \seqnum{A000246}
\cite{Sloane} in a variety of combinatorial settings.
\section{Definitions and background material}\label{back}
The following definitions generalize the classical number-theoretic M\"obius function to any poset.
\begin{definition}
\label{def1} Let $P$ be a poset. Let the \textbf{ M\"{o}bius function} of $P$ be $$\mu_P:\lbrace(x,y)\in P\times P: x\leq y \rbrace \rightarrow \mathbb{Z}$$
defined recursively as follows:
\begin{equation*}
\underset{z\in \lbrack x,y]}{\overset{}{\sum }}\mu_P \left( x,z\right) =
\begin{cases}
$1$, & \text{if $x=y$;} \\
$0$, & $\text{otherwise.}$
\end{cases}
\end{equation*}
\end{definition}
\begin{definition}
Let $P$ be a poset with a minimum element $0_P$ and a maximum element $1_P$. Then the \textbf{M\"{o}bius number} of $P$ is $\mu(P)=\mu_P(0_P,1_P)$.
\end{definition}
For convenience, we assume from here on that every poset has a minimum element and a maximum element. Also we frequently identify the M\"obius number of an element $p\in P$ with the M\"obius 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 \ref{ProofRec}, so we state it explicitly. See Stanley's text \cite{Stanley} for a proof.
\begin{lemma}
\label{Product Poset}\cite[Proposition 3.8.2]{Stanley} Given posets $P$ and $Q$ with $\left(
x,y\right) \leq _{P\times Q}\left( x^{\prime },y^{\prime }\right) ,$ we have
that%
\begin{equation*}
\mu _{P\times Q}\left( \left( x,y\right), \left( x^{\prime },y^{\prime
}\right) \right) =\mu _{P}\left( x,x^{\prime }\right) \mu _{Q}\left(
y,y^{\prime }\right)
\end{equation*}
and in particular $$ \mu(P \times Q)=\mu(P) \cdot \mu(Q).$$
\end{lemma}
\section{Proofs}
\begin{remark} For positive natural numbers $n$, the poset $\Pi_n^{\textrm{odd}}$ is not a lattice if and only if $n \geq 6$.
\end{remark}
\begin{proof}
For $n\leq 5$, there are no chains of length greater than $3$, since
\begin{align*}
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
\end{align*}
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 $$\lbrace \{1\},\{2\},\{3\},\{4,5,6\} \rbrace $$ and $$\lbrace \{1\},\{2\},\{4\},\{3,5,6\} \rbrace $$ have two least upper bounds, namely $$\lbrace \{1\},\{2,3,4,5,6\} \rbrace $$ and$$\lbrace \{2\},\{1,3,4,5,6\} \rbrace ,$$ so $\Pi_6^{\textrm{odd}}$ is not a lattice. For any $n>6$, we can construct a similar pair of elements in $\Pi_n^{\textrm{odd}}$ that lacks a unique least upper bound by adding singletons to each of the above partitions.
\end{proof}
Because of this, the frequently used and very powerful lattice-theoretic tools such as Crapo's Compliment Theorem \cite{Crapo} 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:
\begin{enumerate}
\item In Section \ref{ProofRec}, we write down a true but unwieldy recurrence relation for the M\"obius numbers of the odd-partition posets based on Definition \ref{def1}. 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.
\item In Section \ref{ProofGens}, 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 \ref{main} is true. The generating functions graciously handle the messiness of the sums from Section \ref{ProofRec} for us.
\item In Section \ref{EyeVP}, we write down an initial value problem and show that it has a unique solution.
\item In Section \ref{verify}, 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 \cite{A=B}.
\end{enumerate}
For notational convenience, let $$a_n=\begin{cases}
(-1)^{(n-1)/2}\left((n-2)!!\right)^2, & \text{if $n$ is odd;}\\
(-1)^{n/2}(n-1)\left((n-3)!!\right)^2, & \text{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\"{o}bius numbers of the posets.
\subsection{Recurrence for the M\"obius numbers}\label{ProofRec}
Let $\lambda\vdash n$. That is, $\lambda$ is a partition of the integer $n$. If $\mathcal{B}$ a partition of the set $\{1,2,\cdots ,n\}$ such that the multiset of sizes of parts of $\mathcal{B}$ is $\lambda$, we say $\mathcal{B}$ has \emph{type} $\lambda$. For our purposes, we require $\lambda$ 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(\lambda)$ be the multiplicity of parts of size $i$ in $\lambda$. This allows us to express $\lambda$ in frequency notation as $\lambda = \left(1^{m_1} 3^{m_3} 5^{m_5} \cdots (2k+1)^{m_{2k+1}} n^{m_{n}}\right)$. That is, $\lambda$ 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 $\lambda = \left(1^{m_1} 3^{m_3} 5^{m_5} \cdots (2k+1)^{m_{2k+1}} n^{m_{n}}\right)$. We have the $n!$ elements of $S_n$ acting pointwise on the elements of the set $\{1,2,\ldots,n\}$. Notice that any two set partitions with type $\lambda$ 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 $\lambda$ 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 $$ \bigotimes_{i \in \{1,3,5,\ldots ,2k+1 \}} S_{i} \wr S_{m_i}$$ which has order $$\prod_{i \in \{1,3,5,\ldots ,2k+1 \}} m_i ! \cdot i!^{m_i}. $$ By the orbit-stabilizer theorem, we see that $\Pi_n^{\textrm{odd}}$ has $$\frac{n!}{\prod_{i \in \{1,3,5,\ldots ,2k+1 \}} m_i ! \cdot i!^{m_i} }$$ set partitions of type $\lambda$.
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 $\left(1^2 3^2\right)$ in $\Pi_8^{\textrm{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\cdot 2\cdot 2}$ partitions with type $\left(1^2 3^2\right)$.
Next observe that any two partitions of the same type will have the same M\"obius 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 $\lambda = \{n_1, n_2, \cdots, n_m\}$
(written as a multiset). Then the subposet consisting of all elements
of $\Pi_n^{\textrm{odd}}$ less than or equal to $P$ is isomorphic to the
product poset of $\Pi_{n_1}^{\textrm{odd}}$, $\Pi_{n_2}^{\textrm{odd}}$,
\ldots, $\Pi_{n_m}^{\textrm{odd}}$. Therefore, by Lemma \ref{Product
Poset} we have $$\mu (P)=\prod_{i \in \{1,2,\ldots, m \}} \mu
(\Pi_{n_i}^{\textrm{odd}}).$$
At this point, writing down the recurrence relation for the M\"obius numbers amounts to just putting all the above pieces together. Definition \ref{def1} implies that the M\"obius number of $\Pi_n^{\textrm{odd}}$ is the negation of the sum of the M\"obius numbers of all smaller partitions in $\Pi_n^{\textrm{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\"obius number is as a product of smaller M\"obius numbers. Summing over all valid partitions gives us our recurrence, stated below.
\begin{lemma}\label{recurrence}
Let $\mathcal{P}$ be the set of all types of partitions that occur in $\Pi_n^{\textrm{odd}}$ except for the trivial partition consisting of just 1 part of size $n$. Abbreviate $\mu_i=\mu (\Pi_i^{\textrm{odd}})$. Then $$ \mu_n =-\sum_{\lambda \in \mathcal{P}} \hspace{.1in} \prod_{i \in \{1,3,5,\ldots ,2k+1 \}}\frac{n!\mu_i^{m_i}}{ m_i ! \cdot i!^{m_i} }$$ where $\lambda = (1^{m_1} 3^{m_3} 5^{m_5} \cdots (2k+1)^{m_{2k+1}} )$.
\end{lemma}
\subsection{Building the generating functions}\label{ProofGens}
Recall our notational shortcut, $\mu_i=\mu (\Pi_i^{\textrm{odd}})$. Also, recall the following infinite product formula for the generating function for partitions of sets:
$$ \prod_{n \in \mathbb{N}} \frac{1}{1-t^n}=\prod_{n \in \mathbb{N}} \sum_{i = 0}^{\infty} t^{n\cdot 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 \ref{recurrence}. 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\cdot i}$ should be multiplied by $\frac{\mu_n^i}{i!n!^i}$ to give the M\"obius numbers and the orbit-stabilizer counts that occur in Lemma \ref{recurrence}. Thus, by applying that recurrence in each degree, we have that $$ \prod_{n \textrm{ odd}} \sum_{i = 0}^{\infty} \frac{\mu_n^i}{i!n!^i}t^{n\cdot i}= 1 + t - \frac{\mu_2}{2!}t^2- \frac{\mu_4}{4!}t^4- \frac{\mu_6}{6!}t^6- \frac{\mu_8}{8!}t^8-\cdots.$$
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:
$$ \prod_{n \textrm{ odd}} \sum_{i = 0}^{\infty} \frac{\mu_n^i}{i!n!^i}t^{n\cdot i}= \prod_{n \textrm{ odd}} e^{\frac{\mu_n}{n!}t^n}
\\
= e^{\mu_1t+\frac{\mu_3}{3!}t^3+\frac{\mu_5}{5!}t^5+\frac{\mu_7}{7!}t^7+\cdots}. $$
These two expressions for the same power series provide us with our fundamental strategy for proving that the M\"obius numbers $\mu_i$ really are the numbers $a_i$ as we claim. We simply write down the same two expressions with $a_i$ instead of $\mu_i$. They are equal if and only if for all $i$, we have $a_i=\mu_i$. In the next lemma, we state this approach more formally.
\begin{lemma}\label{genfun}
Let $$L(t)=e^{a_1t+\frac{a_3}{3!}t^3+\frac{a_5}{5!}t^5+\frac{a_7}{7!}t^7+\cdots}$$
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-\cdots . $$ Then $L(t)=R(t)$ is equivalent to Theorem \ref{main}.
\end{lemma}
\subsection{The initial value problem}\label{EyeVP}
We now define an initial value problem, intentionally writing down the initial value problem solved by $L(t)$ as defined in Lemma \ref{genfun} simply using the chain rule and the derivative of the exponential.
\begin{align*}\label{IVP} \frac{dy}{dt}&=y\cdot \left(a_1+\frac{a_3}{2!}t^2+\frac{a_5}{4!}t^4+\frac{a_7}{6!}t^6+\cdots\right) \tag{$\ast$}
\\
y(0) &= 1
\end{align*}
We would like to claim that the initial value problem (\ref{IVP}) has a unique solution. To do this we show the following:
\begin{lemma}
The series $a_1+\frac{a_3}{2!}t^2+\frac{a_5}{4!}t^4+\frac{a_7}{6!}t^6+\cdots$ converges absolutely for $-1