A130103 Expansion of e.g.f. e^(2x)-(1+x)*e^x+x.

0, 1, 1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, 33554406, 67108837, 134217700, 268435427, 536870882, 1073741793, 2147483616

Offset: 0

Author

Paul Barry, May 07 2007

Keywords

• easy
• nonn

Comments

Partial sums are A130104.

Essentially the same as the Euler numbers A000295.

Number of binary strings of length n where 0 is not used or is used at least twice and 1 is used at least once. For example, for n=3 the strings are 100, 010, 001, 111. - Enrique Navarrete, Feb 06 2025

Also the number of ordered set partitions of an n-set into 2 sets such that the first set cannot have a single element and the second set has at least one element. For example, for n=3 the ordered set partitions are: { },{1,2,3}; {1,2},{3}; {1,3},{2}; {2,3},{1}. - Enrique Navarrete, Feb 14 2025

Examples

			G.f. = x + x^2 + 4*x^3 + 11*x^4 + 26*x^5 + 57*x^6 + 120*x^7 + 247*x^8 + ...
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..3321
• Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 18.
• Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. A000295.

Programs

Maple

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+n od: seq(a[n], n=0..30); # Zerinvary Lajos, Feb 22 2008

Mathematica

Join[{0,1},LinearRecurrence[{4,-5,2},{1,4,11},40]] (* Harvey P. Dale, May 16 2014 *)
a[ n_] := If[ n < 2, Boole[n == 1], 2^n - (1 + n)]; (* Michael Somos, Aug 17 2015 *)

PARI

{a(n) = if( n<2, n==1, 2^n - (1+n))}; /* Michael Somos, Aug 17 2015 */

Formula

G.f.: x(1-3x+5x^2-2x^3)/((1-x)^2*(1-2x)).

E.g.f.: e^(2x)-(1+x)*e^x+x.

a(n) = 2^n-n-1+C(1,n)-C(0,n).

a(n) = A130102(n+1)/2.

a(n) = Sum_{i=1..n} i*2^(n-i) - Ctibor O. Zizka, Feb 23 2008