Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
This is relevant and answers part 2: math.stackexchange.com/questions/77391/… –  joriki Nov 11 '11 at 7:54

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

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.