A088567 -id:A088567 - cp's OEIS frontend

A090678 a(n) = A088567(n) mod 2.

1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0

Offset: 0

N. J. A. Sloane, Dec 20 2003

nonn

a(n) = -(-1)^[n/2]*A110036(n)/2 for n>=2, where A110036 gives the partial quotients of the continued fraction expansion of 1 + Sum_{n>=0} 1/x^(2^n). - Paul D. Hanna, Jul 09 2005

O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

b(8m) is (apart from the first term) A038189(m).

Cf. A110036, A110037.

nmax = 104; f = 1 + x/(1 - x) + Sum[x^(3*2^(k - 1))/Product[1 - x^(2^j), {j, 0, k}], {k, 1, Log[2, nmax]}];
a[n_] := Mod[SeriesCoefficient[f, {x, 0, n}], 2];
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Jul 26 2018 *)

{a(n)=(-1)^(n\2)*polcoeff(1+x-x^2*(1+x)/(1+x^2)+ sum(k=1,#binary(n),x^(3*2^(k-1))/prod(j=0,k,1+x^(2^j)+x*O(x^n))),n)} /* Paul D. Hanna */

b(0) == 1; if n is odd, b(n) == b(n-1) + 1; b(8m+2) == 1; b(8m+6) == 0; b(16m+4) == 0; b(16m+12) == 1; for m>0, b(16m) == b(8m), b(32m+8) == 0, b(32m+24) == 1. In other words, for m>0, b(8m) is the value of the bit immediately to the left of the rightmost 1 when m is written in binary.

a(n) = (-1)^floor(n/2)*A110037(n). - Paul D. Hanna, Jul 09 2005

A088585 Bisection of A088567.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 14, 19, 25, 32, 41, 51, 64, 78, 96, 115, 139, 164, 195, 227, 267, 308, 358, 409, 472, 536, 613, 691, 786, 882, 996, 1111, 1249, 1388, 1551, 1715, 1909, 2104, 2330, 2557, 2823, 3090, 3397, 3705, 4062, 4420, 4828, 5237, 5708, 6180, 6715, 7251, 7863

Offset: 0

N. J. A. Sloane, Nov 30 2003

nonn

Also partials sums of A088567. - Philippe Deléham, Aug 20 2006

Cf. A088567, A088575.

a(n) = A088575(n) + 1 for n>=1.

A089013 a(n) = (A088567(8n) mod 2).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1

Offset: 0

N. J. A. Sloane, Dec 20 2003

This is just to give a pointer to A088567, A089013 and A014707.

N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.
Index entries for sequences obtained by enumerating foldings

A038189(n)=a(n) if n>0.

a(0) = 1, a(2*n) = a(n) for n > 0 and a(2*n+1) = (n mod 2) for n >= 0. - A.H.M. Smeets, Aug 02 2018

A088575 Bisection of A088567.

Original entry on oeis.org

1, 1, 2, 4, 6, 9, 13, 18, 24, 31, 40, 50, 63, 77, 95, 114, 138, 163, 194, 226, 266, 307, 357, 408, 471, 535, 612, 690, 785, 881, 995, 1110, 1248, 1387, 1550, 1714, 1908, 2103, 2329, 2556, 2822, 3089, 3396, 3704, 4061, 4419, 4827, 5236, 5707, 6179, 6714, 7250, 7862

Offset: 0

N. J. A. Sloane, Nov 30 2003

nonn

(1 + x^2 + x^3 + x^4 + x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + ...) = (1 + x + 2x^2 + 4x^3 + 6x^4 + ...). - Gary W. Adamson, Jul 27 2010

Cf. A088567, A088585.

a(n) = A088585(n) - 1 for n >= 1.

a(n) = a(n-1) + a(floor(n/2)) + (1-(-1)^n)/2, n > 1. - Vladeta Jovovic, Dec 02 2003

A110037 Signed version of A090678 and congruent to A088567 mod 2.

Original entry on oeis.org

1, 1, -1, 0, 0, 1, 0, -1, 0, 1, -1, 0, 1, 0, 0, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, 0, -1, 0, 1, 0, 0, -1, 0, 1, -1, 0, 0, 1, 0, -1, 0, 1, -1, 0, 1, 0, 0, -1, 1, 0, -1, 0, 0, 1, 0, -1, 1, 0, -1, 0, 1, 0, 0, -1, 0, 1, -1, 0, 0, 1, 0, -1, 0, 1, -1, 0, 1, 0, 0, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, 0, -1, 0, 1, 0, 0, -1, 1, 0, -1, 0, 0, 1, 0, -1, 0

Offset: 0

Paul D. Hanna, Jul 09 2005

a(n) = (-1)^[n/2]*A090678(n) = A088567(n) mod 2, where A088567(n) equals the number of "non-squashing" partitions of n. a(n) = -A110036(n)/2 for n>=2, where the A110036 gives the partial quotients of the continued fraction expansion of 1 + Sum_{n>=0} 1/x^(2^n).

Cf. A110036, A090678, A088567, A073089.

{a(n)=polcoeff(A=1+x-x^2*(1+x)/(1+x^2)+ sum(k=1,#binary(n),x^(3*2^(k-1))/prod(j=0,k,1+x^(2^j)+x*O(x^n))),n)}

G.f.: A(x) = 1+x - x^2*(1+x)/(1+x^2) + Sum_{k>=1} x^(3*2^(k-1))/Product_{j=0..k} (1+x^(2^j)).

Conjecture: a(n) = A073089(n) - A073089(n+1) for n >= 2. - Alan Michael Gómez Calderón, Aug 19 2025

A018819 Binary partition function: number of partitions of n into powers of 2.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294

Offset: 0

David W. Wilson, N. J. A. Sloane and J. H. Conway

First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.
Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.
Euler transform of A036987 with offset 1.
a(n) is the number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003
Normally the OEIS does not include sequences like this where every term is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.
Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g., a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket; e.g., this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004
Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007
Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008
Appears to be row sums of A155077. - Mats Granvik, Jan 19 2009
Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as nonincreasing lists).
Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. - Gary W. Adamson, Nov 21 2009
Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - Gary W. Adamson, Dec 05 2009
Let B = the n-th convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...). - Gary W. Adamson, Aug 15 2016
From Gary W. Adamson, Sep 08 2016: (Start)
The limit of the matrix power M^k as n-->inf results in a single column vector equal to the sequence, where M is the following production matrix:
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ... (End)
a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - David V. Feldman, Jan 29 2020
From Gus Wiseman, May 25 2024: (Start)
Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:
  {1}  {2}   {12}   {3}     {13}     {23}      {123}      {4}
       {11}  {111}  {22}    {122}    {113}     {1113}     {33}
                    {112}   {1112}   {222}     {1222}     {223}
                    {1111}  {11111}  {1122}    {11122}    {1123}
                                     {11112}   {111112}   {2222}
                                     {111111}  {1111111}  {11113}
                                                          {11222}
                                                          {111122}
                                                          {1111112}
                                                          {11111111}
(End)

			G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + ...
a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
a(7) = 6: the partitions are 4 + 2 + 1, 4 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.
From _Joerg Arndt_, Dec 17 2012: (Start)
The a(10) = 14 binary partitions of 10 are (in lexicographic order)
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 1 1 1 ]
[ 3]  [ 2 2 1 1 1 1 1 1 ]
[ 4]  [ 2 2 2 1 1 1 1 ]
[ 5]  [ 2 2 2 2 1 1 ]
[ 6]  [ 2 2 2 2 2 ]
[ 7]  [ 4 1 1 1 1 1 1 ]
[ 8]  [ 4 2 1 1 1 1 ]
[ 9]  [ 4 2 2 1 1 ]
[10]  [ 4 2 2 2 ]
[11]  [ 4 4 1 1 ]
[12]  [ 4 4 2 ]
[13]  [ 8 1 1 ]
[14]  [ 8 2 ]
The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.
The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)
[ 1]  [ 6 3 1 1 ]
[ 2]  [ 6 3 2 ]
[ 3]  [ 6 4 1 ]
[ 4]  [ 6 5 ]
[ 5]  [ 7 2 1 1 ]
[ 6]  [ 7 2 2 ]
[ 7]  [ 7 3 1 ]
[ 8]  [ 7 4 ]
[ 9]  [ 8 2 1 ]
[10]  [ 8 3 ]
[11]  [ 9 1 1 ]
[12]  [ 9 2 ]
[13]  [ 10 1 ]
[14]  [ 11 ]
The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _David V. Feldman_, Jan 29 2020: (Start)
The a(10) = 14 non-borrowing partitions of 10 are (in lexicographic order)
[ 1] [1 1 1 1 1 1 1 1 1 1]
[ 2] [2 2 2 2 2]
[ 3] [3 1 1 1 1 1 1 1]
[ 4] [3 3 1 1 1 1]
[ 5] [3 3 2 2]
[ 6] [3 3 3 1]
[ 7] [5 1 1 1 1 1]
[ 8] [5 5]
[ 9] [6 2 2]
[10] [6 4]
[11] [7 1 1 1]
[12] [7 3]
[13] [9 1]
[14] [10]
The a(11) = 14 non-borrowing partitions of 11 are obtained either by adding 1 to the first even part in each partition (if any) or else appending a 1 after the last part.
(End)
For example, the five partitions of 4, written in nonincreasing order, are [1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]. The last four satisfy the condition, and a(4) = 4. The Maple program below verifies this for small values of n.

T. D. Noe, Table of n, a(n) for n = 0..1000
Max Alekseyev and Franklin T. Adams-Watters, Two proofs of an observation of Vladeta Jovovic
Giedrius Alkauskas, Generalization of the Rodseth-Gupta theorem on binary partitions, Lithuanian Math. J., 43 (2) (2003), 103-110.
Giedrius Alkauskas, Congruence Properties of the Function that Counts Compositions into Powers of 2 , J. Int. Seq. 13 (2010), 10.5.3.
Joerg Arndt, Matters Computational (The Fxtbook), section 38.1, p.729.
Scott M. Bailey and Donald M. Larson, The A(1)-module structure of the homology of Brown-Gitler spectra, arXiv:2107.01316 [math.AT], 2021.
Valentin P. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp. 17-41.
Philippe Biane, Laver tables and combinatorics, arXiv:1810.00548 [math.CO], 2018. Mentions this sequence.
Peter J. Cameron, Firdous Ee Jannat, Rajat Kanti Nath, and Reza Sharafdini, A survey on conjugacy class graphs of groups, arXiv:2403.09423 [math.GR], 2024.
Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 48, 581.
Maciej Gawron, Piotr Miska and Maciej Ulas, Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t, arXiv:1703.01955 [math.NT], 2017.
Michael D. Hirschhorn and James A. Sellers, A different view of m-ary partitions, Australasian J. Combin., vol.30 (2004), 193-196.
Jonathan Jordan and Richard Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. doi: 10.4236/am.2010.15045. - From _N. J. A. Sloane_, Feb 03 2013
Yasuyuki Kachi and Pavlos Tzermias, On the m-ary partition numbers, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.
Matjaž Konvalinka and Igor Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91; see also DOI link. - From _N. J. A. Sloane_, Dec 22 2012
Apisit Pakapongpun and Thomas Ward, Functorial Orbit counting, J. Int. Seq., 12 (2009) 09.2.4, example 25.
Øystein J. Rodseth and James A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
David Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

A000123 is the main entry for the binary partition function and gives many more properties and references.
Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).
Convolution inverse of A106400.
Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.
Multiplicity of n in A048675, for distinct prime indices A087207.
Row lengths of A277905.
A118462 lists binary ranks of strict integer partitions, row sums A372888.
A372890 adds up binary ranks of integer partitions.
Binary indices: A000120, A001511, A029931, A048793, A070939, A272020.
Cf. A005940, A019565, A056239, A158704, A158705, A231204, A277319, A372688.

a018819 n = a018819_list !! n
a018819_list = 1 : f (tail a008619_list) where
   f (x:xs) = (sum $ take x a018819_list) : f xs
-- Reinhard Zumkeller, Jan 28 2012

import Data.List (intersperse)
a018819 = (a018819_list !!)
a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
-- Johan Wiltink, Nov 08 2018

with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
# while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od; # John McKay

max = 59; a[0] = a[1] = 1; a[n_?OddQ] := a[n] = a[n-1]; a[n_?EvenQ] := a[n] = a[n-1] + a[n/2]; Table[a[n], {n, 0, max}]
(* or *) CoefficientList[Series[1/Product[(1-x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* Jean-François Alcover, May 17 2011, updated Feb 17 2014 *)
a[ n_] := If[n<1, Boole[n==0], a[n] = a[n-1] + If[EvenQ@n, a[Quotient[n,2]], 0]]; (* Michael Somos, May 04 2022 *)
Table[Count[IntegerPartitions[n],?(AllTrue[Log2[#],IntegerQ]&)],{n,0,60}] (* _Harvey P. Dale, Jun 20 2024 *)

{ n=15; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*2)); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } /* Jon Perry */

{a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while(m<=n, m*=2; A = subst(A, x, x^2) / (1 - x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */

{a(n) = if( n<1, n==0, if( n%2, a(n-1), a(n/2)+a(n-1)))}; /* Michael Somos, Aug 25 2003 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A018819(n): return 1 if n == 0 else A018819(n-1) + (0 if n % 2 else A018819(n//2)) # Chai Wah Wu, Jan 18 2022

a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m). Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.
G.f.: 1 / Product_{j>=0} (1-x^(2^j)).
a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002
a(2*n) = a(2*n + 1) = A000123(n). - Michael Somos, Aug 25 2003
a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0. - David W. Wilson, Aug 16 2007
G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - Michael Somos, Aug 25 2003
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = u^2*w - 2*u*v^2 + v^3. - Michael Somos, Apr 10 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6 * u1^3 - 3*u3*u2*u1^2 + 3*u3*u2^2*u1 - u3*u2^3. - Michael Somos, Oct 15 2006
G.f.: 1/( Sum_{n >= 0} x^evil(n) - x^odious(n) ), where evil(n) = A001969(n) and odious(n) = A000069(n). - Paul D. Hanna, Jan 23 2012
Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k, see fxtbook link. - Joerg Arndt, Dec 17 2012
G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link. - Joerg Arndt, Feb 28 2014
G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1 - x^(2^j)). - Ilya Gutkovskiy, May 07 2017

A040039 First differences of A033485; also A033485 with terms repeated.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, 70, 70, 83, 83, 101, 101, 119, 119, 142, 142, 165, 165, 195, 195, 225, 225, 262, 262, 299, 299, 346, 346, 393, 393, 450, 450, 507, 507, 577, 577, 647, 647, 730, 730, 813, 813, 914, 914, 1015, 1015, 1134, 1134, 1253, 1253, 1395, 1395

Offset: 0

N. J. A. Sloane and J. H. Conway

Apparently a(n) = number of partitions (p_1, p_2, ..., p_k) of n+1, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i > p_{i+1}+...+p_k. - John McKay (mac(AT)mathstat.concordia.ca), Mar 06 2009
Comment from John McKay confirmed in paper by Bessenrodt, Olsson, and Sellers. Such partitions are called "strongly decreasing" partitions in the paper, see the function s(n) therein.
Also the number of unlabeled binary rooted trees with 2*n + 3 nodes in which the two branches directly under any given non-leaf node are either equal or at least one of them is a leaf. - Gus Wiseman, Oct 08 2018
From Gus Wiseman, Apr 06 2021: (Start)
This sequence counts both of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n + 1 in which all adjacent elements have quotients < 1/2. For example, the a(0) = 1 through a(8) = 7 subsets are:
  {1}  {2}  {3}    {4}    {5}    {6}    {7}      {8}      {9}
            {1,3}  {1,4}  {1,5}  {1,6}  {1,7}    {1,8}    {1,9}
                          {2,5}  {2,6}  {2,7}    {2,8}    {2,9}
                                        {3,7}    {3,8}    {3,9}
                                        {1,3,7}  {1,3,8}  {4,9}
                                                          {1,3,9}
                                                          {1,4,9}
2. Sets of distinct positive integers with maximum n + 1 whose first differences are term-wise greater than their decapitation (remove the maximum). For example, the set q = {1,4,9} has first differences (3,5), which are greater than (1,4), so q is counted under a(8). On the other hand, r = {1,5,9} has first differences (4,4), which are not greater than (1,5), so r is not counted under a(8).
Also the number of partitions of n + 1 into powers of 2 covering an initial interval of powers of 2. For example, the a(0) = 1 through a(8) = 7 partitions are:
  1  11  21   211   221    2211    421      4211      4221
         111  1111  2111   21111   2221     22211     22221
                    11111  111111  22111    221111    42111
                                   211111   2111111   222111
                                   1111111  11111111  2211111
                                                      21111111
                                                      111111111
(End)

			From _Joerg Arndt_, Dec 17 2012: (Start)
The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
[ 1]    [ 10 5 3 1 ]
[ 2]    [ 10 5 4 ]
[ 3]    [ 10 6 2 1 ]
[ 4]    [ 10 6 3 ]
[ 5]    [ 10 7 2 ]
[ 6]    [ 10 8 1 ]
[ 7]    [ 10 9 ]
[ 8]    [ 11 5 2 1 ]
[ 9]    [ 11 5 3 ]
[10]    [ 11 6 2 ]
[11]    [ 11 7 1 ]
[12]    [ 11 8 ]
[13]    [ 12 4 2 1 ]
[14]    [ 12 4 3 ]
[15]    [ 12 5 2 ]
[16]    [ 12 6 1 ]
[17]    [ 12 7 ]
[18]    [ 13 4 2 ]
[19]    [ 13 5 1 ]
[20]    [ 13 6 ]
[21]    [ 14 3 2 ]
[22]    [ 14 4 1 ]
[23]    [ 14 5 ]
[24]    [ 15 3 1 ]
[25]    [ 15 4 ]
[26]    [ 16 2 1 ]
[27]    [ 16 3 ]
[28]    [ 17 2 ]
[29]    [ 18 1 ]
[30]    [ 19 ]
The a(20-1)=30 strongly decreasing partitions of 20 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _Gus Wiseman_, Oct 08 2018: (Start)
The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
  o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
                    (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
                                               (o(o(o(o(oo)))))
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..500 from Joerg Arndt)
Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A000123.
Cf. A088567, A089054.
Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.
The equal case is A001511.
The reflected version is A045690.
The unequal (anti-run) version is A045691.
A000929 counts partitions with all adjacent parts x >= 2y.
A002843 counts compositions with all adjacent parts x <= 2y.
A018819 counts partitions into powers of 2.
A154402 counts partitions with all adjacent parts x = 2y.
A274199 counts compositions with all adjacent parts x < 2y.
A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).
A342096 counts partitions without adjacent x >= 2y (strict: A342097).
A342098 counts partitions with all adjacent parts x > 2y.
A342337 counts partitions with all adjacent parts x = y or x = 2y.
Cf. A000009, A003114, A003242, A224957, A342191, A342330.

# For example, the five partitions of 4, written in nonincreasing order, are
# [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
# Only the last two satisfy the condition, and a(3)=2.
# The Maple program below verifies this for small values of n.
with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
#while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od;
# John McKay

T[n_, m_] := T[n, m] = Sum[Binomial[n-2k-1, n-2k-m] Sum[Binomial[m, i] T[k, i], {i, 1, k}], {k, 0, (n-m)/2}] + Binomial[n-1, n-m];
a[n_] := T[n+1, 1];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]<1/2,{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Apr 06 2021 *)

T(n,m):=sum(binomial(n-2*k-1,n-2*k-m)*sum(binomial(m,i)*T(k,i),i,1,k),k,0,(n-m)/2)+binomial(n-1,n-m);
makelist(T(n+1,1),n,0,40); /* Vladimir Kruchinin, Mar 19 2015 */

/* compute as "A033485 with terms repeated" */
b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
a(n) = b(n\2+1); /* note different offsets */
for(n=0,99, print1(a(n),", ")); /* Joerg Arndt, Jan 21 2011 */

from itertools import islice
from collections import deque
def A040039_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 1, 2, 2)
    while True:
        a += b
        yield from (a, a)
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A040039_list = list(islice(A040039_gen(),40)) # Chai Wah Wu, Jun 07 2022

Let T(x) be the g.f, then T(x) = 1 + x/(1-x)*T(x^2) = 1 + x/(1-x) * ( 1 + x^2/(1-x^2) * ( 1 + x^4/(1-x^4) * ( 1 + x^8/(1-x^8) *(...) ))). [Joerg Arndt, May 11 2010]
From Joerg Arndt, Oct 02 2013: (Start)
G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].
G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).
a(n) = 1/2 * A018819(n+2).
(End)
a(n) = T(n+1,1), where T(n,m)=sum(k..0,(n-m)/2, binomial(n-2*k-1,n-2*k-m)*sum(i=1..k, binomial(m,i)*T(k,i)))+binomial(n-1,n-m). - Vladimir Kruchinin, Mar 19 2015
Using offset 1: a(1) = 1; a(n even) = a(n-1); a(n odd) = a(n-1) + a((n-1)/2). - Gus Wiseman, Oct 08 2018

A089054 Solution to the non-squashing boxes problem (version 1).

Original entry on oeis.org

1, 2, 4, 8, 14, 23, 36, 54, 78, 109, 149, 199, 262, 339, 434, 548, 686, 849, 1043, 1269, 1535, 1842, 2199, 2607, 3078, 3613, 4225, 4915, 5700, 6581, 7576, 8686, 9934, 11321, 12871, 14585, 16493, 18596, 20925, 23481, 26303, 29392, 32788, 36492, 40553, 44972, 49799

Offset: 0

N. J. A. Sloane, Dec 04 2003

nonn

Given n boxes labeled 1..n, such that box i weighs i grams and can support a total weight of i grams; a(n) = number of stacks of boxes that can be formed such that no box is squashed.

Amanda Folsom, Youkow Homma, Jun Hwan Ryu, and Benjamin Tong, On a general class of non-squashing partitions, Discrete Mathematics 339 (2016) 1482-1506.
Oystein J. Rodseth, Sloane's box stacking problem, Discrete Math. 306 (2006), no. 16, 2005-2009.
Øystein J. Rødseth and James A. Sellers, Congruences modulo high powers of 2 for Sloane's box stacking function, Australasian Journal of Combinatorics, Volume 44 (2009), Pages 255-263.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003; Discrete Math., 294 (2005), 259-274.

Cf. A000123, A088567, A089055, A090631, A090632. Row sums of A090641.

max = 50; B[x_] = 1+x/(1-x) + Sum[x^(3 2^(k-1))/Product[(1-x^(2^j)), {j, 0, k}], {k, 1, Log[2, max]}] + O[x]^max;
A[x_] = (B[x]-x)/(1-x)^2;
CoefficientList[A[x], x] (* Jean-François Alcover, Sep 01 2018 *)

G.f.: (B(x)-x)/(1-x)^2, where B(x) = g.f. for A088567.

A187821 Number of non-squashing partitions of n into odd parts.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 3, 4, 5, 6, 5, 6, 7, 9, 7, 9, 11, 12, 11, 12, 15, 17, 15, 17, 21, 22, 21, 22, 27, 29, 27, 29, 36, 36, 36, 36, 45, 47, 45, 47, 57, 58, 57, 58, 69, 73, 69, 73, 86, 88, 86, 88, 103, 109, 103, 109, 125, 130, 125, 130, 147, 157, 147, 157, 176, 184, 176, 184, 205, 220, 205, 220, 241, 256, 241, 256

Offset: 0

Joerg Arndt, Dec 27 2012

nonn

A non-squashing partition of n is a partition p(1) + p(2) + ... + p(m) = n such that p(k) >= sum(j=k+1..m, p(j) ).

			The a(33) = a(35) = 27 non-squashing partitions of 33 and 35 into odd parts are
[ 1]   [ 17 9 5 1 1 ]       [ 1]   [ 19 9 5 1 1 ]
[ 2]   [ 17 9 7 ]           [ 2]   [ 19 9 7 ]
[ 3]   [ 17 11 3 1 1 ]      [ 3]   [ 19 11 3 1 1 ]
[ 4]   [ 17 11 5 ]          [ 4]   [ 19 11 5 ]
[ 5]   [ 17 13 3 ]          [ 5]   [ 19 13 3 ]
[ 6]   [ 17 15 1 ]          [ 6]   [ 19 15 1 ]
[ 7]   [ 19 7 5 1 1 ]       [ 7]   [ 21 7 5 1 1 ]
[ 8]   [ 19 7 7 ]           [ 8]   [ 21 7 7 ]
[ 9]   [ 19 9 3 1 1 ]       [ 9]   [ 21 9 3 1 1 ]
[10]   [ 19 9 5 ]           [10]   [ 21 9 5 ]
[11]   [ 19 11 3 ]          [11]   [ 21 11 3 ]
[12]   [ 19 13 1 ]          [12]   [ 21 13 1 ]
[13]   [ 21 7 3 1 1 ]       [13]   [ 23 7 3 1 1 ]
[14]   [ 21 7 5 ]           [14]   [ 23 7 5 ]
[15]   [ 21 9 3 ]           [15]   [ 23 9 3 ]
[16]   [ 21 11 1 ]          [16]   [ 23 11 1 ]
[17]   [ 23 5 3 1 1 ]       [17]   [ 25 5 3 1 1 ]
[18]   [ 23 5 5 ]           [18]   [ 25 5 5 ]
[19]   [ 23 7 3 ]           [19]   [ 25 7 3 ]
[20]   [ 23 9 1 ]           [20]   [ 25 9 1 ]
[21]   [ 25 5 3 ]           [21]   [ 27 5 3 ]
[22]   [ 25 7 1 ]           [22]   [ 27 7 1 ]
[23]   [ 27 3 3 ]           [23]   [ 29 3 3 ]
[24]   [ 27 5 1 ]           [24]   [ 29 5 1 ]
[25]   [ 29 3 1 ]           [25]   [ 31 3 1 ]
[26]   [ 31 1 1 ]           [26]   [ 33 1 1 ]
[27]   [ 33 ]               [27]   [ 35 ]

Joerg Arndt, Table of n, a(n) for n = 0..1000

Cf. A018819 and A000123 (non-squashing partitions, also binary partitions).

Cf. A088567 (non-squashing partitions into distinct parts)

A088931 G.f.: Sum_{n >= 1} ( x^(2^n)/ ((1+x^(2^(n-1)))*Product_{j=0..n-1} (1-x^(2^j)) ) ).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 2, 1, 4, 3, 5, 4, 7, 6, 8, 7, 12, 11, 15, 14, 20, 19, 24, 23, 31, 30, 37, 36, 45, 44, 52, 51, 64, 63, 75, 74, 90, 89, 104, 103, 124, 123, 143, 142, 167, 166, 190, 189, 221, 220, 251, 250, 288, 287, 324, 323, 369, 368, 413, 412, 465, 464, 516, 515, 580

Offset: 0

N. J. A. Sloane, Dec 02 2003

nonn

This is the g.f. for the number of non-squashing partitions with a repeated part, that is, A000123(n) - A088567(n).

			x^2/((1 + x)*(1 - x)) + x^4/((1 + x^2)*(1 - x)*(1 - x^2)) + x^8/((1 + x^4)*(1 - x)*(1 - x^2)*(1 - x^4)) + ...

N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

Apart from initial terms, same as A088980.

max = 65; Sum[x^(2^n)/((1+x^(2^(n-1))) Product[1-x^(2^j), {j, 0, n-1}]), {n, 1, Log[2, max] // Ceiling}] + O[x]^(max) // CoefficientList[#, x]& (* Jean-François Alcover, Oct 05 2018 *)

cp's OEIS Frontend

A090678 a(n) = A088567(n) mod 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A088585 Bisection of A088567.

Views

Author

Keywords

Comments

Crossrefs

Formula

A089013 a(n) = (A088567(8n) mod 2).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A088575 Bisection of A088567.

Views

Author

Keywords

Comments

Crossrefs

Formula

A110037 Signed version of A090678 and congruent to A088567 mod 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A018819 Binary partition function: number of partitions of n into powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A040039 First differences of A033485; also A033485 with terms repeated.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Python

Formula

A089054 Solution to the non-squashing boxes problem (version 1).

Views

Author

Keywords