A055080 Triangle T(n,k) read by rows, giving number of k-member minimal covers of an unlabeled n-set, k=1..n.

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 9, 4, 1, 1, 9, 23, 17, 5, 1, 1, 12, 51, 65, 28, 6, 1, 1, 16, 103, 230, 156, 43, 7, 1, 1, 20, 196, 736, 863, 336, 62, 8, 1, 1, 25, 348, 2197, 4571, 2864, 664, 86, 9, 1, 1, 30, 590, 6093, 22952, 25326, 8609, 1229, 115, 10, 1, 1, 36, 960

Offset

1,5

Comments

Also number of unlabeled split graphs on n vertices and with a k-element clique (cf. A048194).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.

Vladeta Jovovic, Binary matrices up to row and column permutations

G. F. Royle, Counting Set Covers and Split Graphs, J. Integer Seqs., 3 (2000), #00.2.6.

Eric Weisstein's World of Mathematics, Minimal covers

Formula

T(n,k) = A028657(n,k) - A028657(n-1,k). - Andrew Howroyd, Feb 28 2023

Example

Triangle begins:
  1;
  1,  1;
  1,  2,   1;
  1,  4,   3,   1;
  1,  6,   9,   4,   1;
  1,  9,  23,  17,   5,   1;
  1, 12,  51,  65,  28,   6,  1;
  1, 16, 103, 230, 156,  43,  7, 1;
  1, 20, 196, 736, 863, 336, 62, 8, 1;
  ...
There are four minimal covers of an unlabeled 3-set: one 1-cover {{1,2,3}}, two 2-covers {{1,2},{3}}, {{1,2},{1,3}} and one 3-cover {{1},{2},{3}}.

Prog

(PARI) \\ Needs A(n, m) from A028657.
T(n, k) = A(n-k, k) - if(k<n, A(n-1-k, k))
{ for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print) } \\ Andrew Howroyd, Feb 28 2023

Crossrefs

Row sums give A048194.

Columns are A000012, A087811, A005783, A005784, A005785 A005786, A055066.

Diagonals are A000012, A000027, A005744, A005745, A005746, A005771, A005747, A005748.

Cf. A035348 for labeled case.

Cf. A002620, A028657.

Sequence in context: A034781 A110470 A347699 * A034367 A058717 A034371

Adjacent sequences: A055077 A055078 A055079 * A055081 A055082 A055083

Keyword

nonn,tabl

Author

Vladeta Jovovic, Jun 13 2000

Status

approved