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

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

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

Table of n, a(n) for n=0..18.

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

T(n,0) = 1 = A000012(n).

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

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

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

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

Row sums give A102896.

Sequence in context: A079268 A102316 A261767 * A300620 A133709 A173651

Adjacent sequences: A355312 A355313 A355314 * A355316 A355317 A355318

Keyword

nonn,tabf,more

Author

Geoffrey Critzer, Jun 28 2022

Status

approved