A088932 -id:A088932 - cp's OEIS frontend

A181322 Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) is the number of partitions of 2*n into powers of 2 less than or equal to 2^k.

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 4, 1, 1, 2, 4, 6, 5, 1, 1, 2, 4, 6, 9, 6, 1, 1, 2, 4, 6, 10, 12, 7, 1, 1, 2, 4, 6, 10, 14, 16, 8, 1, 1, 2, 4, 6, 10, 14, 20, 20, 9, 1, 1, 2, 4, 6, 10, 14, 20, 26, 25, 10, 1, 1, 2, 4, 6, 10, 14, 20, 26, 35, 30, 11, 1, 1, 2, 4, 6, 10, 14, 20, 26, 36, 44, 36, 12, 1, 1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 56, 42, 13, 1

Offset: 0

Alois P. Heinz, Jan 26 2011

Column sequences converge towards A000123.

			A(3,2) = 6, because there are 6 partitions of 2*3=6 into powers of 2 less than or equal to 2^2=4: [4,2], [4,1,1], [2,2,2], [2,2,1,1], [2,1,1,1,1], [1,1,1,1,1,1].
Square array A(n,k) begins:
  1,  1,  1,  1,  1,  1,  ...
  1,  2,  2,  2,  2,  2,  ...
  1,  3,  4,  4,  4,  4,  ...
  1,  4,  6,  6,  6,  6,  ...
  1,  5,  9, 10, 10, 10,  ...
  1,  6, 12, 14, 14, 14,  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
G. Blom and C.-E. Froeberg, Om myntvaexling (On money-changing) [Swedish], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103. [Annotated scanned copy] See Table 4.

Columns k=0-5 give: A000012, A000027(n+1), A002620(n+2), A008804, A088932, A088954.
Main diagonal gives A000123.
Cf. A145515.
See A262553 for another version of this array.
See A072170 for a related array (having the same limiting column).

b:= proc(n, j) local nn, r;
      if n<0 then 0
    elif j=0 then 1
    elif j=1 then n+1
    elif n b(n/2^(k-1), k):
seq(seq(A(n, d-n), n=0..d), d=0..13);

b[n_, j_] := b[n, j] = Module[{nn, r}, Which[n<0, 0, j == 0, 1, j == 1, n+1, nJean-François Alcover, Jan 15 2014, translated from Maple *)

A181322(n,k,r=1)={if(nA181322(n-1,k,0)+A181322(2*n,k-1,0),n-=r=1+n\1,(r-k)*binomial(r,k)*sum(i=0,min(k-1,k+n), binomial(k,i)/(r-k+i)*A181322(k-i+n,k,0) *(-1)^i))} \\ From Maple. - M. F. Hasler, Feb 19 2019

G.f. of column k: 1/(1-x) * 1/Product_{j=0..k-1} (1 - x^(2^j)).
A(n,k) = Sum_{i=0..k} A089177(n,i).
For n < 2^k, T(n,k) = A000123(k). T(n,0) = 1, T(n,1) = n+1. - M. F. Hasler, Feb 19 2019

A089177 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n))) giving number of non-squashing partitions of n into k parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 4, 4, 1, 1, 5, 6, 2, 1, 6, 9, 4, 1, 7, 12, 6, 1, 8, 16, 10, 1, 1, 9, 20, 14, 2, 1, 10, 25, 20, 4, 1, 11, 30, 26, 6, 1, 12, 36, 35, 10, 1, 13, 42, 44, 14, 1, 14, 49, 56, 20, 1, 15, 56, 68, 26, 1, 16, 64, 84, 36, 1, 1, 17, 72, 100, 46, 2, 1, 18, 81, 120, 60, 4, 1

Offset: 0

N. J. A. Sloane, Dec 08 2003

T(n,k) = A181322(n,k) - A181322(n,k-1) for n>0. - Alois P. Heinz, Jan 25 2014

			Triangle begins:
  1;
  1, 1;
  1, 2,  1;
  1, 3,  2;
  1, 4,  4,  1;
  1, 5,  6,  2;
  1, 6,  9,  4;
  1, 7, 12,  6;
  1, 8, 16, 10,  1;

Alois P. Heinz, Rows n = 0..1002, flattened
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. A078121, A089178. Columns give A002620, A008804, A088932, A088954. Row sums give A000123.

