[proofplan] We first identify the interval $[\sigma,\tau]$ as a product of smaller partition lattices, one factor for each block of $\tau$. Multiplicativity of the Möbius function on products then reduces the general interval formula to the top-bottom value in $\Pi_k$. The top-bottom value is proved by the Möbius recursion: after grouping lower partitions by their block sizes, the needed cancellation is exactly the coefficient identity coming from the exponential generating function $\exp(\log(1+x))=1+x$. [/proofplan] [step:Factor the interval into independent partition lattices over the blocks of $\tau$] Let $\sigma,\tau\in\Pi_n$ satisfy $\sigma\le\tau$. For each block $B\in\tau$, let \begin{align*} \mathcal S_B:=\{C\in\sigma:C\subset B\} \end{align*} be the set of blocks of $\sigma$ contained in $B$, and let $k_B:=|\mathcal S_B|$. Since $\sigma\le\tau$, the sets $\mathcal S_B$ partition the set of blocks of $\sigma$. Define a map $\Phi:[\sigma,\tau]\to \prod_{B\in\tau}\Pi(\mathcal S_B)$ as follows. If $\pi\in[\sigma,\tau]$, then $\Phi(\pi)_B$ is the partition of $\mathcal S_B$ whose blocks are the collections of $\sigma$-blocks lying inside a common block of $\pi$. This is well-defined because every block of $\pi$ is contained in a block of $\tau$. Define the inverse map $\Psi:\prod_{B\in\tau}\Pi(\mathcal S_B)\to [\sigma,\tau]$ by sending a tuple $(\alpha_B)_{B\in\tau}$ to the partition of $\{1,\dots,n\}$ whose blocks are the unions \begin{align*} \bigcup_{C\in A} C \end{align*} as $B$ ranges over $\tau$ and $A$ ranges over the blocks of $\alpha_B$. The partition $\Psi((\alpha_B)_{B\in\tau})$ is coarser than $\sigma$ and finer than $\tau$, so it belongs to $[\sigma,\tau]$. The constructions $\Phi$ and $\Psi$ are inverse to one another, and both preserve refinement order. Hence \begin{align*} [\sigma,\tau]\cong \prod_{B\in\tau}\Pi(\mathcal S_B)\cong \prod_{B\in\tau}\Pi_{k_B}. \end{align*} [guided] The point of this step is that refinements inside different blocks of $\tau$ cannot interact. If $\pi$ lies between $\sigma$ and $\tau$, then every block of $\pi$ is a union of blocks of $\sigma$, but it is still contained in a single block of $\tau$. Thus the only choices made by $\pi$ are, separately for each $B\in\tau$, how to group the $\sigma$-blocks that lie inside $B$. For a block $B\in\tau$, define \begin{align*} \mathcal S_B:=\{C\in\sigma:C\subset B\}. \end{align*} This is a finite set with $k_B=|\mathcal S_B|$ elements. Given $\pi\in[\sigma,\tau]$, define $\Phi(\pi)_B$ to be the partition of $\mathcal S_B$ in which two blocks $C,D\in\mathcal S_B$ lie in the same part exactly when they are contained in the same block of $\pi$. This produces an element of $\Pi(\mathcal S_B)$. Conversely, suppose that for every $B\in\tau$ we are given a partition $\alpha_B\in\Pi(\mathcal S_B)$. For each block $A$ of $\alpha_B$, form the union \begin{align*} \bigcup_{C\in A} C. \end{align*} The collection of all these unions, over all $B\in\tau$, is a partition of $\{1,\dots,n\}$. It is coarser than $\sigma$, because its blocks are unions of blocks of $\sigma$, and it is finer than $\tau$, because each such union is contained in the corresponding block $B$ of $\tau$. Therefore it lies in $[\sigma,\tau]$. These two constructions undo each other: starting with $\pi$, recording how it groups the $\sigma$-blocks inside each $B$, and then taking the corresponding unions recovers $\pi$; starting with the tuple $(\alpha_B)_{B\in\tau}$ and then recording the induced groupings recovers the same tuple. They also preserve order because making a partition coarser exactly corresponds to making the induced grouping of $\sigma$-blocks coarser in each factor. Hence \begin{align*} [\sigma,\tau]\cong \prod_{B\in\tau}\Pi(\mathcal S_B)\cong \prod_{B\in\tau}\Pi_{k_B}. \end{align*} [/guided] [/step] [step:Reduce the general interval formula to the top-bottom value in $\Pi_k$] Each factor $\Pi(\mathcal S_B)$ is finite, hence locally finite, and under the interval isomorphism the element $\sigma$ corresponds to the tuple of discrete partitions while $\tau$ corresponds to the tuple of one-block partitions. By [citetheorem:8096], the value $\mu_{\Pi_n}(\sigma,\tau)$ agrees with the Möbius value of this product interval between the corresponding bottom and top elements. By repeated application of [citetheorem:8097], the Möbius function of a finite product of locally finite posets is the product of the Möbius functions of the factors. Applying these theorems to the interval factorization above gives \begin{align*} \mu_{\Pi_n}(\sigma,\tau)=\prod_{B\in\tau}\mu_{\Pi(\mathcal S_B)}(\hat{0}_B,\hat{1}_B)=\prod_{B\in\tau}\mu_{\Pi_{k_B}}(\hat{0},\hat{1}), \end{align*} where $\hat{0}_B$ and $\hat{1}_B$ denote respectively the discrete partition and the one-block partition of $\mathcal S_B$, and $\hat{0}$ and $\hat{1}$ in $\Pi_{k_B}$ denote respectively the discrete partition and the one-block partition of a $k_B$-element set. Thus it remains to prove that \begin{align*} \mu_{\Pi_k}(\hat{0},\hat{1})=(-1)^{k-1}(k-1)! \end{align*} for every $k\in\mathbb N$. [/step] [step:Compute the top-bottom value by Möbius recursion and an exponential generating function] For $n=1$, the interval $[\hat{0},\hat{1}]$ has one element, so $\mu_{\Pi_1}(\hat{0},\hat{1})=1=(-1)^0 0!$. Assume now that $n\ge 2$, and assume inductively that $\mu_{\Pi_m}(\hat{0},\hat{1})=(-1)^{m-1}(m-1)!$ for every integer $m$ with $1\le m<n$. By [citetheorem:8093] applied in the finite poset $\Pi_n$, since $\hat{0}<\hat{1}$ we have \begin{align*} \mu_{\Pi_n}(\hat{0},\hat{1})=-\sum_{\hat{0}\le \pi<\hat{1}}\mu_{\Pi_n}(\hat{0},\pi). \end{align*} Let $\pi\in\Pi_n$ have blocks $A_1,\dots,A_r$, where $r=|\pi|$. Applying the interval product factorization with $\sigma=\hat{0}$ and $\tau=\pi$ gives \begin{align*} [\hat{0},\pi]\cong \prod_{j=1}^r \Pi_{|A_j|}. \end{align*} Since $\pi<\hat{1}$, each block size $|A_j|$ is strictly smaller than $n$ whenever $r=1$ is excluded, and the induction hypothesis applies to every factor. Hence [citetheorem:8097] gives \begin{align*} \mu_{\Pi_n}(\hat{0},\pi)=\prod_{j=1}^r (-1)^{|A_j|-1}(|A_j|-1)!. \end{align*} Define a sequence $w:\mathbb N\to\mathbb Z$ by $w_m:=(-1)^{m-1}(m-1)!$. The preceding formula says that every proper partition $\pi<\hat{1}$ contributes the product $\prod_{A\in\pi}w_{|A|}$. Therefore the recursion will give $\mu_{\Pi_n}(\hat{0},\hat{1})=w_n$ once we prove \begin{align*} \sum_{\pi\in\Pi_n}\prod_{A\in\pi}w_{|A|}=0. \end{align*} To prove this identity, define the formal [power series](/page/Power%20Series) $W\in\mathbb Q[[x]]$ by \begin{align*} W=\sum_{m=1}^{\infty}w_m\frac{x^m}{m!}=\sum_{m=1}^{\infty}(-1)^{m-1}\frac{x^m}{m}=\log(1+x). \end{align*} Expanding $\exp(W)$ in $\mathbb Q[[x]]$ gives the weighted set-partition identity \begin{align*} \sum_{n=0}^{\infty}\left(\sum_{\pi\in\Pi_n}\prod_{A\in\pi}w_{|A|}\right)\frac{x^n}{n!}=\exp(W). \end{align*} Indeed, the term $W^r/r!$ chooses $r$ labelled blocks with weights $w_m$, and the factor $r!$ removes the ordering of the blocks. Since $W=\log(1+x)$, this gives \begin{align*} \sum_{n=0}^{\infty}\left(\sum_{\pi\in\Pi_n}\prod_{A\in\pi}w_{|A|}\right)\frac{x^n}{n!}=\exp(\log(1+x))=1+x. \end{align*} Comparing the coefficient of $x^n/n!$ for $n\ge 2$ gives the desired cancellation. Thus \begin{align*} 0=\sum_{\pi\in\Pi_n}\prod_{A\in\pi}w_{|A|}=\sum_{\hat{0}\le \pi<\hat{1}}\mu_{\Pi_n}(\hat{0},\pi)+w_n, \end{align*} and the Möbius recursion yields \begin{align*} \mu_{\Pi_n}(\hat{0},\hat{1})=-\sum_{\hat{0}\le \pi<\hat{1}}\mu_{\Pi_n}(\hat{0},\pi)=w_n=(-1)^{n-1}(n-1)!. \end{align*} [guided] The unsupported part of the original argument was the count of falling chains, so we instead prove the same top-bottom value directly from the defining recursion for the Möbius function. For $n=1$, the interval has one element and therefore $\mu_{\Pi_1}(\hat{0},\hat{1})=1=(-1)^0 0!$. Now let $n\ge 2$ and assume the formula already holds for all smaller partition lattices $\Pi_m$ with $1\le m<n$. The recursive formula [citetheorem:8093] applies because $\Pi_n$ is finite, hence locally finite. Since $\hat{0}<\hat{1}$, it gives \begin{align*} \mu_{\Pi_n}(\hat{0},\hat{1})=-\sum_{\hat{0}\le \pi<\hat{1}}\mu_{\Pi_n}(\hat{0},\pi). \end{align*} Thus the task is to compute the sum of all lower interval Möbius values. Let $\pi\in\Pi_n$ have blocks $A_1,\dots,A_r$. The interval $[\hat{0},\pi]$ factors independently over these blocks: \begin{align*} [\hat{0},\pi]\cong \prod_{j=1}^r \Pi_{|A_j|}. \end{align*} The product formula [citetheorem:8097] applies because all these factors are finite posets. If $\pi<\hat{1}$, then no factor has size $n$ as the single top block of the whole set, so every block size appearing in this product is covered by the induction hypothesis. Therefore \begin{align*} \mu_{\Pi_n}(\hat{0},\pi)=\prod_{j=1}^r (-1)^{|A_j|-1}(|A_j|-1)!. \end{align*} It remains to show that the total weighted sum over all partitions cancels. Define $w_m:=(-1)^{m-1}(m-1)!$ for $m\in\mathbb N$. The weight of a partition $\pi$ is $\prod_{A\in\pi}w_{|A|}$. Define $W\in\mathbb Q[[x]]$ by \begin{align*} W=\sum_{m=1}^{\infty}w_m\frac{x^m}{m!}=\sum_{m=1}^{\infty}(-1)^{m-1}\frac{x^m}{m}=\log(1+x). \end{align*} We now justify the weighted set-partition generating function in this case. Expanding the exponential means \begin{align*} \exp(W)=\sum_{r=0}^{\infty}\frac{W^r}{r!}. \end{align*} Fix $n\ge 0$ and $r\ge 0$. For an ordered list of positive integers $m_1,\dots,m_r$ with $m_1+\cdots+m_r=n$, the contribution to the coefficient of $x^n/n!$ from $W^r/r!$ is \begin{align*} \frac{1}{r!}\binom{n}{m_1,\dots,m_r}\prod_{i=1}^r w_{m_i}. \end{align*} Here the multinomial coefficient chooses which labelled elements of $\{1,\dots,n\}$ lie in the first block, second block, and so on. The factor $1/r!$ removes the ordering of these blocks. Hence, after summing over $r$ and over all positive block sizes, each partition $\pi\in\Pi_n$ is counted exactly once with weight $\prod_{A\in\pi}w_{|A|}$. Therefore \begin{align*} \sum_{n=0}^{\infty}\left(\sum_{\pi\in\Pi_n}\prod_{A\in\pi}w_{|A|}\right)\frac{x^n}{n!}=\exp(W)=\exp(\log(1+x))=1+x. \end{align*} For every $n\ge 2$, the coefficient of $x^n/n!$ on the right-hand side is zero, so \begin{align*} \sum_{\pi\in\Pi_n}\prod_{A\in\pi}w_{|A|}=0. \end{align*} The unique contribution of the one-block partition $\hat{1}$ is $w_n=(-1)^{n-1}(n-1)!$, and every other contribution is $\mu_{\Pi_n}(\hat{0},\pi)$. Therefore \begin{align*} 0=\sum_{\hat{0}\le \pi<\hat{1}}\mu_{\Pi_n}(\hat{0},\pi)+w_n. \end{align*} Substituting this into the Möbius recursion gives \begin{align*} \mu_{\Pi_n}(\hat{0},\hat{1})=-\sum_{\hat{0}\le \pi<\hat{1}}\mu_{\Pi_n}(\hat{0},\pi)=w_n=(-1)^{n-1}(n-1)!. \end{align*} [/guided] [/step] [step:Substitute the top-bottom formula into each product factor] Returning to $\sigma\le\tau$, the reduction step gives \begin{align*} \mu_{\Pi_n}(\sigma,\tau)=\prod_{B\in\tau}\mu_{\Pi_{k_B}}(\hat{0},\hat{1}). \end{align*} Applying the top-bottom formula to each factor yields \begin{align*} \mu_{\Pi_n}(\sigma,\tau)=\prod_{B\in\tau}(-1)^{k_B-1}(k_B-1)!. \end{align*} If $k_B=1$, then the corresponding factor is \begin{align*} (-1)^0 0!=1, \end{align*} which is exactly the Möbius value of a one-point interval. This also covers the case $n=1$. Hence both stated formulas follow. [/step]