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
Examples
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;
...
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.
Programs
-
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
Comments