say that we have two chains of length n, call them $C_1$ and $C_2$.Let us say that the smallest value in $C_1$ is $a_1$, and the smallest one in $C_2$ is b_1. Further, for each element in these chains, assign a new positive value to it if $i \equiv 0 \mod{2}$, and a negative value if $i \equiv 1 \mod{2}$. We require that we assign unique values, so it must be an injection. So, for example, say we had two chains of length 2, consisting of $a_1 < a_2$, $b_1 < b_2$ . Let us set $a_1 = -1$, $b_1 = -2$, $a_2 = 1$, $b_2=2$.

Given this, we know that there are $2n \choose n$ linear extension of two chains. We can to each linear extension associate a descent set. With our example from before, one linear extension would be: $-1 > -2 < 1 < 2$. This would have descent set $\{1\}$. To each linear extension adjoin a 0 to the start of the extension , and to the end of the extension. GIven this, we want to find how many linear extension there are with k descents, where the resulting linear extension has no double descents, that is, no $i$, so that $a_{i-1} > a_i > a_{i+1}$.

Through experimentation I've seem to come across the number ${n \choose 2k}{2k \choose k}$, but I'm not sure what this really counts, and I would really want a combinatorial way of explaining this. Any help would be welcome, I'm completly stuck. For some examples of how such an adjoined linear extension could look, let us use the example from before:

$0 > -1 > -2 < 1 < 2 > 0$. This would then have a double descent so it would NOT qualify.

  • $\begingroup$ What's $i$ in "$i\equiv0$ mod $2$"? How can you "set $a_1=-1$" if you already have $a_1<a_2$? Do you mean "map $a_1$ to $-1$"? What's a descent set? $\endgroup$
    – joriki
    Apr 9, 2011 at 7:21
  • $\begingroup$ What I meant was that we label the smallest element in the first chain with a negative value, then the next to smallest with a positive, then a negative etc. Descent set en.wikipedia.org/wiki/Permutation#Ascents.2C_descents_and_runs. Do you understand me better now? $\endgroup$
    – Dedalus
    Apr 9, 2011 at 8:32

1 Answer 1


Solved it, so no need for answers now. Thanks anyways!

  • $\begingroup$ Would you mind sharing your solution? $\endgroup$
    – draks ...
    Jul 16, 2012 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .