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)

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,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]

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

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)

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

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)

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

Prog

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

Crossrefs

Cf. A053218, A053221 (first differences).

Sequence in context: A002663 A099855 A347435 * A364415 A189418 A027992

Adjacent sequences: A003466 A003467 A003468 * A003470 A003471 A003472

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

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

Title corrected by Geoffrey Critzer, Jun 29 2013

Status

approved