7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Have you tried calculating the first few terms and entering the sequence into oeis.org? $\endgroup$ – Samuel Apr 15 '15 at 16:24
  • $\begingroup$ A huge underestimate is to group vectors by their sum, then randomly order vectors with the same sum. So $\prod_i{n\choose i}!$ $\endgroup$ – Empy2 Apr 15 '15 at 16:32
  • $\begingroup$ 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. $\endgroup$ – Shane Apr 15 '15 at 16:38
  • $\begingroup$ @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? $\endgroup$ – Pburg Apr 15 '15 at 16:44
  • 4
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Apr 15 '15 at 17:14
-3
$\begingroup$

You have to first rank the entries of the vectors. As in the first ranking of your example the second entry has 'higher importance' for the order (-> higher priority for the actual ranking of the whole set) than the first entry.

In your second ranking it is the first entry which dominates for the purpose of ranking.

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$

$\endgroup$
  • 1
    $\begingroup$ 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).$ $\endgroup$ – Pburg Apr 15 '15 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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