Bruno L. O. Andreotti - cp's OEIS frontend

User: Bruno L. O. Andreotti

Bruno L. O. Andreotti has authored 2 sequences.

A362895 a(n) is the length of the smallest orbit of the n-th natural downset.

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

Offset: 0

Bruno L. O. Andreotti, May 09 2023

Under a partial order based on the bitwise OR operation (see Wikipedia link) as a join, the set N_n = {0,1,2,...,n-1} is downward closed for all nonnegative integers n. Let N_n under the bitwise ordering be the n-th 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 n-th 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 n-th natural downset (see examples for an illustration of n = 5).
Intuitively, this can be understood as the number of ways to internally rotate the n-th 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 n-th 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.

			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}

Bruno L. O. Andreotti, Table of n, a(n) for n = 0..9999
Bruno L. O. Andreotti, Python program for n = 0 to 128
Wikipedia, Bitwise OR

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

Python
```
# See Andreotti link.
```

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

A341633 a(n) is the cardinality of the central rank of the free distributive lattice on n generators.

Original entry on oeis.org

1, 2, 4, 24, 621, 492288, 81203064840

Offset: 1

Bruno L. O. Andreotti, Feb 16 2021

Sequence for 2 <= n <= 5 is given in Church (1940); n = 1 obtained trivially from {} - {{}} - {{}, {1}}; n = 6 and n = 7 obtained from the triangle A269699.
a(n) is also provably the number of downward closed subsets of the powerset of {1,2,3,...,n} which have the cardinality 2^(n-1).
If FD(n) (the free distributive lattice on n generators) is rank unimodal for all n, then a(n) is the largest cardinality of any rank of FD(n).
If FD(n) is rank unimodal and Sperner for all n, then a(n) is the width of FD(n). (Consequences provable, antecedents are open questions - e.g., Stanley (1991))
This sequence is related (at least methodologically) to the n-th Dedekind number (A000372), which is obtained from the cardinality of FD(n).
a(n) is also the number of balanced monotone Boolean functions. - Aniruddha Biswas, Nov 22 2024

			a(4)=24 is obtained from the 24 downsets on the 8th and central rank of FD(4), each containing 8 members (enumeration is arbitrary):
   1  {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
   2  {{},{1},{2},{4},{1,2},{1,4},{2,4},{1,2,4}}
   3  {{},{1},{3},{4},{1,3},{1,4},{3,4},{1,3,4}}
   4  {{},{2},{3},{4},{2,3},{2,4},{3,4},{2,3,4}}
   5  {{},{1},{2},{3},{4},{1,2},{1,3},{2,3}}
   6  {{},{1},{2},{3},{4},{1,2},{1,4},{2,4}}
   7  {{},{1},{2},{3},{4},{1,3},{1,4},{3,4}}
   8  {{},{1},{2},{3},{4},{2,3},{2,4},{3,4}}
   9  {{},{1},{2},{3},{4},{1,2},{1,3},{1,4}}
  10  {{},{1},{2},{3},{4},{1,2},{2,3},{2,4}}
  11  {{},{1},{2},{3},{4},{1,3},{2,3},{3,4}}
  12  {{},{1},{2},{3},{4},{1,4},{2,4},{3,4}}
  13  {{},{1},{2},{3},{4},{1,2},{2,3},{3,4}}
  14  {{},{1},{2},{3},{4},{1,2},{1,4},{3,4}}
  15  {{},{1},{2},{3},{4},{1,2},{1,4},{2,3}}
  16  {{},{1},{2},{3},{4},{1,2},{1,3},{3,4}}
  17  {{},{1},{2},{3},{4},{1,2},{2,4},{3,4}}
  18  {{},{1},{2},{3},{4},{1,2},{1,3},{2,4}}
  19  {{},{1},{2},{3},{4},{1,3},{1,4},{2,3}}
  20  {{},{1},{2},{3},{4},{1,3},{1,4},{2,4}}
  21  {{},{1},{2},{3},{4},{1,3},{2,4},{3,4}}
  22  {{},{1},{2},{3},{4},{1,3},{2,3},{2,4}}
  23  {{},{1},{2},{3},{4},{1,4},{2,3},{3,4}}
  24  {{},{1},{2},{3},{4},{1,4},{2,3},{2,4}}

Bruno L. O. Andreotti, Python program for n = 1 to 6
Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
Aniruddha Biswas and Palash Sarkar, Counting Unate and Monotone Boolean Functions Under Restrictions of Balancedness and Non-Degeneracy, J. Int. Seq. (2025) Vol. 28, Art. No. 25.3.4. See pp. 3, 11-12.
Randolph Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940). 732--734.
Randolph Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940). 732--734.
Richard P. Stanley, Some application of algebra to combinatorics, Discrete Applied Mathematics, 34 (1991), 241-277.

Cf. A000372, A269699, A371722.

Python
```
# See Andreotti link.
```

a(n) = A269699(n, 2^(n-1)).

cp's OEIS Frontend

User: Bruno L. O. Andreotti

A362895 a(n) is the length of the smallest orbit of the n-th natural downset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula