A003469 - OEIS

%I M4153 #71 Nov 22 2023 06:32:45

%S 1,6,22,65,171,420,988,2259,5065,11198,24498,53157,114583,245640,

%T 524152,1113959,2359125,4980546,10485550,22019865,46137091,96468716,

%U 201326292,419430075,872414881,1811938950,3758095978,7784627789,16106126895,33285996048

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

%C 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]

%C Partial sums of A053221.

%C 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

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

%H Vincenzo Librandi, <a href="/A003469/b003469.txt">Table of n, a(n) for n = 1..1000</a>

%H T. Hearne and C. G. Wagner, <a href="http://dx.doi.org/10.1016/0012-365X(73)90141-6">Minimal covers of finite sets</a>, Discr. Math. 5 (1973), 247-251.

%H Anthony J. Macula, <a href="https://www.jstor.org/stable/2690571">Lewis Carroll and the Enumeration of Minimal Covers</a>, Math. Mag. vol. 68, n4, p 274 Oct '95.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (7,-19,25,-16,4)

%F G.f.: x*(1 - x - x^2)/((1 - x)^3*(1 - 2*x)^2).

%F a(n) = (n + 1)*2^n - (n + 1)*(n + 2)/2. - _Paul Barry_, Jan 27 2003

%F E.g.f.: (2*x + 1)*exp(2*x) - (x^2/2 + 2*x + 1)*exp(x). - _Jianing Song_, Sep 04 2018

%e From _Jianing Song_, Sep 04 2018: (Start)

%e For n = 4 the inverted triangle table is:

%e 1     2     3     4

%e    3     5     7

%e       8    12

%e         20

%e So a(4) = 1 + 2 + 3 + 4 + 3 + 5 + 7 + 8 + 12 + 20 = 65.

%e For n = 5 the inverted triangle table is:

%e 1     2     3     4     5

%e    3     5     7     9

%e       8    12    16

%e         20    28

%e            48

%e So a(5) = 1 + 2 + 3 + 4 + 5 + 3 + 5 + 7 + 9 + 8 + 12 + 16 + 20 + 28 + 48 = 171. (End)

%p a := n -> add((n+1)*binomial(n+1, k+1)/2, k=1..n):

%p seq(a(n), n=1..30); # _Zerinvary Lajos_, May 08 2007

%p A003469:=(-1+z+z**2)/(2*z-1)**2/(z-1)**3; # conjectured by _Simon Plouffe_ in his 1992 dissertation

%t Table[(n+1)2^n-(n+1)(n+2)/2, {n, 200}] (* _Vladimir Joseph Stephan Orlovsky_, Jun 30 2011 *)

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

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

%o (Magma) [2^n*(n+1)-(n^2+3*n+2)/2: n in [1..30]]; // _Vincenzo Librandi_, Aug 19 2011

%Y Cf. A053218, A053221 (first differences).

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_

%E Offset changed from 2 to 1 by _Vincenzo Librandi_, Aug 19 2011

%E Title corrected by _Geoffrey Critzer_, Jun 29 2013