T:= proc(n) option remember;
     `if`(n=0, 1, zip((x, y)-> x+y, [T(n-1)], [0, T(floor(n/2))], 0)[])
    end:
seq(T(n), n=0..25);  # Alois P. Heinz, Apr 01 2012

row[0] = {1}; row[1] = {1, 1}; row[n_] := row[n] = Plus @@ PadRight[ {row[n-1], Join[{0}, row[Floor[n/2]]]} ]; Table[row[n], {n, 0, 25}] // Flatten (* Jean-François Alcover, Jan 31 2014 *)

Row 0 = {1}, row 1 = {1 1}; for n >=2, row n = row n-1 + (row floor(n/2) shifted one place right).
G.f. for column k (k >= 2): x^(2^(k-2))/((1-x)*Product_{j=0..k-2} (1-x^(2^j))). [corrected by Jason Yuen, Jan 12 2025]
Conjecture: let R(n,x) be the n-th reversed row polynomial, then R(n,x) = Sum_{k=0..A000523(A053645(n)) + 1} T(A053645(n),k)*R(2^(A000523(n)-k),x) for n > 0, n != 2^m with R(0,x) = 1 where R(2^m,x) is the (m+1)-th row polynomial of A078121. - Mikhail Kurkov, Jun 28 2025

More terms from Alford Arnold, May 22 2004

A088954 G.f.: 1/((1-x)^2(1-x^2)(1-x^4)(1-x^8)(1-x^16)).

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 202, 238, 284, 330, 390, 450, 524, 598, 692, 786, 900, 1014, 1154, 1294, 1460, 1626, 1827, 2028, 2264, 2500, 2780, 3060, 3384, 3708, 4088, 4468, 4904, 5340, 5844, 6348, 6920, 7492, 8148, 8804, 9544

Offset: 0

N. J. A. Sloane, Dec 02 2003

nonn

a(n) is the number of partitions of 2*n into powers of 2 less than or equal to 2^5. First differs from A000123 at n=32. - Alois P. Heinz, Apr 02 2012

Alois P. Heinz, Table of n, a(n) for n = 0..2000
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.
Index entries for linear recurrences with constant coefficients, signature (2, 0, -2, 2, -2, 0, 2, 0, -2, 0, 2, -2, 2, 0, -2, 2, -2, 0, 2, -2, 2, 0, -2, 0, 2, 0, -2, 2, -2, 0, 2, -1).

See A000027, A002620, A008804, A088932, A000123 for similar sequences.

Column k=5 of A181322.

f := proc(n,k) option remember; if k > n then RETURN(0); fi; if k= 0 then if n=0 then RETURN(1) else RETURN(0); fi; fi; if k = 1 then RETURN(1); fi; if n mod 2 = 1 then RETURN(f(n-1,k)); fi; f(n-1,k)+f(n/2,k-1); end; # present sequence is f(2m,6)
GFF := k->x^(2^(k-2))/((1-x)*mul((1-x^(2^j)),j=0..k-2)); # present g.f. is GFF(6)/x^16
a:= proc(n) local m, r; m:= iquo(n, 16, 'r'); r:= r+1; [1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166][r] +(((((128/5*m +8*(15+r))*m +(228 +[0, 32, 68, 104, 144, 184, 228, 272, 320, 368, 420, 472, 528, 584, 644, 704][r]))*m +(172 +[0, 43, 98, 153, 223, 293, 378, 463, 566, 669, 790, 911, 1053, 1195, 1358, 1521][r]))*m +(247/5 +[0, 22, 55, 88, 138, 188, 255, 322, 415, 508, 627, 746, 900, 1054, 1243, 1432][r]))*m)/3 end: seq(a(n), n=0..60); # Alois P. Heinz, Apr 17 2009

CoefficientList[Series[1/((1-x)^2(1-x^2)(1-x^4)(1-x^8)(1-x^16)),{x,0,70}],x] (* or *) LinearRecurrence[{2,0,-2,2,-2,0,2,0,-2,0,2,-2,2,0,-2,2,-2,0,2,-2,2,0,-2,0,2,0,-2,2,-2,0,2,-1},{1,2,4,6,10,14,20,26,36,46,60,74,94,114,140,166,202,238,284,330,390,450,524,598,692,786,900,1014,1154,1294,1460,1626},70](* Harvey P. Dale, Feb 12 2013 *)

