OFFSET
0,4
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
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).
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
EXAMPLE
G.f. = x + x^2 + 4*x^3 + 11*x^4 + 26*x^5 + 57*x^6 + 120*x^7 + 247*x^8 + ...
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 *)
PROG
(PARI) {a(n) = if( n<2, n==1, 2^n - (1+n))}; /* Michael Somos, Aug 17 2015 */
CROSSREFS
KEYWORD
easy,nonn,changed
AUTHOR
Paul Barry, May 07 2007
STATUS
approved