|
%I #365 Mar 09 2024 12:33:24
%S 1,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,
%T 131072,262144,524288,1048576,2097152,4194304,8388608,16777216,
%U 33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592
%N Coefficients of expansion of (1-x)/(1-2*x) in powers of x.
%C Apart from initial term, same as A000079 (powers of 2).
%C Also the number of compositions (ordered partitions) of n. - Toby Bartels, Aug 27 2003
%C 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
%C 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.
%C a(n+2) is the number of distinct Boolean functions of n variables under action of symmetric group.
%C Also the number of unlabeled (1+2)-free posets. - Detlef Pauly, May 25 2003
%C Image of the central binomial coefficients A000984 under the Riordan array ((1-x), x*(1-x)). - _Paul Barry_, Mar 18 2005
%C Binomial transform of (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...); inverse binomial transform of A007051. - _Philippe Deléham_, Jul 04 2005
%C Also, number of rationals in [0, 1) whose binary expansions terminate after n bits. - Brad Chalfan, May 29 2006
%C Equals row sums of triangle A144157. - _Gary W. Adamson_, Sep 12 2008
%C 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
%C 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
%C From _Paul Curtz_, Jul 20 2011: (Start)
%C Array T(m,n) = 2*T(m,n-1) + T(m-1,n):
%C 1, 1, 2, 4, 8, 16, ... = a(n)
%C 1, 3, 8, 20, 48, 112, ... = A001792,
%C 1, 5, 18, 56, 160, 432, ... = A001793,
%C 1, 7, 32, 120, 400, 1232, ... = A001794,
%C 1, 9, 50, 220, 840, 2912, ... = A006974, followed with A006975, A006976, gives nonzero coefficients of Chebyshev polynomials of first kind A039991 =
%C 1,
%C 1, 0,
%C 2, 0, -1,
%C 4, 0, -3, 0,
%C 8, 0, -8, 0, 1.
%C T(m,n) third vertical: 2*n^2, n positive (A001105).
%C Fourth vertical appears in Janet table even rows, last vertical (A168342 array, A138509, rank 3, 13, = A166911)). (End)
%C A131577(n) and differences are:
%C 0, 1, 2, 4, 8, 16,
%C 1, 1, 2, 4, 8, 16, = a(n),
%C 0, 1, 2, 4, 8, 16,
%C 1, 1, 2, 4, 8, 16.
%C 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
%C 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
%C 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
%C Number of self conjugate integer partitions with exactly n parts for n>=1. - _David Christopher_, Aug 18 2014
%C The sequence is the INVERT transform of (1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...). - _Gary W. Adamson_, Jul 16 2015
%C Also, number of threshold graphs on n nodes [Hougardy]. - _Falk Hüffner_, Dec 03 2015
%C Number of ternary words of length n in which binary subwords appear in the form 10...0. - _Milan Janjic_, Jan 25 2017
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%D Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
%D Xavier Merlin, Methodix Algèbre, Ellipses, 1995, p. 153.
%H Vincenzo Librandi, <a href="/A011782/b011782.txt">Table of n, a(n) for n = 0..1000</a>
%H Michael A. Allen, <a href="https://arxiv.org/abs/2209.01377">On a Two-Parameter Family of Generalizations of Pascal's Triangle</a>, arXiv:2209.01377 [math.CO], 2022.
%H Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, <a href="https://arxiv.org/abs/2308.09344">On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks</a>, arXiv:2308.09344 [math.CO], 2023.
%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.
%H Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.
%H Jean-Luc Baril and José Luis Ramírez, <a href="https://arxiv.org/abs/2302.12741">Descent distribution on Catalan words avoiding ordered pairs of Relations</a>, arXiv:2302.12741 [math.CO], 2023.
%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
%H Christian Bean, Bjarki Gudmundsson, and Henning Ulfarsson, <a href="https://arxiv.org/abs/1705.04109">Automatic discovery of structural rules of permutation classes</a>, arXiv:1705.04109 [math.CO], 2017.
%H Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, <a href="https://arxiv.org/abs/2306.03155">Pattern-avoiding stabilized-interval-free permutations</a>, arXiv:2306.03155 [math.CO], 2023.
%H Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 14.
%H Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.
%H Johann Cigler, <a href="http://arxiv.org/abs/1501.04750">Some remarks and conjectures related to lattice paths in strips along the x-axis</a>, arXiv:1501.04750 [math.CO], 2015.
%H Johann Cigler, <a href="https://arxiv.org/abs/2212.02118">Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials</a>, arXiv:2212.02118 [math.NT], 2022.
%H Colin Defant and Kai Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-sorting with consecutive-pattern-avoiding stacks</a>, arXiv:2008.12297 [math.CO], 2020.
%H John B. Dobson, <a href="https://arxiv.org/abs/1610.09361">A matrix variation on Ramus's identity for lacunary sums of binomial coefficients</a>, arXiv preprint arXiv:1610.09361 [math.NT], 2016.
%H Mareike Fischer, <a href="https://doi.org/10.1007/s00026-021-00539-2">Extremal Values of the Sackin Tree Balance Index</a>, Ann. Comb. (2021) Vol. 25, 515-541, Remark 10.
%H Juan B. Gil and Jessica A. Tomasko, <a href="https://arxiv.org/abs/2108.06462">Fibonacci colored compositions and applications</a>, arXiv:2108.06462 [math.CO], 2021.
%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 23.
%H Mats Granvik, <a href="/A011782/a011782.txt">Alternating powers of 2 as convoluted divisor recurrence</a>
%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.
%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015-2016. See Table 1.1 p. 2.
%H S. Heubach and T. Mansour, <a href="http://arXiv.org/abs/math.CO/0310197">Counting rises, levels and drops in compositions</a>, arXiv:math/0310197 [math.CO], 2003.
%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.
%H Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I,</a> arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=2, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. Also on <a href="http://arxiv.org/abs/1302.2274">arXiv</a>, arXiv:1302.2274 [math.CO], 2013.
%H Olivia Nabawanda and Fanja Rakotondrajao, <a href="https://arxiv.org/abs/2011.07304">The sets of flattened partitions with forbidden patterns</a>, arXiv:2011.07304 [math.CO], 2020.
%H R. A. Proctor, <a href="https://arxiv.org/abs/math/0606404">Let's Expand Rota's Twelvefold Way for Counting Partitions!</a>, arXiv:math/0606404 [math.CO], 2006-2007.
%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
%H Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, <a href="https://arxiv.org/abs/2310.12366">Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation</a>, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
%H R. Simion and F. W. Schmidt, <a href="http://dx.doi.org/10.1016/S0195-6698(85)80052-4">Restricted permutations</a>, European J. Combin., 6, 383-406, 1985, see pp. 392-393.
%H Christoph Wernhard and Wolfgang Bibel, <a href="https://arxiv.org/abs/2104.13645">Learning from Łukasiewicz and Meredith: Investigations into Proof Structures (Extended Version)</a>, arXiv:2104.13645 [cs.AI], 2021.
%H Yan X. Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>
%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (2).
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%F a(0) = 1, a(n) = 2^(n-1).
%F G.f.: (1 - x) / (1 - 2*x) = 1 / (1 - x / (1 - x)). - _Michael Somos_, Apr 18 2012
%F E.g.f.: cosh(z)*exp(z) = (exp(2*z) + 1)/2.
%F a(0) = 1 and for n>0, a(n) = sum of all previous terms.
%F a(n) = Sum_{k=0..n} binomial(n, 2*k). - _Paul Barry_, Feb 25 2003
%F a(n) = Sum_{k=0..n} binomial(n,k)*(1+(-1)^k)/2. - _Paul Barry_, May 27 2003
%F a(n) = floor((1+2^n)/2). - Toby Bartels (toby+sloane(AT)math.ucr.edu), Aug 27 2003
%F G.f.: Sum_{i>=0} x^i/(1-x)^i. - _Jon Perry_, Jul 10 2004
%F a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(k+1, n-k)*binomial(2*k, k). - _Paul Barry_, Mar 18 2005
%F a(n) = Sum_{k=0..floor(n/2)} A055830(n-k, k). - _Philippe Deléham_, Oct 22 2006
%F a(n) = Sum_{k=0..n} A098158(n,k). - _Philippe Deléham_, Dec 04 2006
%F G.f.: 1/(1 - (x + x^2 + x^3 + ...)). - _Geoffrey Critzer_, Aug 30 2008
%F a(n) = A000079(n) - A131577(n).
%F a(n) = A173921(A000079(n)). - _Reinhard Zumkeller_, Mar 04 2010
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F a(n) = A000041(n) + A056823(n). - _Omar E. Pol_, Aug 31 2013
%F 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
%F 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
%F a(n) = Sum_(k=0..2} stirling2(n, k).
%F 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
%F a(n) = A053120(n, n), n >= 0, (main diagonal of triangle of Chebyshev's T polynomials). - _Wolfdieter Lang_, Nov 26 2019
%e 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 + ...
%e ( -1 1 -1)
%e det ( 1 1 1) = 4
%e ( -1 -1 -1)
%p A011782:= n-> ceil(2^(n-1)): seq(A011782(n), n=0..50); # _Wesley Ivan Hurt_, Feb 21 2015
%p with(PolynomialTools): A011782:=seq(coeftayl((1-x)/(1-2*x), x = 0, k),k=0..10^2); # _Muniru A Asiru_, Sep 26 2017
%t f[s_] := Append[s, Ceiling[Plus @@ s]]; Nest[f, {1}, 32] (* _Robert G. Wilson v_, Jul 07 2006 *)
%t CoefficientList[ Series[(1-x)/(1-2x), {x, 0, 32}], x] (* _Robert G. Wilson v_, Jul 07 2006 *)
%t Table[Sum[StirlingS2[n, k], {k,0,2}], {n, 0, 30}] (* _Robert A. Russell_, Apr 25 2018 *)
%t Join[{1},NestList[2#&,1,40]] (* _Harvey P. Dale_, Dec 06 2018 *)
%o (PARI) {a(n) = if( n<1, n==0, 2^(n-1))};
%o (PARI) Vec((1-x)/(1-2*x) + O(x^30)) \\ _Altug Alkan_, Oct 31 2015
%o (Magma) [Floor((1+2^n)/2): n in [0..35]]; // _Vincenzo Librandi_, Aug 21 2011
%o (Haskell)
%o a011782 n = a011782_list !! n
%o a011782_list = 1 : scanl1 (+) a011782_list
%o -- _Reinhard Zumkeller_, Jul 21 2013
%o (Sage) [sum(stirling_number2(n,j) for j in (0..2)) for n in (0..35)] # _G. C. Greubel_, Jun 02 2020
%o (Python)
%o def A011782(n): return 1 if n == 0 else 2**(n-1) # _Chai Wah Wu_, May 11 2022
%Y Cf. A000670, A051486, A053120, A057711, A080929, A080961, A082138.
%Y Cf. A082139, A082140, A082141, A089067, A144157, A131577, A211216.
%Y 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).
%Y Cf. A005418 (unoriented), A122746(n-3) (chiral), A016116 (achiral).
%Y Row sums of triangle A100257.
%Y A row of A160232.
%Y Row 2 of A278984.
%K nonn,nice,easy
%O 0,3
%A Lee D. Killough (killough(AT)wagner.convex.com)
%E Additional comments from _Emeric Deutsch_, May 14 2001
%E Typo corrected by _Philippe Deléham_, Oct 25 2008
|
