9
$\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$
11
  • $\begingroup$ Have you tried calculating the first few terms and entering the sequence into oeis.org? $\endgroup$
    – Samuel
    Apr 15, 2015 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, 2015 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, 2015 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, 2015 at 16:44
  • 5
    $\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$ Apr 15, 2015 at 17:14

2 Answers 2

1
$\begingroup$

As observed by Brian M. Scott in the comments, these are linear extensions of the subset lattice (also known as the Boolean lattice).

So let us look them up, following Samuel's advice: compute some small instances in SageMath,

sage: for n in range(2,5): (n, posets.BooleanLattice(n).linear_extensions().cardinality())
(2, 2)
(3, 48)
(4, 1680384)

followed by OEIS lookup, which takes us to A046873. From there (and following links) we learn the next numbers:

5 14807804035657359360
6 141377911697227887117195970316200795630205476957716480
7 630470261306055898099742878692134361829979979674711225065761605059425237453564989302659882866111738567871048772795838071474370002961694720

and apparently that is how far they are currently known (the $n=7$ value computed in 2017 by Brouwer and Christensen). OEIS also gives pointers to asymptotic results.

$\endgroup$
-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
  • 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, 2015 at 16:29

You must log in to answer this question.

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