A003469 Number of minimal covers of an (n + 1)-set by a collection of n nonempty subsets, a(n) = A035348(n,n-1).

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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]

Partial sums of A053221.

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

Examples

			From _Jianing Song_, Sep 04 2018: (Start)
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)
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
• Anthony J. Macula, Lewis Carroll and the Enumeration of Minimal Covers, Math. Mag. vol. 68, n4, p 274 Oct '95.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Index entries for linear recurrences with constant coefficients, signature (7,-19,25,-16,4)

Crossrefs

Cf. A053218, A053221 (first differences).

Programs

Magma

[2^n*(n+1)-(n^2+3*n+2)/2: n in [1..30]]; // Vincenzo Librandi, Aug 19 2011

Maple

a := n -> add((n+1)*binomial(n+1, k+1)/2, k=1..n):
seq(a(n), n=1..30); # Zerinvary Lajos, May 08 2007
A003469:=(-1+z+z**2)/(2*z-1)**2/(z-1)**3; # conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

Table[(n+1)2^n-(n+1)(n+2)/2, {n, 200}] (* Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *)
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 *)

PARI

a(n) = (n+1)*2^n-(n+1)*(n+2)/2;

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

Extensions

Offset changed from 2 to 1 by Vincenzo Librandi, Aug 19 2011

Title corrected by Geoffrey Critzer, Jun 29 2013