# How many ways to order vectors in $\{0,1\}^n$?

How many different rankings can be produced for the vectors in $\{0,1\}^n$ that also respect the usual $\geqq$ ordering of vectors (defined below)?

I want to produce a complete ordering where, for $x\neq y$, if $x_i \geq y_i$ for all $i=1,\dots,n$ then $x$ is greater than $y$ according to that new vector ordering.

This leaves some freedom in the ordering where I could have $(1,0,0) > (0,1,1)$ as a possibility. $(1,0,0) < (0,1,1)$ is also allowed.

Example: For $n=2$, there are two rankings.

$(1,1) \geq (0,1) \geq (1,0) \geq (0,0)$ and $(1,1) \geq' (1,0) \geq' (0,1) \geq' (0,0)$.

• Have you tried calculating the first few terms and entering the sequence into oeis.org? – Samuel Apr 15 '15 at 16:24
• A huge underestimate is to group vectors by their sum, then randomly order vectors with the same sum. So $\prod_i{n\choose i}!$ – Empy2 Apr 15 '15 at 16:32
• And the obvious overestimate is $(2^n-2)!$, which are the number of ways of having all ones at the top end and all zeros at the bottom end and any arbitrary order in between. – Shane Apr 15 '15 at 16:38
• @TravisJ I am only imposing that if $x_i≥y_i$ for all $i=1,…,n$ then $x$ is greater than or equal to $y$ according to that new vector ordering. I think of this as the usual partial ordering of vectors. So the question becomes how many different ways can this partial ordering be made complete? – Pburg Apr 15 '15 at 16:44
• You’re looking for the number of linear extensions of the subset order on an $n$-element set; to the best of my knowledge this is unknown in general. – Brian M. Scott Apr 15 '15 at 17:14

How many possibilities are there to rank the $n$ entries there are?
The answer to this (and your) question is $n!=n(n-1)\cdots$
• Doesn't this impose more structure than I want? I could have $(0,1,1)>(1,0,1)$ which seems to imply that the middle entry is more important than the first. But I might also allow that $(1,0,0)>(0,1,0).$ – Pburg Apr 15 '15 at 16:29