|
| |
|
|
A011782
|
|
Expansion of (1-x)/(1-2*x) in powers of x.
|
|
217
|
|
|
|
1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Apart from initial term, same as A000079 (powers of 2).
Also the number of compositions (i.e. ordered partitions) of n, so that (for example) 3 = 2 + 1 and 3 = 1 + 2 are counted separately. See also A000079. - Toby Bartels (toby+sloane(AT)math.ucr.edu), Aug 27 2003
Number of ways of putting n unlabeled items into (any number of) labeled boxes where every box contains at least one item. Also "unimodal permutations of n items", i.e. those which rise then fall. (E.g. for three items: ABC, ACB, BCA and CBA are unimodal) - Henry Bottomley, Jan 17 2001.
Number of permutations in S_n avoiding the patterns 213 and 312. - Tuwani Albert Tshifhumulo (tat(AT)univen.ac.za), Apr 20 2001. More generally (see Simion and Schmidt), the number of permutations in S_n avoiding (i) the 123 and 132 patterns; (ii) the 123 and 213 patterns; (iii) the 132 and 213 patterns; (iv) the 132 and 231 patterns; (v) the 132 and 312 patterns; (vi) the 213 and 231 patterns; (vii) the 213 and 312 patterns; (viii) the 231 and 312 patterns; (ix) the 231 and 321 patterns; (x) the 312 and 321 patterns.
a(n+2)= number of distinct Boolean functions of n variables under action of symmetric group.
Also the number of unlabeled (1+2)-free posets. - Detlef Pauly, May 25 2003
Image of the central binomial coefficients A000984 under the Riordan array ((1-x),x(1-x)). - Paul Barry, Mar 18 2005
Binomial transform of (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...); inverse binomial transform of A007051 . - Philippe DELEHAM, Jul 04 2005
Also, number of rationals in [0, 1) whose binary expansions terminate after n bits. - Brad Chalfan (brad(AT)chalfan.net), May 29 2006
Equals row sums of triangle A144157 [From Gary W. Adamson, Sep 12 2008]
Prepend A089067 with a 1, getting (1, 1, 3, 5, 13, 23, 51,...) as polcoeff A(x); then (1, 1, 2, 4, 8, 16,...) = A(x)/A(x^2). [Gary W. Adamson, Feb 18 2010]
a(n) = A173921(A000079(n)). [From Reinhard Zumkeller, Mar 04 2010]
An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 2, 8, 32 and 128, lead to this sequence. For the corner squares these vectors lead to the companion sequence A094373. [Johannes W. Meijer, Aug 15 2010]
a(n) = SUM(A093873(k)/A093875(k): 2^n<=k<2^(n+1)), sums of rows of the full tree of Kepler's harmonic fractions. [From Reinhard Zumkeller, Oct 17 2010]
From Paul Curtz, Jul 20 2011. (Start)
Array T(m,n)=2*T(m,n-1) + T(m-1,n)
1, 1, 2, 4, 8, 16, =a(n)
1, 3, 8, 20, 48, 112, =A001792,
1, 5, 18, 56, 160, 432, =A001793
1, 7, 32, 120, 400, 1232, =A001794,
1, 9, 50, 220, 840, 2912, =A006974,followed with A006975,A006976,
gives nonzero coefficients of Chebyshev polynomials of first kind A039991=
1,
1, 0,
2, 0, -1,
4, 0, -3, 0,
8, 0, -8, 0, 1.
T(m,n) third vertical: 2*n^2, n positive (A001105).
Fourth vertical appears in Janet table even rows,last vertical (A168342 array, A138509,rank 3,13,=A166911)). (End)
A131577(n) and differences are
0, 1, 2, 4, 8, 16,
1, 1, 2, 4, 8, 16, =a(n),
0, 1, 2, 4, 8, 16,
1, 1, 2, 4, 8, 16.
Number of 2-color necklaces of length 2n equal to their complemented reversal. For length 2n+1, the number is 0. [David W. Wilson, Jan 01 2012]
|
|
|
REFERENCES
|
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), http://faculty.valpo.edu/lpudwell/slides/notredame.pdf, 2012. - From N. J. A. Sloane, Jan 03 2013
R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985, see pp. 392-393.
|
|
|
LINKS
|
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=2, pages 10-11). - From N. J. A. Sloane, May 09 2012
Index entries for sequences related to Boolean functions
Index to divisibility sequences
Index entries for related partition-counting sequences
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
FORMULA
|
a(0)=1, a(n)=2^(n-1).
G.f.: (1 - x) / (1 - 2*x) = 1 / (1 - x / (1 - x)). - Michael Somos, Apr 18 2012
E.g.f.: cosh(z)*exp(z)=(exp(2z)+1)/2.
a(0) = 1 and for n>0, a(n) = sum of all previous terms.
a(n)=Sum{k=0..n, binomial(n, 2*k)}. - Paul Barry, Feb 25 2003
a(n)=Sum{k=0..n, binomial(n, k)*(1+(-1)^k)/2 } - Paul Barry, May 27 2003
a(n)=floor((1+2^n)/2) - Toby Bartels (toby+sloane(AT)math.ucr.edu), Aug 27 2003
G.f.: sum(i>=0, x^i/(1-x)^i) - Jon Perry, Jul 10 2004
a(n)=sum{k=0..n, (-1)^(n-k)*binomial(k+1, n-k)*binomial(2*k, k)} - Paul Barry, Mar 18 2005
a(n) = Sum_{k, 0<=k<=[n/2]} A055830(n-k,k) . - Philippe DELEHAM, Oct 22 2006
a(n) = Sum_{k, 0<=k<=n} A098158(n,k) . - Philippe DELEHAM, Dec 04 2006
G.f.: 1/(1-(x+x^2+x^3+...)) [From Geoffrey Critzer, Aug 30 2008]
a(n)=A000079(n) - A131577(n) .
E.g.f.: (exp(2*x)+1)/2 = (G(0) + 1)/2 ; G(k) = 1 + 2*x/(2*k+1 - x*(2*k+1)/(x + (k+1)/G(k+1))) ; (continued fraction). - Sergei N. Gladkovskii, Dec 03 2011
A051049(n) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 18 2012
A008619(n) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Apr 18 2012
INVERT transform is A122367. MOBIUS transform is A123707. EULER transform of A059966. PSUM transform is A000079. PSUMSIGN transform is A078008. BINOMIAL transform is A007051. REVERT transform is A105523. A002866(n) = a(n)*n!. - Michael Somos, Apr 18 2012
G.f.: U(0) where U(k)= 1 + x*(k+3) - x*(k+2)/U(k+1) ; (continued fraction, 1-step). - Sergei N. Gladkovskii, Oct 10 2012
|
|
|
EXAMPLE
|
1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 32*x^6 + 64*x^7 + ...
|
|
|
MATHEMATICA
|
f[s_] := Append[s, Ceiling[Plus @@ s]]; Nest[f, {1}, 32] (* or *)
CoefficientList[ Series[(1 - x)/(1 - 2x), {x, 0, 32}], x] (from Robert G. Wilson v, Jul 07 2006)
|
|
|
PROG
|
(PARI) {a(n) = if( n<1, n==0, 2^(n-1))}
(MAGMA) [Floor((1+2^n)/2): n in [0..35]]; // Vincenzo Librandi, Aug 21 2011
|
|
|
CROSSREFS
|
Cf. A051486, A000670, A051486, A144157, A082140, A082141, A082138, A082139, A080951, A080929, A057711, A089067.
((1-x)/(1-2x))^k: A011782, A045623, A058396, A062109, A169792-A169797; a row of A160232.
Row sums of triangle A100257.
Cf. A211216.
Sequence in context: A034008 A123344 A141531 A166444 A084633 A122803 A000079
Adjacent sequences: A011779 A011780 A011781 * A011783 A011784 A011785
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
killough(AT)wagner.convex.com (Lee D. Killough). Additional comments from Emeric Deutsch, May 14, 2001.
|
|
|
EXTENSIONS
|
Corrected typo. - Philippe DELEHAM, Oct 25 2008
|
|
|
STATUS
|
approved
|
| |
|
|
