Enumerating Ideals in Posets I am trying to work through Exercise 44 (a) in Ch.3 of R. Stanley's Enumerative Combinatorics. The problem is as follows: 
Let $w=a_1a_2\cdots a_n\in \mathfrak{S}_n$. Let $P_w=\{(i,a_i)\colon i\in[n]\}$, regarded as a subposet of $\mathbb{P}\times\mathbb{P}$. In other words, define $(i,a_i)\leq(k,a_k)$ if $i\leq k$ and $a_i\leq a_k$. Let $j(P)$ denote the number of order ideals of the poset $P$. Show that $$\sum_{w\in \mathfrak{S}_n}j(P_w)=\sum_{i=0}^n\frac{n!}{i!}{n\choose i}.$$
So far, I have worked through examples, and I believe that the number $\frac{n!}{i!}{n\choose i}$ is equal to $\sum_{w\in S_n}m_i(P_w)$, where $m_i(P)$ denotes the number of ideals of the poset $P$ whose longest chain contains exactly $i$ elements. However, I can't seem to find out how to prove this. Any help would be greatly appreciated.  
 A: A downset (order ideal) is completely determined by its maximal elements, which form an antichain. For $w\in\mathfrak{S}_n$ and $k\le n$ let $d(w,k)$ be the number of downsets in $P(w)$ with $k$ maximal elements. Let $d_n(k)=\sum_{w\in\mathfrak{S}_n}d(w,k)$. I claim that
$$d_n(k)=\frac{n!}{k!}\binom{n}k\;.\tag{1}$$
Pick any set $M$ of $k$ elements of $[n]$. If they are the maximal elements of a downset of some $P(w)$ with $w\in\mathfrak{S}_n$, they must appear in descending order in $w$. Conversely, if they do appear in $w$ in descending order, they uniquely determine a downset in $P(w)$. (You have to check this, but it’s straighforward.) There are $(n-k)!$ possible permutations of the remaining elements of $[n]$, and by a standard stars and bars argument there are $$\binom{k+(n-k+1)-1}k=\binom{n}k=\binom{n}{n-k}$$ ways to insert the elements of $M$ into this string in descending order, so $M$ is the set of maximal elements of a downset in $$(n-k)!\binom{n}{n-k}=\frac{n!}{k!}$$ words in $\mathfrak{S}_n$. Thus, $M$ contributes $\frac{n!}{k!}$ to $d_n(k)$. Since there are $\binom{n}k$ subsets of $[n]$ of size $k$, we’ve established $(1)$, from which the desired result is immediate.