a(0)=1, a(1)=2, a(2)=4, a(3)=6, a(4)=10, a(5)=14, a(6)=20, a(7)=26, a(8)=36, a(9)=46, a(10)=60, a(11)=74, a(12)=94, a(13)=114, a(14)=140, a(15)=166, a(16)=202, a(17)=238, a(18)=284, a(19)=330, a(20)=390, a(21)=450, a(22)=524, a(23)=598, a(24)=692, a(25)=786, a(26)=900, a(27)=1014, a(28)=1154, a(29)=1294, a(30)=1460, a(31)=1626, a(n)=2*a(n-1)-2*a(n-3)+ 2*a(n-4)- 2*a(n-5)+ 2*a(n-7)-2*a(n-9)+2*a(n-11)-2*a(n-12)+2*a(n-13)-2*a(n-15)+2*a(n-16)-2*a(n-17)+ 2*a(n-19)- 2*a(n-20)+ 2*a(n-21)-2*a(n-23)+2*a(n-25)-2*a(n-27)+2*a(n-28)-2*a(n-29)+ 2*a(n-31)-a(n-32). - Harvey P. Dale, Feb 12 2013

A008643 Molien series for group of 4 X 4 upper triangular matrices over GF(2).

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 35, 35, 44, 44, 56, 56, 68, 68, 84, 84, 100, 100, 120, 120, 140, 140, 165, 165, 190, 190, 220, 220, 250, 250, 286, 286, 322, 322, 364, 364, 406, 406, 455, 455, 504, 504, 560, 560, 616, 616, 680, 680, 744

Offset: 0

N. J. A. Sloane

Number of partitions of n into parts 1, 2, 4 and 8. - Ilya Gutkovskiy, May 24 2017

D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 105.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 233
Index entries for Molien series
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1).

Cf. A008804, A088932 (partial sums).

R:=PowerSeriesRing(Integers(), 65); Coefficients(R!( (&*[1/(1-x^(2^j)): j in [0..3]]) )); // G. C. Greubel, Feb 01 2020

a:= proc(n) local m, r; m := iquo(n, 8, 'r'); r:= iquo(r,2)+1; ([11, 17, 26, 35][r]+ (9+ 3*r+ 4*m) *m) *m/3+ [1, 2, 4, 6][r] end: seq(a(n), n=0..100);  # Alois P. Heinz, Oct 06 2008

CoefficientList[1/((1-x)*(1-x^2)*(1-x^4)*(1-x^8)) + O[x]^65, x] (* Jean-François Alcover, May 29 2015 *)
LinearRecurrence[{1,1,-1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1}, {1,1,2,2,4,4,6,6,10,10,14,14,20,20,26}, 65] (* Ray Chandler, Jul 15 2015 *)

my(x='x+O('x^65)); Vec(1/((1-x)*(1-x^2)*(1-x^4)*(1-x^8))) \\ G. C. Greubel, Feb 01 2020

my(b(m) = (m^3 + 12*m^2 + (44 - 3*(m%2))*m + 48)\48); vector(59,n,b((n-1)\2)) \\ Hoang Xuan Thanh, Aug 14 2025

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/((1-x)*(1-x^2)*(1-x^4)*(1-x^8)) ).list()
A077952_list(65) # G. C. Greubel, Feb 01 2020

G.f.: 1/((1-x)*(1-x^2)*(1-x^4)*(1-x^8)).
a(n) = floor(((n+14)*(3*(n+1)*(-1)^n + 2*n^2 + 17*n + 57) + 24*(floor(n/2) + 1)*(-1)^floor(n/2))/768). - Tani Akinari, Jun 16 2013
a(n) ~ 1/384*n^3. - Ralf Stephan, Apr 29 2014

cp's OEIS Frontend

A181322 Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) is the number of partitions of 2*n into powers of 2 less than or equal to 2^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A089177 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n))) giving number of non-squashing partitions of n into k parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A088954 G.f.: 1/((1-x)^2*(1-x^2)*(1-x^4)*(1-x^8)*(1-x^16)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A008643 Molien series for group of 4 X 4 upper triangular matrices over GF(2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A088954 G.f.: 1/((1-x)^2(1-x^2)(1-x^4)(1-x^8)(1-x^16)).