|
|
A003469
|
|
Number of minimal covers of an (n + 1)-set by a collection of n nonempty subsets, a(n) = A035348(n,n-1).
(Formerly M4153)
|
|
2
|
|
|
1, 6, 22, 65, 171, 420, 988, 2259, 5065, 11198, 24498, 53157, 114583, 245640, 524152, 1113959, 2359125, 4980546, 10485550, 22019865, 46137091, 96468716, 201326292, 419430075, 872414881, 1811938950, 3758095978, 7784627789, 16106126895, 33285996048
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A cover of a set S is a collection of nonempty subsets of S whose union is S. A cover of S is called minimal if none of its proper subsets covers S. [from the Hearne/Wagner reference]
Construct an inverted triangle table with n rows as follows: the first row are numbers from 1 to n; for the other rows, each number is the sum of the two numbers above it. Then a(n) is the sum of all numbers in the table. See examples below. - Jianing Song, Sep 04 2018
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1 - x - x^2)/((1 - x)^3*(1 - 2*x)^2).
a(n) = (n + 1)*2^n - (n + 1)*(n + 2)/2. - Paul Barry, Jan 27 2003
E.g.f.: (2*x + 1)*exp(2*x) - (x^2/2 + 2*x + 1)*exp(x). - Jianing Song, Sep 04 2018
|
|
EXAMPLE
|
For n = 4 the inverted triangle table is:
1 2 3 4
3 5 7
8 12
20
So a(4) = 1 + 2 + 3 + 4 + 3 + 5 + 7 + 8 + 12 + 20 = 65.
For n = 5 the inverted triangle table is:
1 2 3 4 5
3 5 7 9
8 12 16
20 28
48
So a(5) = 1 + 2 + 3 + 4 + 5 + 3 + 5 + 7 + 9 + 8 + 12 + 16 + 20 + 28 + 48 = 171. (End)
|
|
MAPLE
|
a := n -> add((n+1)*binomial(n+1, k+1)/2, k=1..n):
|
|
MATHEMATICA
|
CoefficientList[Series[((2*x + 1)*Exp[2*x] - (x^2/2 + 2*x + 1)*Exp[x])/x, {x, 0, 200}], x]*Table[(k+1)!, {k, 0, 200}] (* Stefano Spezia, Sep 04 2018 *)
|
|
PROG
|
(PARI) a(n) = (n+1)*2^n-(n+1)*(n+2)/2;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|