login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A011782 Expansion of (1-x)/(1-2*x) in powers of x. 303
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 Deléham, 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. - 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)). - 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. - 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

Edges and also central terms of triangle A198069: a(0) = A198069(0,0) and for n > 0: a(n) = A198069(n,0) = A198069(n,2^n) = A198069(n,2^(n-1)). - Reinhard Zumkeller, May 26 2013

These could be called the composition numbers (see the second comment) since the equivalent sequence for partitions is A000041, the partition numbers. - Omar E. Pol, Aug 28 2013

Number of self conjugate integer partitions with exactly n parts for n>=1. - David Christopher, Aug 18 2014

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.

J. Cigler, Some remarks on lattice paths in strips along the x-axis; http://homepage.univie.ac.at/johann.cigler/preprints/lattice-paths.pdf, 2014.

S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Mats Granvik, Alternating powers of 2 as convoluted divisor recurrence

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

R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv math.CO.0606404.

L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 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.

Index entries for sequences related to Boolean functions

Index to divisibility sequences

Index entries for related partition-counting sequences

Index to sequences with linear recurrences with constant coefficients, signature (2).

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 Deléham, Oct 22 2006

a(n) = Sum_{k, 0<=k<=n} A098158(n,k). - Philippe Deléham, Dec 04 2006

G.f.: 1/(1-(x+x^2+x^3+...)). - 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

a(n) = A000041(n) + A056823(n). - Omar E. Pol, Aug 31 2013

E.g.f.: E(0), where E(k) = 1 + x/( 2*k+1 - x/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 25 2013

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] (* Robert G. Wilson v, Jul 07 2006 *)

CoefficientList[ Series[(1 - x)/(1 - 2x), {x, 0, 32}], x] (* 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

(Haskell)

a011782 n = a011782_list !! n

a011782_list = 1 : scanl1 (+) a011782_list

-- Reinhard Zumkeller, Jul 21 2013

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 A000079 A120617

Adjacent sequences:  A011779 A011780 A011781 * A011783 A011784 A011785

KEYWORD

nonn,nice,easy

AUTHOR

Lee D. Killough (killough(AT)wagner.convex.com)

EXTENSIONS

Additional comments from Emeric Deutsch, May 14 2001

Typo corrected by Philippe Deléham, Oct 25 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 22 18:41 EST 2014. Contains 249807 sequences.