# On the descent set of a permutation

$\pi\in S_n$, $\mathrm{desc}(\pi):=\{i\in[n-1]: \pi_{i+1}<\pi_i\}$. $S\subset[n-1]$ and $S$ of size $k$. Could you help me to calculate the following numbers, please?

1) The number of permutations $\pi\in S_n$ with $\mathrm{desc}(\pi)\supseteq S$.

2) The number of permutations $\pi\in S_n$ with $\mathrm{desc}(\pi)=S$.

-
By "understand the following numbers", do you mean understand their definitions, or understand how to calculate them? – joriki Nov 11 '11 at 7:41
calculate, I edited the question – Alex M Nov 11 '11 at 7:49
This is relevant and answers part 2: math.stackexchange.com/questions/77391/… – joriki Nov 11 '11 at 7:54

Question $(2)$ is answered in R.P. Stanley, Enumerative Combinatorics, v.$1$, in example $2.2.4$ on page $69$. If $S = \{ s_1, s_2, \dots, s_k\}$ (with $0 = s_0 < s_1 < \dots < s_k < s_{k+1}=n$) he defines $\beta_n(S)$ to be the number of permutations $\pi \in S_n$ with desc$(\pi) = S$ and proves that it is equal to the determinant of the $(k+1) \times (k+1)$ matrix whose $(i,j)^{\text{th}}$ entry is $\binom{n-s_i}{s_{j+1}-s_i}$ for $i,j\in[0,k]$.

Edit: It's not a very fulfilling answer but the number of permutations $\pi$ with desc$(\pi) \supseteq S$ is simply equal to $\sum_{T \supseteq S} \beta_n(T)$. I bet there's a cleaner formula, though...

-
Note that Stanley also gives the form given in the question linked to in my comment above, $n!\det[1/(s_{j+1}-s_i)!]$. The two are equivalent since the factors added to the columns cancel the factors added to the rows, except for the factors of $n!$ added to the first row. – joriki Nov 11 '11 at 17:18
@joriki: Sorry, I didn't notice your comment before I posted mine. – Dimitrije Kostic Nov 11 '11 at 23:47

I don’t know how useful it is, but here’s a slightly less ugly answer to the first question.

Let $S=\{a_1,\dots,a_k\}$ with $a_1<\dots<a_k$. A set $B=\{a_i,a_{i+1},\dots,a_{i+m}\}$ of consecutive members of $S$ is a block of $S$ iff $a_{i+j}=a_i+j$ for $0\le j\le m$ and $a_i-1,a_{i+m}+1\notin S$. Let $M$ be the multiset whose members are the sizes of the blocks of $S$. Then $$|\{\pi\in_n:\operatorname{desc}(\pi)\supseteq S\}|= \frac{n!}{\prod\limits_{m\in M}(m+1)!}.\tag{1}$$

To see this, let $B=\{a_i,a_{i+1},\dots,a_{i+m}\}$ be a block of $S$ of size $m+1$. The $m+2=|B|+1$ numbers $a_i,\dots,a_{i+m+1}$ must appear in descending order in $\pi$, a condition that is satisfied by only $\frac1{(m+2)!}$ of the $n!$ permutations of $[n]$. The corresponding conditions for any other blocks of $S$ are independent, and $(1)$ follows immediately.

More laboriously, one can observe that if $B$ is a block of $S$ of size $m$, there are $\binom{n}{m+1}$ ways to choose the members of the block and the immediately following element of $\pi$ and no freedom in how they are ordered. The remaining $n-\sum\limits_{m\in M}(m+1)$ elements of $\pi$ can be ordered arbitrarily, so we end up with $$\left(n-\sum_{m\in M}(m+1)\right)!\prod_{m\in M}\binom{n}{m+1}=\frac{n!}{\prod\limits_{m\in M}(m+1)!}$$ permutations whose descents include $S$.

-