login
a(n) = n*(2^n - 1).
17

%I #56 Feb 13 2022 04:32:52

%S 0,1,6,21,60,155,378,889,2040,4599,10230,22517,49140,106483,229362,

%T 491505,1048560,2228207,4718574,9961453,20971500,44040171,92274666,

%U 192937961,402653160,838860775,1744830438,3623878629,7516192740,15569256419,32212254690

%N a(n) = n*(2^n - 1).

%C a(n)/2^n is the expected value of the cardinality of the generalized union of n randomly selected (with replacement) subsets of [n] where the probability of selection is equal for all subsets. - _Geoffrey Critzer_, May 18 2009

%C Form a triangle in which interior members T(i,j) = T(i-1,j-1) + T(i-1,j). The exterior members are given by 1,2,3,...,2*n-1: T(1,1) = n, T(2,1) = n-1, T(3,1) = n-2, ..., T(n,1) = 1 and T(2,2) = n + 1, T(3,3) = n + 2, ..., T(n,n) = 2*n - 1. The sum of all members will reproduce this sequence. For example, with n = 4 the exterior members are 1 to 7: row(1) = 4; row(2) = 3,5; row(3) = 2,8,6; row(4) = 1,10,14,7. The sum of all these members is 60, the fourth term in the sequence. - _J. M. Bergot_, Oct 16 2012

%H Harry J. Smith, <a href="/A066524/b066524.txt">Table of n, a(n) for n = 0..250</a>

%H A. Umar, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Umar/umar2.html">Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations</a>, Journal of Integer Sequences, 14 (2011), #11.7.5.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-13,12,-4).

%F a(n) = 2*a(n-1) + 2^n = A000225(n) * A001477(n) = A036289(n) - A001477(n).

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

%F a(n) = n * Sum_{j = 1..n} binomial(n,j), n >= 0. - _Zerinvary Lajos_, May 10 2007

%F Row sums of triangles A132751. - _Gary W. Adamson_, Aug 28 2007

%F E.g.f.: x*(2*exp(2*x) - exp(x)). From an earlier rewritten comment. - _Wolfdieter Lang_, Feb 16 2016

%F Sum_{n>=1} 1/a(n) = A335764. - _Amiram Eldar_, Jun 23 2020

%e a(4) = 4*(2^4 - 1) = 4*15 = 60.

%t Table[n*2^n-n,{n,0,3*4!}] (* _Vladimir Joseph Stephan Orlovsky_, Apr 25 2010 *)

%t CoefficientList[Series[x (1 - 2 x^2)/((1 - x) (1 - 2 x))^2, {x, 0, 30}], x] (* _Michael De Vlieger_, Jan 24 2016 *)

%o (Sage) [gaussian_binomial(n,1,2)*n for n in range(0,29)] # _Zerinvary Lajos_, May 29 2009

%o (Magma) [n*(2^n-1): n in [0..30]]; // _Vincenzo Librandi_, Jan 24 2016

%Y Cf. A000225, A132751, A335764.

%K nonn,easy

%O 0,3

%A _Henry Bottomley_, Jan 08 2002