A173921 -id:A173921 - cp's OEIS frontend

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

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

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

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

			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)

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.
Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks, arXiv:2308.09344 [math.CO], 2023.
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.
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 14.
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.
Bishal Deb, Cyclic sieving phenomena via combinatorics of continued fractions, arXiv:2508.13709 [math.CO], 2025. See p. 42.
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.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 25.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
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
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
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.

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.

a011782 n = a011782_list !! n
a011782_list = 1 : scanl1 (+) a011782_list
-- Reinhard Zumkeller, Jul 21 2013

[Floor((1+2^n)/2): n in [0..35]]; // Vincenzo Librandi, Aug 21 2011

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))};
```

Vec((1-x)/(1-2*x) + O(x^30)) \\ Altug Alkan, Oct 31 2015

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

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

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

Additional comments from Emeric Deutsch, May 14 2001

Typo corrected by Philippe Deléham, Oct 25 2008

A001787 a(n) = n*2^(n-1).

Original entry on oeis.org

0, 1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264, 24576, 53248, 114688, 245760, 524288, 1114112, 2359296, 4980736, 10485760, 22020096, 46137344, 96468992, 201326592, 419430400, 872415232, 1811939328, 3758096384, 7784628224, 16106127360, 33285996544

Offset: 0

N. J. A. Sloane

Number of edges in an n-dimensional hypercube.
Number of 132-avoiding permutations of [n+2] containing exactly one 123 pattern. - Emeric Deutsch, Jul 13 2001
Number of ways to place n-1 nonattacking kings on a 2 X 2(n-1) chessboard for n >= 2. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 22 2001
Arithmetic derivative of 2^n: a(n) = A003415(A000079(n)). - Reinhard Zumkeller, Feb 26 2002
(-1) times the determinant of matrix A_{i,j} = -|i-j|, 0 <= i,j <= n.
a(n) is the number of ones in binary numbers 1 to 111...1 (n bits). a(n) = A000337(n) - A000337(n-1) for n = 2,3,... . - Emeric Deutsch, May 24 2003
The number of 2 X n 0-1 matrices containing n+1 1's and having no zero row or column. The number of spanning trees of the complete bipartite graph K(2,n). This is the case m = 2 of K(m,n). See A072590. - W. Edwin Clark, May 27 2003
Binomial transform of 0,1,2,3,4,5,... (A001477). Without the initial 0, binomial transform of odd numbers.
With an additional leading zero, [0,0,1,4,...] this is the binomial transform of the integers repeated A004526. Its formula is then (2^n*(n-1) + 0^n)/4. - Paul Barry, May 20 2003
Number of zeros in all different (n+1)-bit integers. - Ralf Stephan, Aug 02 2003
From Lekraj Beedassy, Jun 03 2004: (Start)
Final element of a summation table (as opposed to a difference table) whose first row consists of integers 0 through n (or first n+1 nonnegative integers A001477); illustrating the case n=5:
   0   1   2   3   4   5
     1   3   5   7   9
       4   8  12  16
        12  20  28
          32  48
            80
and the final element is a(5)=80. (End)
This sequence and A001871 arise in counting ordered trees of height at most k where only the rightmost branch at the root actually achieves this height and the count is by the number of edges, with k = 3 for this sequence and k = 4 for A001871.
Let R be a binary relation on the power set P(A) of a set A having n = |A| elements such that for all elements x,y of P(A), xRy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. Then a(n) = |R|. - Ross La Haye, Sep 21 2004
Number of 2 X n binary matrices avoiding simultaneously the right-angled numbered polyomino patterns (ranpp) (00;1) and (10;1). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in same relative order as those in the triple (x,y,z). - Sergey Kitaev, Nov 11 2004
Number of subsequences 00 in all binary words of length n+1. Example: a(2)=4 because in 000,001,010,011,100,101,110,111 the sequence 00 occurs 4 times. - Emeric Deutsch, Apr 04 2005
If you expand the n-factor expression (a+1)*(b+1)*(c+1)*...*(z+1), there are a(n) variables in the result. For example, the 3-factor expression (a+1)*(b+1)*(c+1) expands to abc+ab+ac+bc+a+b+c+1 with a(3) = 12 variables. - David W. Wilson, May 08 2005
An inverse Chebyshev transform of n^2, where g(x)->(1/sqrt(1-4*x^2))*g(x*c(x^2)), c(x) the g.f. of A000108. - Paul Barry, May 13 2005
Sequences A018215 and A058962 interleaved. - Graeme McRae, Jul 12 2006
The number of never-decreasing positive integer sequences of length n with a maximum value of 2*n. - Ben Paul Thurston, Nov 13 2006
Total size of all the subsets of an n-element set. For example, a 2-element set has 1 subset of size 0, 2 subsets of size 1 and 1 of size 2. - Ross La Haye, Dec 30 2006
Convolution of the natural numbers [A000027] and A045623 beginning [0,1,2,5,...]. - Ross La Haye, Feb 03 2007
If M is the matrix (given by rows) [2,1;0,2] then the sequence gives the (1,2) entry in M^n. - Antonio M. Oller-Marcén, May 21 2007
If X_1,X_2,...,X_n is a partition of a 2n-set X into 2-blocks then, for n > 0, a(n) is equal to the number of (n+1)-subsets of X intersecting each X_i (i=1,2,...,n). - Milan Janjic, Jul 21 2007
Number of n-permutations of 3 objects u,v,w, with repetition allowed, containing exactly one u. Example: a(2)=4 because we have uv, vu, uw and wu. - Zerinvary Lajos, Dec 27 2007
A member of the family of sequences defined by a(n) = n*[c(1)*...*c(r)]^(n-1); c(i) integer. This sequence has c(1)=2, A027471 has c(1)=3. - Ctibor O. Zizka, Feb 23 2008
a(n) is the number of ways to split {1,2,...,n-1} into two (possibly empty) complementary intervals {1,2,...,i} and {i+1,i+2,...,n-1} and then select a subset from each interval. - Geoffrey Critzer, Jan 31 2009
Equals the Jacobsthal sequence A001045 convolved with A003945: (1, 3, 6, 12, ...). - Gary W. Adamson, May 23 2009
Starting with offset 1 = A059570: (1, 2, 6, 14, 34, ...) convolved with (1, 2, 2, 2, ...). - Gary W. Adamson, May 23 2009
Equals the first left hand column of A167591. - Johannes W. Meijer, Nov 12 2009
The number of tatami tilings of an n X n square with n monomers is n*2^(n-1). - Frank Ruskey, Sep 25 2010
Under T. D. Noe's variant of the hypersigma function, this sequence gives hypersigma(2^n): a(n) = A191161(A000079(n)). - Alonso del Arte, Nov 04 2011
Number of Dyck (n+2)-paths with exactly one valley at height 1 and no higher valley. - David Scambler, Nov 07 2011
Equals triangle A059260 * A016777 as a vector, where A016777 = (3n + 1): [1, 4, 7, 10, 13, ...]. - Gary W. Adamson, Mar 06 2012
Main transitions in systems of n particles with spin 1/2 (see A212697 with b=2). - Stanislav Sykora, May 25 2012
Let T(n,k) be the triangle with (first column) T(n,1) = 2*n-1 for n >= 1, otherwise T(n,k) = T(n,k-1) + T(n-1,k-1), then a(n) = T(n,n). - J. M. Bergot, Jan 17 2013
Sum of all parts of all compositions (ordered partitions) of n. The equivalent sequence for partitions is A066186. - Omar E. Pol, Aug 28 2013
Starting with a(1)=1: powers of 2 (A000079) self-convolved. - Bob Selcoe, Aug 05 2015
Coefficients of the series expansion of the normalized Schwarzian derivative -S{p(x)}/6 of the polynomial p(x) = -(x-x1)*(x-x2) with x1 + x2 = 1 (cf. A263646). - Tom Copeland, Nov 02 2015
a(n) is the number of North-East lattice paths from (0,0) to (n+1,n+1) that have exactly one east step below y = x-1 and no east steps above y = x+1. Details can be found in Pan and Remmel's link. - Ran Pan, Feb 03 2016
Also the number of maximal and maximum cliques in the n-hypercube graph for n > 0. - Eric W. Weisstein, Dec 01 2017
Let [n]={1,2,...,n}; then a(n-1) is the total number of elements missing in proper subsets of [n] that contain n to form [n]. For example, for n = 3, a(2) = 4 since the proper subsets of [3] that contain 3 are {3}, {1,3}, {2,3} and the total number of elements missing in these subsets to form [3] is 4:  2 in the first subset, 1 in the second, and 1 in the third. - Enrique Navarrete, Aug 08 2020
Number of 3-permutations of n elements avoiding the patterns 132, 231. See Bonichon and Sun. - Michel Marcus, Aug 19 2022

			a(2)=4 since 2314, 2341,3124 and 4123 are the only 132-avoiding permutations of 1234 containing exactly one increasing subsequence of length 3.
x + 4*x^2 + 12*x^3 + 32*x^4 + 80*x^5 + 192*x^6 + 448*x^7 + ...
a(5) = 1*0 + 5*1 + 10*2 + 10*3 + 5*4 + 1*5 = 80, with 1,5,10,10,5,1 the 5th row of Pascal's triangle. - _J. M. Bergot_, Apr 29 2014

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 796.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 131.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 282.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..500
Rémi Abgrall and Wasilij Barsukow, Extensions of Active Flux to arbitrary order of accuracy, arXiv:2208.14476 [math.NA], 2022.
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
F. S. Al-Kharousi, A. Umar, and M. M. Zubairu, On injective partial Catalan monoids, arXiv:2501.00285 [math.GR], 2024. See p. 9.
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.
Douglas W. Bass and I. Hal Sudborough, Hamilton decompositions and (n/2)-factorizations of hypercubes, J. Graph Algor. Appl., Vol. 7, No. 1 (2003), pp. 79-98.
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
Harlan J. Brothers, Pascal's Prism: Supplementary Material.
David Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Frank Ellermann, Illustration of binomial transforms
Mohamed Elkadi and Bernard Mourrain, Symbolic-numeric methods for solving polynomial equations and applications, Chap 3. of A. Dickenstein and I. Z. Emiris, eds., Solving Polynomial Equations, Springer, 2005, pp. 126-168. See p. 152.
Alejandro Erickson, Frank Ruskey, Mark Schurch and Jennifer Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.
Samuele Giraudo, Pluriassociative algebras I: The pluriassociative operad, Advances in Applied Mathematics, Vol. 77 (2016), pp. 1-42, arXiv preprint, arXiv:1603.01040 [math.CO], 2016.
Frank A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424.
Frank A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)
Frank A. Haight, Letter to N. J. A. Sloane, n.d.
V. E. Hoggatt, Jr., Letter to N. J. A. Sloane, Jul 06, 1976
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=4, q=-4.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 408. (Dead link)
Milan Janjić, Two Enumerative Functions.
Milan Janjić and Boris Petković, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
Milan Janjić and Boris Petković, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5.
C. W. Jones, J. C. P. Miller, J. F. C. Conn, and R. C. Pankhurst, Tables of Chebyshev polynomials, Proc. Roy. Soc. Edinburgh. Sect. A. 62, (1946). 187-203.
Kenji Kimura and Saburo Higuchi, Monte Carlo estimation of the number of tatami tilings, International Journal of Modern Physics C, Vol. 27, No. 11 (2016), 1650128, arXiv preprint, arXiv:1509.05983 [cond-mat.stat-mech], 2015-2016, eq. (1).
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, University of Kentucky Research Reports (2004). (Dead link)
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012.
T. Y. Lam, On the diagonalization of quadratic forms, Math. Mag., 72 (1999), 231-235 (see page 234).
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. See Eq.(3).
Duško Letić, Nenad Cakić, Branko Davidović, Ivana Berković and Eleonora Desnica, Some certain properties of the generalized hypercubical functions, Advances in Difference Equations, 2011, 2011:60.
Toufik Mansour and Armend Sh. Shabani, Bargraphs in bargraphs, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 2763-2773.
Ronald Orozco López, Deformed Differential Calculus on Generalized Fibonacci Polynomials, arXiv:2211.04450 [math.CO], 2022.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Michael Penn, on the alternating sum of subsets, YouTube video, 2021.
Michael Penn, Rare proof of well-known sum, YouTube video, 2023.
Aleksandar Petojević, A Note about the Pochhammer Symbol, Mathematica Moravica, Vol. 12-1 (2008), 37-42.
Maxwell Phillips, Ahmed Ammar, and Firas Hassan, A Generalized Multi-Level Structure for High-Precision Binary Decoders, IEEE 67th Int'l Midwest Symp. Circ. Sys. (MWSCAS 2024), 42-46.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Lara Pudwell, Nathan Chenette and Manda Riehl, Statistics on Hypercube Orientations, AMS Special Session on Experimental and Computer Assisted Mathematics, Joint Mathematics Meetings (Denver 2020).
Lara Pudwell, Connor Scholten, Tyler Schrock and Alexa Serrato, Noncontiguous pattern containment in binary trees, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), chapter 5.2.
Aaron Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. and Theoret. Computer Sci., 3 (1999), 151-154.
Aaron Robertson, Herbert S. Wilf and Doron Zeilberger, Permutation patterns and continued fractions, Electr. J. Combin. 6, 1999, #R38.
Thomas Selig and Haoyue Zhu, Complete non-ambiguous trees and associated permutations: connections through the Abelian sandpile model, arXiv:2303.15756 [math.CO], 2023, see p. 16.
Jeffrey Shallit, Letter to N. J. A. Sloane Mar 14, 1979, concerning A001787, A005209, A005210, A005211.
Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Hypercube.
Eric Weisstein's World of Mathematics, Hypercube Graph.
Eric Weisstein's World of Mathematics, Leibniz Harmonic Triangle.
Eric Weisstein's World of Mathematics, Maximal Clique.
Eric Weisstein's World of Mathematics, Maximum Clique.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,-4).

Three other versions, essentially identical, are A085750, A097067, A118442.
Partial sums of A001792.
A058922(n+1) = 4*A001787(n).
Equals A090802(n, 1).
Column k=1 of A038207.
Row sums of A003506, A322427, A322428.
Cf. A053109, A001788, A001789, A000337, A130300, A134083, A002064, A027471, A003945, A059670, A167591, A059260, A016777, A212697, A000079, A263646.

a001787 n = n * 2 ^ (n - 1)
a001787_list = zipWith (*) [0..] $ 0 : a000079_list
-- Reinhard Zumkeller, Jul 11 2014

[n*2^(n-1): n in [0..40]]; // Vincenzo Librandi, Feb 04 2016

spec := [S, {B=Set(Z, 0 <= card), S=Prod(Z, B, B)}, labeled]: seq(combstruct[count](spec, size=n), n=0..29); # Zerinvary Lajos, Oct 09 2006
A001787:=1/(2*z-1)^2; # Simon Plouffe in his 1992 dissertation, dropping the initial zero

Table[Sum[Binomial[n, i] i, {i, 0, n}], {n, 0, 30}] (* Geoffrey Critzer, Mar 18 2009 *)
f[n_] := n 2^(n - 1); f[Range[0, 40]] (* Vladimir Joseph Stephan Orlovsky, Feb 09 2011 *)
Array[# 2^(# - 1) &, 40, 0] (* Harvey P. Dale, Jul 26 2011 *)
Join[{0}, Table[n 2^(n - 1), {n, 20}]] (* Eric W. Weisstein, Dec 01 2017 *)
Join[{0}, LinearRecurrence[{4, -4}, {1, 4}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)
CoefficientList[Series[x/(-1 + 2 x)^2, {x, 0, 20}], x] (* Eric W. Weisstein, Dec 01 2017 *)

PARI
```
{a(n) = if( n<0, 0, n * 2^(n-1))}
```

concat(0, Vec(x/(1-2*x)^2 + O(x^50))) \\ Altug Alkan, Nov 03 2015

def A001787(n): return n*(1<Chai Wah Wu, Nov 14 2022

a(n) = Sum_{k=1..n} k*binomial(n, k). - Benoit Cloitre, Dec 06 2002
E.g.f.: x*exp(2x). - Paul Barry, Apr 10 2003
G.f.: x/(1-2*x)^2.
G.f.: x / (1 - 4*x / (1 + x / (1 - x))). - Michael Somos, Apr 07 2012
A108666(n) = Sum_{k=0..n} binomial(n, k)^2 * a(n). - Michael Somos, Apr 07 2012
PSumSIGN transform of A053220. PSumSIGN transform is A045883. Binomial transform is A027471(n+1). - Michael Somos, Jul 10 2003
Starting at a(1)=1, INVERT transform is A002450, INVERT transform of A049072, MOBIUS transform of A083413, PSUM transform is A000337, BINOMIAL transform is A081038, BINOMIAL transform of A005408. - Michael Somos, Apr 07 2012
a(n) = 2*a(n-1)+2^(n-1).
a(2*n) = n*4^n, a(2*n+1) = (2*n+1)4^n.
G.f.: x/det(I-x*M) where M=[1,i;i,1], i=sqrt(-1). - Paul Barry, Apr 27 2005
Starting 1, 1, 4, 12, ... this is 0^n + n2^(n-1), the binomial transform of the 'pair-reversed' natural numbers A004442. - Paul Barry, Jul 24 2003
Convolution of [1, 2, 4, 8, ...] with itself. - Jon Perry, Aug 07 2003
The signed version of this sequence, n(-2)^(n-1), is the inverse binomial transform of n(-1)^(n-1) (alternating sign natural numbers). - Paul Barry, Aug 20 2003
a(n-1) = (Sum_{k=0..n} 2^(n-k-1)*C(n-k, k)*C(1,(k+1)/2)*(1-(-1)^k)/2) - 0^n/4. - Paul Barry, Oct 15 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)(n-2k)^2. - Paul Barry, May 13 2005
a(n+2) = A049611(n+2) - A001788(n).
a(n) = n! * Sum_{k=0..n} 1/((k - 1)!(n - k)!). - Paul Barry, Mar 26 2003
a(n+1) = Sum_{k=0..n} 4^k * A109466(n,k). - Philippe Deléham, Nov 13 2006
Row sums of A130300 starting (1, 4, 12, 32, ...). - Gary W. Adamson, May 20 2007
Equals row sums of triangle A134083. Equals A002064(n) + (2^n - 1). - Gary W. Adamson, Oct 07 2007
a(n) = 4*a(n-1) - 4*a(n-2), a(0)=0, a(1)=1. - Philippe Deléham, Nov 16 2008
Sum_{n>0} 1/a(n) = 2*log(2). - Jaume Oliver Lafont, Feb 10 2009
a(n) = A000788(A000225(n)) = A173921(A000225(n)). - Reinhard Zumkeller, Mar 04 2010
a(n) = n * A011782(n). - Omar E. Pol, Aug 28 2013
a(n-1) = Sum_{t_1+2*t_2+...+n*t_n=n} (t_1+t_2+...+t_n-1)*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n). - Mircea Merca, Dec 06 2013
a(n+1) = Sum_{r=0..n} (2*r+1)*C(n,r). - J. M. Bergot, Apr 07 2014
a(n) = A007283(n)*n/6. - Enxhell Luzhnica, Apr 16 2016
a(n) = (A000225(n) + A000337(n))/2. - Anton Zakharov, Sep 17 2016
Sum_{n>0} (-1)^(n+1)/a(n) = 2*log(3/2) = 2*A016578. - Ilya Gutkovskiy, Sep 17 2016
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} (i+1) * C(k,i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = Sum_{i=1..n} Sum_{j=1..n} phi(i)*binomial(n, i*j). - Ridouane Oudra, Feb 17 2024

A000788 Total number of 1's in binary expansions of 0, ..., n.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186

Offset: 0

N. J. A. Sloane

Partial sums of A000120.
The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016
a(n-1) is the largest possible number of ordered pairs (a,b) such that a/b is a prime in a subset of the positive integers with n elements. - Yifan Xie, Feb 21 2025

J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
L. E. Bush, An asymptotic formula for the average sums of the digits of integers, Amer. Math. Monthly, 47 (1940), pp. 154-156. [From the bibliography of Stolarsky, 1977]
P. Cheo and S. Yien, A problem on the k-adic representation of positive integers (Chinese; English summary), Acta Math. Sinica, 5 (1955), pp. 433-438. [From the bibliography of Stolarsky, 1977]
M. P. Drazin and J. S. Griffith, On the decimal representation of integers, Proc. Cambridge Philos. Soc., (4), 48 (1952), pp. 555-565. [From the bibliography of Stolarsky, 1977]
E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
Grabner, P. J.; Kirschenhofer, P.; Prodinger, H.; Tichy, R. F.; On the moments of the sum-of-digits function. Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), 263-271, Kluwer Acad. Publ., Dordrecht, 1993.
R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.
E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.
Donald E. Knuth, The Art of Computer Programming, volume 3 Sorting and Searching, section 5.3.4, subsection Bitonic sorting, with C'(p) = a(p-1).
Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.
I. Shiokawa, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.
Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1000 by T. D. Noe).
G. Agnarsson, On the number of hypercubic bipartitions of an integer, arXiv preprint arXiv:1106.4997 [math.CO], 2011.
G. Agnarsson, Induced subgraphs of hypercubes, arXiv preprint arXiv:1112.3015 [math.CO], 2011.
G. Agnarsson and K. Lauria, Extremal subgraphs of the d-dimensional grid graph, arXiv preprint arXiv:1302.6517 [math.CO], 2013.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Mathias Hauan Arbo, Esten Ingar Grøtli, and Jan Tommy Gravdahl, CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics, arXiv:1901.06713 [cs.RO], 2019.
Venkata Sai Narayana Bavisetty, Matthew Wheeler, Reinhard Laubenbacher, and Claus Kadelka, Upper bound for the stability of Boolean networks, arXiv:2506.12310 [q-bio.MN], 2025. See p. 8.
Johann Cigler, A curious class of Hankel determinants, arXiv:1803.05164 [math.CO], 2018.
G. F. Clements and B. Lindström, A sequence of (+-1) determinants with large values, Proc. Amer. Math. Soc., 16 (1965), pp. 548-550. [From the bibliography of Stolarsky, 1977]
Jean Coquet, Power sums of digital sums, J. Number Theory 22 (1986), no. 2, 161-176.
H. Delange, Sur la fonction sommatoire de la fonction "somme des chiffres", Enseignement Math., (2), 21 (1975), pp. 31-47. [From the bibliography of Stolarsky, 1977]
Laurent Feuilloley, Brief Announcement: Average Complexity for the LOCAL Model, arXiv preprint arXiv:1505.05072 [cs.DC], 2015.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Oscar E. González, An observation of Rankin on Hankel determinants, Department of Mathematics, University of Illinois at Urbana-Champaign, 2018.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is the present sequence).
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36 and 44.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
Raoul Nakhmanson-Kulish, Graphic representation of K(n)=a(n)/(n log2(n)/2) from n=63 to 131071
D. J. Newman, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21 (1969), pp. 719-721. [From the bibliography of Stolarsky, 1977]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
S. C. Tang, An improvement and generalization of Bellman-Shapiro's theorem on a problem in additive number theory, Proc. Amer. Math. Soc., 14 (1963), pp. 199-204. [From the bibliography of Stolarsky, 1977]
Eric Weisstein's World of Mathematics, Binary
David W. Wilson, Fast C++ function for computing a(n)
Index entries for sequences related to binary expansion of n

For number of 0's in binary expansion of 0, ..., n see A059015.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
Cf. A005183, A360189.
Cf. A027868, A037123, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

a000788_list = scanl1 (+) A000120_list
-- Walt Rorie-Baety, Jun 30 2012

{a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
-- Walt Rorie-Baety, Jul 15 2012

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
seq(a(n), n=0..62);  # Alois P. Heinz, Nov 11 2024

a[n_] := Count[ Table[ IntegerDigits[k, 2], {k, 0, n}], 1, 2]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 16 2011 *)
Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)
Accumulate[DigitCount[Range[0,70],2,1]] (* Harvey P. Dale, Jun 08 2013 *)

A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
, n+1 == 1<A000788(n>>1)*2+n>>1+1 \\
, n == 1<A000788(n>>=1)+A000788(n-1)+n )} \\ M. F. Hasler, Nov 22 2009

a(n)=sum(k=1,n,hammingweight(k)) \\ Charles R Greathouse IV, Oct 04 2013

a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r)); \\ Michel Marcus, Mar 27 2018

a(n)={n++; my(t, i, s); c=n; while(c!=0, i++; c\=2); for(j=1, i, d=(n\2^(i-j))%2; t+=(2^(i-j)*(s*d+d*(i-j)/2)); s+=d); t} \\ David A. Corneth, Nov 26 2024
(C++) /* See David W. Wilson link. */

def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # Chai Wah Wu, Mar 01 2023

def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # Chai Wah Wu, Nov 11 2024

McIlroy (1974) gives bounds and recurrences. - N. J. A. Sloane, Mar 24 2014
Stolarsky (1977) studies the asymptotics, and gives at least nine references to earlier work on the problem. I have added all the references that were not here already. - N. J. A. Sloane, Apr 06 2014
a(n) = Sum_{k=1..n} A000120(k). - Benoit Cloitre, Dec 19 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan, Sep 13 2003
a(n) = n*log_2(n)/2 + O(n); a(2^n)=n*2^(n-1)+1. - Benoit Cloitre, Sep 25 2003 (The first result is due to Bellman and Shapiro, - N. J. A. Sloane, Mar 24 2014)
a(n) = n*log_2(n)/2+n*F(log_2(n)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - Ralf Stephan, Apr 19 2003
a(2^n-1) = A001787(n) = n*2^(n-1). - M. F. Hasler, Nov 22 2009
a(4^n-2) = n(4^n-2).
For real n, let f(n) = [n]/2 if [n] even, n-[n+1]/2 otherwise. Then a(n) = Sum_{k>=0} 2^k*f((n+1)/2^k).
a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - Reinhard Zumkeller, Mar 04 2010
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/2^j + 1/2)*(2n + 2 - floor(n/2^j + 1/2))*2^j - floor(n/2^j)*(2n + 2 - (1 + floor(n/2^j)) * 2^j)), where m=floor(log_2(n)).
a(n) = (n+1)*A000120(n) - 2^(m-1) + 1/4 + (1/2)*Sum_{j=1..m+1} ((floor(n/2^j) + 1/2)^2 - floor(n/2^j + 1/2)^2)*2^j, where m=floor(log_2(n)).
a(2^m-1) = m*2^(m-1).
(This is the total number of '1' digits occurring in all the numbers with <= m bits.)
Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/p^j + (p-d)/p)*(2n + 2 + ((p-2*d)/p - floor(n/p^j + (p-d)/p))*p^j) - floor(n/p^j)*(2n + 2 - (1+floor(n/p^j)) * p^j)), where m=floor(log_p(n)).
a(n) = (n+1)*F(n,p,d) + (1/2)*Sum_{j=1..m+1} ((((p-2*d)/p)*floor(n/p^j+(p-d)/p) + floor(n/p^j))*p^j - (floor(n/p^j+(p-d)/p)^2 - floor(n/p^j)^2)*p^j), where m=floor(log_p(n)) and F(n,p,d) = number of digits >= d in the base p representation of n.
a(p^m-1) = (p-d)*m*p^(m-1).
(This is the total number of digits >= d occurring in all the numbers  with <= m digits in base p representation.)
G.f.: g(x) = (1/(1-x)^2)*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - Reinhard Zumkeller, Apr 14 2014
For n > 0, if n is written as 2^m + r with 0 <= r < 2^m, then a(n) = m*2^(m-1) + r + 1 + a(r). - Shreevatsa R, Mar 20 2018
a(n) = n*(n+1)/2 + Sum_{k=1..floor(n/2)} ((2k-1)((g(n,k)-1)*2^(g(n,k) + 1) + 2) - (n+1)*(g(n,k)+1)*g(n,k)/2), where g(n,k) = floor(log_2(n/(2k-1))). - Fabio Visonà, Mar 17 2020
From Jeffrey Shallit, Aug 07 2021: (Start)
A 2-regular sequence, satisfying the identities
a(4n+1) = -a(2n) + a(2n+1) + a(4n)
a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)
a(4n+3) = -4a(n) + 4a(2n+1)
a(8n) = 4a(n) - 8a(2n) + 5a(4n)
a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)
for n>=0. (End)
a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - Alois P. Heinz, Mar 06 2023

More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001

T(n,k) = SUM(bn(i)*bk(L-i-1): 0<=iA070939(n), n=SUM(bn(i)*2^i:0<=i

T(n,2*k+1) = T(n,2*k) + 1;

T(n,k) <= MIN{A000120(n),A000120(k)};

row sums give A173921; central terms give A159780;

T(n,0) = A000004(n);

T(n,1) = A000012(n) for n>0;

T(n,2) = A079944(n-2) for n>1;

T(n,3) = A079882(n-2) for n>2;

T(n,4) = A173922(n-4) for n>3;

T(n,8) = A173923(n-8) for n>7;

T(n,n) = A159780(n).

			T(13,10) = T('1101','1010') = 1*0 + 1*1 + 0*0 + 1*1 = 2;
T(13,11) = T('1101','1011') = 1*1 + 1*1 + 0*0 + 1*1 = 3;
T(13,12) = T('1101','1100') = 1*0 + 1*0 + 0*1 + 1*1 = 1;
T(13,13) = T('1101','1101') = 1*1 + 1*0 + 0*1 + 1*1 = 2.
Triangle begins:
  0;
  0, 1;
  0, 1, 0;
  0, 1, 1, 2;
  0, 1, 0, 1, 0;
  0, 1, 0, 1, 1, 2;
  ...

T[n_, k_] := Module[{bn, bk, lg},
     bn = IntegerDigits[n, 2];
     bk = IntegerDigits[k, 2];
     lg = Max[Length[bn], Length[bk]];
     ListConvolve[PadLeft[bn, lg], PadLeft[bk, lg]]][[1]];
Table[T[n, k], {n, 0, 13}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 19 2021 *)

T(n,k) = c(A030101(n),k,0) with c(x,y,z) = if y=0 then z else c([x/2],[y/2],z+(x mod 2)*(y mod 2)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A001787 a(n) = n*2^(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A000788 Total number of 1's in binary expansions of 0, ..., n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

Extensions

A062709 a(n) = 2^n + 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A173920 Triangle read by rows: T(n,k) = convolution of n with k in binary representation, 0<=k<=n.

Views

Author

Keywords

Comments

Examples