

A362895


a(n) is the length of the smallest orbit of the nth natural downset


1



1, 1, 1, 1, 1, 3, 3, 1, 1, 4, 12, 12, 6, 6, 4, 1, 1, 5, 20, 30, 30, 60, 60, 20, 10, 10, 30, 30, 10, 10, 5, 1, 1, 6, 30, 60, 60, 180, 180, 60, 60, 120, 360, 360, 180, 180, 120, 30, 15, 15, 60, 90, 90, 180, 180, 60, 20, 20, 60, 60, 15, 15, 6, 1, 1, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Under a partial order based on the bitwise OR operation (see Wikipedia link) as a join, the set N_n = {0,1,2,...,n1} is downward closed for all nonnegative integers n. Let N_n under the bitwise ordering be the nth natural downset. E.g., for n = 0 to n = 9, the sets N_0 through N_9 under a bitwise ordering form the downward closed posets represented by the following Hasse diagrams:
7 7
/  \ /  \
3 3 3 5 3 5 6 3 5 6 3 5 6
/ \  \  X \  X X   X X   X X 
1 1 2 1 2 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 8
 \ / \ / \  / \  / \  / \  / \ \ / /
{} 0 0 0 0 0 0 0 0 0
The sequence {a(n)} lists the length of the orbit of the nth natural downset under permutations of its atoms. Equivalently, given the smallest number k such that n <= 2^k, a(n) is the number of labeled downsets of the Boolean lattice of size 2^k which are isomorphic to the nth natural downset (see examples for an illustration of n = 5).
Intuitively, this can be understood as the number of ways to internally rotate the nth natural downset within this smallest Boolean lattice that it can fit while still being a downset.
More generally, for any nonnegative integer m, the number of labeled downsets of the Boolean lattice of size 2^m which are isomorphic to the nth natural downset is given by a(n)*binomial(m,k). Thus, a(n) is the smallest (nonzero) orbit length, which obtains when binomial(m,k) = 1.
Note that k is the number of elements in the 1st rank of the posets, which is also the number of vertices in the corresponding simplicial complex, or k = ceiling(log_2(n)) for n > 0.


LINKS



FORMULA

Let k(n) = ceiling(log_2(n)) for n > 0, j = 2^k(n)n, and k(j) = ceiling(log_2(j)) if j > 0, or k(j) = 0 if j = 0. Provably, a(n) = a(j)*binomial(k(n),k(j)).


EXAMPLE

For any nonnegative integer m the natural downset corresponding to N_2^m = {0,1,2,...,(2^m)1} is a Boolean lattice. For n = 5 we have k = 3 which corresponds to the Boolean lattice N_2^k = N_8. We can illustrate a(5) = 3 under this definition based on the three downsets of N_8 which are isomorphic to N_5 (including N_5 itself):
7
/  \
3 5 6 3 5 6
 X X  :  \ , / \ , / 
1 2 4 1 2 4 1 2 4 1 2 4
\  / \  / \  / \  /
0 0 0 0
Other examples:
a(0) = 1: N_0 = {} > {}
a(1) = 1: N_1 = {0} > {0}
a(2) = 1: N_2 = {0,1} > {0,1}
a(3) = 1: N_3 = {0,1,2} > {0,1,2}
a(4) = 1: N_4 = {0,1,2,3} > {0,1,2,3}
a(5) = 3: N_5 = {0,1,2,3,4} > {0,1,2,3,4}, {0,1,2,4,5}, {0,1,2,4,6}
a(6) = 3: N_6 = {0,1,2,3,4,5} > {0,1,2,3,4,5}, {0,1,2,3,4,6}, {0,1,2,4,5,6}
a(7) = 1: N_7 = {0,1,2,3,4,5,6} > {0,1,2,3,4,5,6}
a(8) = 1: N_8 = {0,1,2,3,4,5,6,7} > {0,1,2,3,4,5,6,7}
a(9) = 4: N_9 = {0,1,2,3,4,5,6,7,8} > {0,1,2,3,4,5,6,7,8}, {0,1,2,3,8,9,10,11}, {0,1,4,5,8,9,12,13}, {0,2,4,6,8,10,12,14}


PROG

(Python) # See Andreotti link.


CROSSREFS

The cardinality of the downset lattice of the nth natural downset is A132581. When n is a power of 2, the cardinality of the downset lattice of the nth natural downset is the log_2(n)th Dedekind number (A000372).


KEYWORD

nonn,easy


AUTHOR



STATUS

approved



