Möbius function of subpermutation ordering of $[n]$, is equal to number of derangements of $[n]$.

85 Views Asked by At

Let $P_n$ be the poset of subpermutations of $[n]$, ordered by the relation $$x\preceq y \iff x \text{ is a subsequence of } y$$ (e.g. for $P_7$, we have that $(3,7,6)\preceq (2,3,7,1,6)$ ).

Let us assume now the poset $\hat{P_n}=P_n\cup \{ \hat{0},\hat{1}\} $, constructed by adding a minimum ellement $\hat{0}$ and a maximum ellement $\hat{1}$. We want to show that $$|\mu(\hat{0},\hat{1})|=D_n,$$ where $D_n$ is the number of derangements of $\left[n\right]$ (i.e. the number of permutations of $\left[n\right]$ without fixed points) and $\mu$ is the Möbius function of $\hat{P_n}$.


I have managed to show that $P_n$ is a finite graded poset of rank $n-1$. I also observed that, for any $k\in\{0,1,\cdots,n\}$ $$\#\left\{ x\in\hat{P_{n}}\mid\hat{p}\left(x\right)=k\right\} =\binom{n}{k}k!$$and thus $$D_n=\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}\left(n-k\right)!=\sum_{k=0}^{n}\left(-1\right)^{n-k}\#\left\{ x\in\hat{P_{n}}\mid\hat{p}\left(x\right)=k\right\}$$ where $\hat{p}$ is the rank function of $\hat{P_n}$. But I do not know how to procced.

Moreover, by Philip Hall’s theorem (Proposition 3.8.5, Stanley's "Enumerative Combinatorics Vol 1"(2011).) I know that $$\left|\mu\left(\hat{0},\hat{1}\right)\right|=\left|\sum_{i=1}^{n+1}\left(-1\right)^{i}c_{i}\right|,$$ where $c_i$ be the number of chains $\hat{0}<t_0<t_1<\cdots<t_i=\hat{1}$ of length $i$ between $\hat{0}$ and $\hat{1}$.

I have shown that $$c_{i}=\sum_{1\le k_{1}<\ldots<k_{i-1}\le n}\binom{k_{2}}{k_{1}}\cdots\binom{k_{i-1}}{k_{i-2}}\cdot k_{i-1}!$$ and it seems that the requested equality holds, but I cannot show it.

Can anyone help me?

1

There are 1 best solutions below

0
On BEST ANSWER

First show by induction on $k$ that $\mu(\hat 0,x)=(-1)^{\hat p(x)}$ for each $x\in\hat P_n$: if $\hat p(x)=k>0$, and $0\le\ell<k$, then $x$ has $\binom{k}\ell$ predecessors of rank $\ell$ in $\hat P_n$, so

$$\begin{align*} \mu(\hat 0,x)&=-\sum_{\hat 0\preceq y\prec x}\mu(\hat 0,y)\\ &=-\sum_{\ell=0}^{k-1}(-1)^\ell\binom{k}\ell\\ &=-\left(\sum_{\ell=0}^k(-1)^\ell\binom{k}\ell-(-1)^k\binom{k}k\right)\\ &=(-1)^k\,. \end{align*}$$

Thus,

$$\begin{align*} \left|\mu(\hat 0,\hat 1)\right|&=\left|-\sum_{\hat 0\preceq x\prec\hat1}\mu(\hat 0,x)\right|\\ &=\left|\sum_{k=0}^n(-1)^k\binom{n}kk!\right|\\ &=\left|\sum_{k=0}^n(-1)^{n-k}\binom{n}{n-k}(n-k)!\right|\\ &=\left|\sum_{k=0}^n(-1)^{n-k}\binom{n}k(n-k)!\right|\\ &=\left|\sum_{k=0}^n(-1)^k\binom{n}k(n-k)!\right|\\ &=|D_n|\\ &=D_n\,. \end{align*}$$