

A011782


Coefficients of expansion of (1x)/(12*x) in powers of x.


811



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
(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 (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.
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 ((1x), x*(1x)).  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
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
Array T(m,n) = 2*T(m,n1) + T(m1,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)
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 2color necklaces of length 2n equal to their complemented reversal. For length 2n+1, the number is 0.  David W. Wilson, Jan 01 2012
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
Also, 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 4letter odd case), pp. 6869, problems 2.66, 2.67 and 2.68.  Wolfdieter Lang, Jul 17 2017
Number of Dequivalence classes of Łukasiewicz paths. Łukasiewicz paths are Dequivalent 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 AAABABBB and AABAABAA.  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(n1,k) ways to insert these in the cyclic representation and since k runs from 0 to n1, we obtain a(n) = Sum_{k=0..n1} C(n1,k) = 2^(n1).  Dennis P. Walsh, May 23 2020
Maximum number of preimages that a permutation of length n + 1 can have under the consecutive231avoiding stacksorting map.  Colin Defant, Aug 28 2020


REFERENCES

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 2428, Winter 1997.
S. Kitaev, Patterns in Permutations and Words, SpringerVerlag, 2011. see p. 399 Table A.7
Xavier Merlin, Methodix Algèbre, Ellipses, 1995, p. 153.


LINKS



FORMULA

a(0) = 1, a(n) = 2^(n1).
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/(1x)^i.  Jon Perry, Jul 10 2004
a(n) = Sum_{k=0..n} (1)^(nk)*binomial(k+1, nk)*binomial(2*k, k).  Paul Barry, Mar 18 2005
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 degreen 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 degreen polynomial such that p(k) = a(k) for k = 0, 1, ..., 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, 1step).  Sergei N. Gladkovskii, Oct 10 2012
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).
a(n) = A053120(n, n), n >= 0, (main diagonal of triangle of Chebyshev's T polynomials).  Wolfdieter Lang, Nov 26 2019


EXAMPLE

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)


MAPLE

with(PolynomialTools): A011782:=seq(coeftayl((1x)/(12*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[(1x)/(12x), {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 *)


PROG

(PARI) {a(n) = if( n<1, n==0, 2^(n1))};
(PARI) Vec((1x)/(12*x) + O(x^30)) \\ Altug Alkan, Oct 31 2015
(Haskell)
a011782 n = a011782_list !! n
a011782_list = 1 : scanl1 (+) a011782_list
(Sage) [sum(stirling_number2(n, j) for j in (0..2)) for n in (0..35)] # G. C. Greubel, Jun 02 2020
(Python)


CROSSREFS



KEYWORD

nonn,nice,easy


AUTHOR

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


EXTENSIONS



STATUS

approved



