cp's OEIS Frontend

A269699 Irregular triangle read by rows: T(n, k) is the number of k-element proper ideals of the n-dimensional Boolean lattice, with 0 < k < 2^n.

%I A269699 #52 Oct 28 2021 07:11:05
%S A269699 1,1,2,1,1,3,3,4,3,3,1,1,4,6,10,13,18,19,24,19,18,13,10,6,4,1,1,5,10,
%T A269699 20,35,61,95,155,215,310,387,470,530,580,605,621,605,580,530,470,387,
%U A269699 310,215,155,95,61,35,20,10,5,1,1,6,15,35,75,156,306,605,1110,2045,3512,5913,9415
%N A269699 Irregular triangle read by rows: T(n, k) is the number of k-element proper ideals of the n-dimensional Boolean lattice, with 0 < k < 2^n.
%C A269699 The set of maximal elements of an ideal is an antichain; conversely, the down-set of a nonempty antichain is an ideal. The down-set of the top element of the n-dimensional Boolean lattice contains all 2^n elements of the lattice, and thus is not a proper ideal.
%C A269699 Empirically, the rows are unimodal.
%C A269699 By the Markowsky paper, T(n, k) = T(n, 2^n - k).
%C A269699 Also, T(n,k) is the number of n-dimensional Ferrers diagrams with k nodes (i.e., (n-1)-dimensional partitions) that fit into an n-dimensional hypercube of side 2 (i.e., a Boolean or binary hupercube). T(n, k) = T(n, 2^n - k) follows from the map that takes a Ferrers diagram to its complement in the box. - _Suresh Govindarajan_, Apr 10 2016
%H A269699 Danny Rorabaugh and Suresh Govindarajan, <a href="/A269699/b269699.txt">Table of n, a(n) for n = 1..279</a>
%H A269699 George Markowsky, <a href="http://dx.doi.org/10.1016/0012-365X(80)90156-9">The level polynomials of the free distributive lattices</a>, Discrete Math., 29 (1980), 275-285.
%H A269699 Wikipedia, <a href="https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29">Boolean algebra</a> and <a href="https://en.wikipedia.org/wiki/Ideal_%28order_theory%29">Ideal</a>.
%e A269699 For row n = 3, the k-element proper ideals are the down-sets of the following antichains:
%e A269699 T(3, 1) = 1: [{}];
%e A269699 T(3, 2) = 3: [{0}], [{1}], [{2}];
%e A269699 T(3, 3) = 3: [{0},{1}], [{0},{2}], [{1},{2}];
%e A269699 T(3, 4) = 4: [{0,1}], [{0,2}], [{1,2}], [{0},{1},{2}];
%e A269699 T(3, 5) = 3: [{0,1},{2}], [{0,2},{1}], [{1,2},{0}];
%e A269699 T(3, 6) = 3: [{0,1},{0,2}], [{0,1},{1,2}], [{0,2},{1,2}];
%e A269699 T(3, 7) = 1: [{0,1},{0,2},{1,2}].
%e A269699 E.g., the 5-element down-set of [{0,1},{2}] is [{},{0},{1},{2},{0,1}].
%e A269699 The table begins:
%e A269699 n\k 1 2  3  4  5  6  7   8   9  10  11  12  13  14  15  16  17
%e A269699 1   1
%e A269699 2   1 2  1
%e A269699 3   1 3  3  4  3  3  1
%e A269699 4   1 4  6 10 13 18 19  24  19  18  13  10   6   4   1
%e A269699 5   1 5 10 20 35 61 95 155 215 310 387 470 530 580 605 621 605 ...
%o A269699 (Sage) # Returns row n.
%o A269699 def T(n):
%o A269699   B = posets.BooleanLattice(n)
%o A269699   t = [0]*(2^n + 1)
%o A269699   for A in B.antichains():
%o A269699     t[len(B.order_ideal(A))] += 1
%o A269699   return t[1:-1]
%Y A269699 Columns are: A000012 (k = 1), A000027 (k = 2), A000217 (k = 3), A000292 (k = 4), A095661 (k = 5).
%Y A269699 Cf. A007153 (row sums), A007318, A059119.
%K A269699 nonn,tabf
%O A269699 1,3
%A A269699 _Danny Rorabaugh_, Mar 03 2016