cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A011782 Coefficients of expansion of (1-x)/(1-2*x) in powers of x.

Original entry on oeis.org

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, 4294967296, 8589934592
Offset: 0

Views

Author

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

Keywords

Comments

Apart from initial term, same as A000079 (powers of 2).
Number of compositions (ordered partitions) of n. - Toby Bartels, 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, 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) is the number of distinct Boolean functions of n variables under action of symmetric group.
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, 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
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
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
The sequence is the INVERT transform of (1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...). - Gary W. Adamson, Jul 16 2015
Number of threshold graphs on n nodes [Hougardy]. - Falk Hüffner, Dec 03 2015
Number of ternary words of length n in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017
a(n) is the number of words of length n over an alphabet of two letters, of which one letter appears an even number of times (the empty word of length 0 is included). See the analogous odd number case in A131577, and the Balakrishnan reference in A006516 (the 4-letter odd case), pp. 68-69, problems 2.66, 2.67 and 2.68. - Wolfdieter Lang, Jul 17 2017
Number of D-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are D-equivalent iff the positions of pattern D are identical in these paths. - Sergey Kirgizov, Apr 08 2018
Number of color patterns (set partitions) for an oriented row of length n using two or fewer colors (subsets). Two color patterns are equivalent if we permute the colors. For a(4)=8, the 4 achiral patterns are AAAA, AABB, ABAB, and ABBA; the 4 chiral patterns are the 2 pairs AAAB-ABBB and AABA-ABAA. - Robert A. Russell, Oct 30 2018
The determinant of the symmetric n X n matrix M defined by M(i,j) = (-1)^max(i,j) for 1 <= i,j <= n is equal to a(n) * (-1)^(n*(n+1)/2). - Bernard Schott, Dec 29 2018
For n>=1, a(n) is the number of permutations of length n whose cyclic representations can be written in such a way that when the cycle parentheses are removed what remains is 1 through n in natural order. For example, a(4)=8 since there are exactly 8 permutations of this form, namely, (1 2 3 4), (1)(2 3 4), (1 2)(3 4), (1 2 3)(4), (1)(2)(3 4), (1)(2 3)(4), (1 2)(3)(4), and (1)(2)(3)(4). Our result follows readily by conditioning on k, the number of parentheses pairs of the form ")(" in the cyclic representation. Since there are C(n-1,k) ways to insert these in the cyclic representation and since k runs from 0 to n-1, we obtain a(n) = Sum_{k=0..n-1} C(n-1,k) = 2^(n-1). - Dennis P. Walsh, May 23 2020
Maximum number of preimages that a permutation of length n + 1 can have under the consecutive-231-avoiding stack-sorting map. - Colin Defant, Aug 28 2020
a(n) is the number of occurrences of the empty set {} in the von Neumann ordinals from 0 up to n. Each ordinal k is defined as the set of all smaller ordinals: 0 = {}, 1 = {0}, 2 = {0,1}, etc. Since {} is the foundational element of all ordinals, the total number of times it appears grows as powers of 2. - Kyle Wyonch, Mar 30 2025

Examples

			G.f. = 1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 32*x^6 + 64*x^7 + 128*x^8 + ...
    ( -1   1  -1)
det (  1   1   1)  = 4
    ( -1  -1  -1)

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.
  • S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
  • Xavier Merlin, Methodix Algèbre, Ellipses, 1995, p. 153.

Links

Crossrefs

Cf. A000670, A051486, A053120, A057711, A080929, A080961, A082138.
Cf. A082139, A082140, A082141, A089067, A144157, A131577, A211216.
Sequences with g.f.'s of the form ((1-x)/(1-2*x))^k: this sequence (k=1), A045623 (k=2), A058396 (k=3), A062109 (k=4), A169792 (k=5), A169793 (k=6), A169794 (k=7), A169795 (k=8), A169796 (k=9), A169797 (k=10).
Cf. A005418 (unoriented), A122746(n-3) (chiral), A016116 (achiral).
Row sums of triangle A100257.
A row of A160232.
Row 2 of A278984.

Programs

  • Haskell
    a011782 n = a011782_list !! n
a011782_list = 1 : scanl1 (+) a011782_list
-- Reinhard Zumkeller, Jul 21 2013
  • Magma
    [Floor((1+2^n)/2): n in [0..35]]; // Vincenzo Librandi, Aug 21 2011
  • Maple
    A011782:= n-> ceil(2^(n-1)): seq(A011782(n), n=0..50); # Wesley Ivan Hurt, Feb 21 2015
with(PolynomialTools):  A011782:=seq(coeftayl((1-x)/(1-2*x), x = 0, k),k=0..10^2); # Muniru A Asiru, Sep 26 2017
  • 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 *)
Table[Sum[StirlingS2[n, k], {k,0,2}], {n, 0, 30}] (* Robert A. Russell, Apr 25 2018 *)
Join[{1},NestList[2#&,1,40]] (* Harvey P. Dale, Dec 06 2018 *)
  • PARI
    {a(n) = if( n<1, n==0, 2^(n-1))};
  • PARI
    Vec((1-x)/(1-2*x) + O(x^30)) \\ Altug Alkan, Oct 31 2015
  • Python
    def A011782(n): return 1 if n == 0 else 2**(n-1) # Chai Wah Wu, May 11 2022
  • Sage
    [sum(stirling_number2(n,j) for j in (0..2)) for n in (0..35)] # G. C. Greubel, Jun 02 2020

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(2*z) + 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..floor(n/2)} A055830(n-k, k). - Philippe Deléham, Oct 22 2006
a(n) = Sum_{k=0..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).
a(n) = A173921(A000079(n)). - Reinhard Zumkeller, Mar 04 2010
a(n) = Sum_{k=2^n..2^(n+1)-1} A093873(k)/A093875(k), sums of rows of the full tree of Kepler's harmonic fractions. - Reinhard Zumkeller, Oct 17 2010
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
G.f.: 1 + x/(1 + x)*( 1 + 3*x/(1 + 3*x)*( 1 + 5*x/(1 + 5*x)*( 1 + 7*x/(1 + 7*x)*( 1 + ... )))). - Peter Bala, May 27 2017
a(n) = Sum_{k=0..2} stirling2(n, k).
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=2. - Robert A. Russell, Apr 25 2018
a(n) = A053120(n, n), n >= 0, (main diagonal of triangle of Chebyshev's T polynomials). - Wolfdieter Lang, Nov 26 2019

Extensions

Additional comments from Emeric Deutsch, May 14 2001
Typo corrected by Philippe Deléham, Oct 25 2008

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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