0,3

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 ((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

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

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.

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

Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.

Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.

Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.

Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.

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

Christian Bean, Bjarki Gudmundsson, and Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.

Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.

Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.

Colin Defant and Kai Zheng, Stack-sorting with consecutive-pattern-avoiding stacks, arXiv:2008.12297 [math.CO], 2020.

John B. Dobson, A matrix variation on Ramus's identity for lacunary sums of binomial coefficients, arXiv preprint arXiv:1610.09361 [math.NT], 2016.

Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. (2021) Vol. 25, 515-541, Remark 10.

Juan B. Gil and Jessica A. Tomasko, Fibonacci colored compositions and applications, arXiv:2108.06462 [math.CO], 2021.

Mats Granvik, Alternating powers of 2 as convoluted divisor recurrence

Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016. See Table 1.1 p. 2.

S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

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

Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. Also on arXiv, arXiv:1302.2274 [math.CO], 2013.

Olivia Nabawanda and Fanja Rakotondrajao, The sets of flattened partitions with forbidden patterns, arXiv:2011.07304 [math.CO], 2020.

R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.

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.

Christoph Wernhard and Wolfgang Bibel, Learning from Łukasiewicz and Meredith: Investigations into Proof Structures (Extended Version), arXiv:2104.13645 [cs.AI], 2021.

Yan X. Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015.

Index entries for sequences related to Boolean functions

Index to divisibility sequences

Index entries for related partition-counting sequences

Index entries for linear recurrences with constant coefficients, signature (2).

Index entries for sequences related to Chebyshev polynomials.

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

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)

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

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

(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

(Sage) [sum(stirling_number2(n, j) for j in (0..2)) for n in (0..35)] # G. C. Greubel, Jun 02 2020

(Python)

def A011782(n): return 1 if n == 0 else 2**(n-1) # Chai Wah Wu, May 11 2022

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.

Sequence in context: A141531 A084633 A000079 * A120617 A131577 A155559

Adjacent sequences: A011779 A011780 A011781 * A011783 A011784 A011785

nonn,nice,easy,changed

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

Additional comments from Emeric Deutsch, May 14 2001

Typo corrected by Philippe Deléham, Oct 25 2008

approved