cp's OEIS Frontend

A355315 Triangular array read by rows: T(n,k) is the number of independent collections of subsets of [n] having exactly k members, n>=0, 0<=k<=A347025(n).

%I A355315 #19 Jan 16 2023 14:56:02
%S A355315 1,1,1,1,3,3,1,7,21,26,6,1,15,105,400,803,782,340,34
%N A355315 Triangular array read by rows: T(n,k) is the number of independent collections of subsets of [n] having exactly k members, n>=0, 0<=k<=A347025(n).
%C A355315 Here, an independent collection of subsets of [n] is such that no member is a union of other members.  The empty set is not contained in any independent set although the empty collection is independent.  These collections are the bases of the union closed families counted in A102896 which gives the row sums of this sequence.
%D A355315 K. H. Kim, Boolean Matrix Theory and Applications, Marcel Decker Inc., 1982, page 44.
%H A355315 P. Erdős and D. Kleitman, <a href="https://doi.org/10.1016/j.disc.2006.03.013">Extremal problems among subsets of a set</a>, Discrete Mathematics, 8, 1974, 281-294.
%H A355315 D. Kleitman, <a href="https://doi.org/10.1090/S0002-9939-1966-0184866-9">On a combinatorial problem of Erdős</a>, Proc. Amer. Math Soc, 17 (1966) 139-141.
%F A355315 T(n,0) = 1 = A000012(n).
%F A355315 T(n,1) = 2^n - 1 = A000225(n).
%F A355315 T(n,2) = binomial(2^n-1,2) = A134057(n).
%e A355315 T(3,4) = 6 because we have: {{1}, {2}, {1, 3}, {2, 3}}, {{1}, {3}, {1, 2}, {2, 3}}, {{1}, {1, 2}, {1, 3}, {2, 3}}, {{2}, {3}, {1, 2}, {1, 3}}, {{2}, {1, 2}, {1, 3}, {2, 3}}, {{3}, {1, 2}, {1, 3}, {2, 3}}.
%e A355315 Triangle T(n,k) begins:
%e A355315   1;
%e A355315   1,  1;
%e A355315   1,  3,   3;
%e A355315   1,  7,  21,  26,   6;
%e A355315   1, 15, 105, 400, 803, 782, 340, 34;
%e A355315   ...
%t A355315 independentQ[collection_] := If[MemberQ[collection, Table[0, {nn}]] \[Or] !
%t A355315     DuplicateFreeQ[collection], False, Apply[And,Table[! MemberQ[   Map[Clip[Total[#]] &,Subsets[Drop[collection, {i}], {2, Length[collection]}]],
%t A355315       collection[[i]]], {i, 1, Length[collection]}]]]; Map[Select[#, # > 0 &] &,
%t A355315   Table[Table[Length[Select[Subsets[Tuples[{0, 1}, nn], {i}], independentQ[#] &]], {i, 0, 7}], {nn, 0, 4}]] // Grid
%Y A355315 Columns k=0..2 give: A000012, A000225, A134057.
%Y A355315 Row sums give A102896.
%K A355315 nonn,tabf,more
%O A355315 0,5
%A A355315 _Geoffrey Critzer_, Jun 28 2022