Sign up ×
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.

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.

share|cite|improve this question
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? –  joriki Apr 9 '11 at 7:21
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 Do you understand me better now? –  Dedalus Apr 9 '11 at 8:32

1 Answer 1

up vote 0 down vote accepted

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

share|cite|improve this answer
Would you mind sharing your solution? –  draks ... Jul 16 '12 at 14:57

Your Answer


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.