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

%I #19 Jan 16 2023 14:56:02

%S 1,1,1,1,3,3,1,7,21,26,6,1,15,105,400,803,782,340,34

%N 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 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 K. H. Kim, Boolean Matrix Theory and Applications, Marcel Decker Inc., 1982, page 44.

%H 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 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 T(n,0) = 1 = A000012(n).

%F T(n,1) = 2^n - 1 = A000225(n).

%F T(n,2) = binomial(2^n-1,2) = A134057(n).

%e 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 Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 3, 3;

%e 1, 7, 21, 26, 6;

%e 1, 15, 105, 400, 803, 782, 340, 34;

%e ...

%t independentQ[collection_] := If[MemberQ[collection, Table[0, {nn}]] \[Or] !

%t DuplicateFreeQ[collection], False, Apply[And,Table[! MemberQ[ Map[Clip[Total[#]] &,Subsets[Drop[collection, {i}], {2, Length[collection]}]],

%t collection[[i]]], {i, 1, Length[collection]}]]]; Map[Select[#, # > 0 &] &,

%t Table[Table[Length[Select[Subsets[Tuples[{0, 1}, nn], {i}], independentQ[#] &]], {i, 0, 7}], {nn, 0, 4}]] // Grid

%Y Columns k=0..2 give: A000012, A000225, A134057.

%Y Row sums give A102896.

%K nonn,tabf,more

%O 0,5

%A _Geoffrey Critzer_, Jun 28 2022