OFFSET
0,5
COMMENTS
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.
REFERENCES
K. H. Kim, Boolean Matrix Theory and Applications, Marcel Decker Inc., 1982, page 44.
LINKS
P. Erdős and D. Kleitman, Extremal problems among subsets of a set, Discrete Mathematics, 8, 1974, 281-294.
D. Kleitman, On a combinatorial problem of Erdős, Proc. Amer. Math Soc, 17 (1966) 139-141.
FORMULA
EXAMPLE
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}}.
Triangle T(n,k) begins:
1;
1, 1;
1, 3, 3;
1, 7, 21, 26, 6;
1, 15, 105, 400, 803, 782, 340, 34;
...
MATHEMATICA
independentQ[collection_] := If[MemberQ[collection, Table[0, {nn}]] \[Or] !
DuplicateFreeQ[collection], False, Apply[And, Table[! MemberQ[ Map[Clip[Total[#]] &, Subsets[Drop[collection, {i}], {2, Length[collection]}]],
collection[[i]]], {i, 1, Length[collection]}]]]; Map[Select[#, # > 0 &] &,
Table[Table[Length[Select[Subsets[Tuples[{0, 1}, nn], {i}], independentQ[#] &]], {i, 0, 7}], {nn, 0, 4}]] // Grid
CROSSREFS
KEYWORD
nonn,tabf,more
AUTHOR
Geoffrey Critzer, Jun 28 2022
STATUS
approved