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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a natural number $m$, let $|m|=\{1<\dots<m\}$ be the linearly ordered set with $m$ distinct elements. Then consider the partially ordered set obtained by taking the cartesian product $|2| \times |n|$, where $(a,b)\leq(c,d)$ iff $a\leq c$ and $b\leq d$.

A total extension of a poset $P$ is a total order on the underlying set of $P$ that extends the partial order structure.

Then, is there a closed-form formula for the number of distinct total extensions of $|2|\times |n|$?

share|cite|improve this question
up vote 3 down vote accepted

If you take the elements of $|2|$ to be ( and ), then for any total extension of $|2|\times|n|$ the first component of all pairs constitute a string of balanced parentheses -- and each such balanced string gives rise to a total extension.

Therefore your answer is the $n$th Catalan number, which is $\frac{1}{n+1}\binom{2n}{n}$.

share|cite|improve this answer
Nifty, thanks! $ $ – Harry Gindi Mar 13 '12 at 20:51

Yes, there is. It is the same as filling the Young tableau of shape $2\times n$ with numbers $\{1, 2, \ldots, 2n\}$. It is the same as $n$-th Catalan's number $$C_n = \frac{1}{n+1}\binom{2n}{n}.$$ To see the last part you could construct a bijection between your total orders and correct parenthesis expressions of length $2n$ -- for that kind of expression to be balanced it is necessary and sufficient to have equal number of opening symbols "(" and closing symbols ")" and at every point in the expression the number of currently opened braces to be non-zero. However, this is exactly what your ordering condition forces.

More complicated Young tableaux can be calculated using the hook formula (try to google it) that has a beautiful probabilistic proof that can be seen here.

share|cite|improve this answer
dtldarek, wondering: If you look at the set of total extensions of the poset in question, is there an "obvious" partial ordering on this set with maximal element given by the sequence 112233...nn and with minimal element given by the sequence 123...n123...n. I'm modeling the various ways of composing "cubically suspended" strict omega-categories – Harry Gindi Mar 15 '12 at 15:03

This is an answer for question posted in one of the comments.

Sorry, I don't know what a "cubically suspended" strict omega-category is, so I do not know anything related. I don't know of any special orderings on the set you describe, but you can create tons and tons of artificial ones.

One way is to look for distances and norms for permutations and then design function $f$ that combines them into $g(x) = f(d(x,112233),d(x,123123))$ such that your condition holds. Trivial example is $f(d_1, d_2) = \langle {d_1 \leq 0, d_2 > 0} \rangle$ with standard partial order on $\{true, false\}^2$.

You may also think about those sequences as two copies of set $\{1, \ldots, n\}$ painted, say, red and green (in a sequence ...4...4..., the first symbol 4 is red and the second is green). Then, if you consider the set of indices of green numbers, your minimal and maximal elements are the boundaries, you cannot get smaller than in 112233..., you can get greater than in 123..123... Just add some set ordering, I think there are many that will fit.

One more way is that you could split your sequence in half and construct step-differences, i.e. 010 010 for 1122 3344 and 111 111 for 1234 1234, and then apply some even simple metrics.

I know I haven't answered your question--those are just some examples. However, I hope it will be useful to you, even if only a bit.

share|cite|improve this answer
Thanks! I was thinking that perhaps the way to mess with it would be to take the transitive reflexive closure of the relation <, where a<b iff a can be obtained from b by transposing a higher number left past a lower number (assume that the righthand copy of each number lives in a fixed position, then pass a higher number past one of these fixed lower numbers). – Harry Gindi Mar 16 '12 at 9:58
@HarryGindi Yeah, I think that is possible, but those kind of things get complicated very quickly. – dtldarek Mar 16 '12 at 13:25

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.