2
$\begingroup$

$\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$.

  • 0
    A minor note: A more widespread notation is $\mathrm{Des}(\pi)$ for the descent set of $\pi$ and $\mathrm{des}(\pi)=|\mathrm{Des}(\pi)|$ for the number of descents of $\pi$.2017-11-14

2 Answers 2

2

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...

  • 0
    @joriki: Sorry, I didn't notice your comment before I posted mine.2011-11-11
2

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 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$.