A125790 -id:A125790 - cp's OEIS frontend

A002577 Number of partitions of 2^n into powers of 2.

1, 2, 4, 10, 36, 202, 1828, 27338, 692004, 30251722, 2320518948, 316359580362, 77477180493604, 34394869942983370, 27893897106768940836, 41603705003444309596874, 114788185359199234852802340, 588880400923055731115178072778, 5642645813427132737155703265972004

Offset: 0

N. J. A. Sloane

For given m, the general formula for t_m(n, k) and the corresponding tables T, computed as in the example, determine a family of related sequences (placed in the rows or in the columns of T). For example, the numbers from the second row of T, computed for given m and n > 2, are the (m+2)-gonal numbers. So the second row contains the first members of: A000290 (the square numbers) when m=2, A000326 (the pentagonal numbers) when m=3, and so on. But rows IV, V etc. of the given table are not represented in the OEIS till now. - Valentin Bakoev, Feb 25 2009; edited by M. F. Hasler, Feb 09 2014

			To compute t_2(6,1) we can use a table T, defined as T[i,j]= t_2(i,j), for i=1,2,...,6(=n), and j= 0,1,2,...,32(= k*m^{n-1}). It is: 1,2,3,4,5,6,7,8,9...,33; 1,4,9,16,25,36,49...,81; (so the second row contains the first members of A000290 -- the square numbers) 1,10,35,84,165,...,969; (so the third row contains the first members of A000447. The r-th tetrahedral number is given by formula r(r+1)(r+2)/6. This row (also A000447) contains the tetrahedral numbers, obtained for r=1,3,5,7,...) 1,36,201,656,1625; 1,202,1827; 1,1828; Column 1 contains the first 6 members of A002577. - _Valentin Bakoev_, Feb 25 2009
G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 36*x^4 + 202*x^5 + 1828*x^6 + ...

R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
Lawrence, Jim. "Dual-Antiprisms and Partitions of Powers of 2 into Powers of 2." Discrete & Computational Geometry, Vol. 16 (2019): 465-478. See page 466.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..85
V. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp.17-41.
C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, 2012. - From _N. J. A. Sloane_, Dec 23 2012
G. Blom and C.-E. Froeberg, Om myntvaexling, (On money-changing) [ Swedish ], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103.
G. Blom and C.-E. Froeberg, Om myntvaexling (On money-changing) [Swedish], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103. [Annotated scanned copy]
R. F. Churchhouse, Congruence properties of the binary partition function, Math. Proc. Cambr. Phil. Soc. vol 66, no. 2 (1969), 365-370.
Carl-Erik Froberg, Accurate estimation of the number of binary partitions, BIT Numerical Mathematics vol. 17, no 4 (1977) 386-391.
C.-E. Froberg, Accurate estimation of the number of binary partitions [Annotated scanned copy]
H. Minc, The free commutative entropic logarithmetic, Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).

a(n) = A000123(2^(n-1)) = A018818(2^n).
Cf. A078537, A078121, A000290, A000447.
Column k=2 of A145515, diagonal of A152977. - Alois P. Heinz, Mar 25 2012
See also A002575, A002576.
A column of A125790.
Cf. A000079, A078125, A145513.

import Data.MemoCombinators (memo2, list, integral)
a002577 n = a002577_list !! n
a002577_list = f [1] where
   f xs = (p' xs $ last xs) : f (1 : map (* 2) xs)
   p' = memo2 (list integral) integral p
   p  0 = 1; p []  = 0
   p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m
-- Reinhard Zumkeller, Nov 27 2015

A002577 := proc(n) if n<=1 then n+1 else A000123(2^(n-1)); fi; end;

$RecursionLimit = 10^5; (* b = A000123 *) b[0] = 1; b[n_?EvenQ] := b[n] = b[n-1] + b[n/2]; b[n_?OddQ] := b[n] = b[n-1] + b[(n-1)/2]; a[n_] := b[2^(n-1)]; a[0] = 1; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Nov 23 2011 *)
a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^2^k, {k, 0, n}], {x, 0, 2^n}]; (* Michael Somos, Apr 21 2014 *)

a(n)=polcoeff(prod(j=0,n,1/(1-x^(2^j)+x*O(x^(2^n)))),2^n) \\ Paul D. Hanna

a(n) is about 0.9233*Sum_j {i=0, 1, 2, 3, ...} 2^(j*(2n-j-1)/2)/j!. - Henry Bottomley, Jul 23 2003
a(n) = A078121(n+1, 1). - Paul D. Hanna, Sep 13 2004
A002577(n)-1 = A125792(n). - Let m > 1, n > 0 and k >= 0. The general formula for the number of all partitions of k*m^n into powers of m is t_m(n, k)= k+1 if n=1, t_m(n, k)= 1 if k=0, and t_m(n, k)= t_m(n, k-1) + t_m(n-1, k*m) if n > 1 and k > 0. A002577 is obtained for m=2 and n=1,2,3,... - Valentin Bakoev, Feb 25 2009
a(n) = [x^(2^n)] 1/Product_{j>=0} (1-x^(2^j)). - Alois P. Heinz, Sep 27 2011

Edited by M. F. Hasler, Feb 09 2014

A125791 a(n) = 2^(n(n-1)(n-2)/6) for n>=1.

Original entry on oeis.org

1, 1, 2, 16, 1024, 1048576, 34359738368, 72057594037927936, 19342813113834066795298816, 1329227995784915872903807060280344576, 46768052394588893382517914646921056628989841375232

Offset: 1

Paul D. Hanna, Dec 10 2006

nonn

a(n) is a tetrahedral power of 2; exponents of 2 in a(n) begin: 0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, ..., n*(n-1)*(n-2)/6, ... (cf. A000292).
Table A125790 is related to partitions into powers of 2, with A002577 in column 1 of A125790; further, column k of A125790 equals row sums of matrix power A078121^k, where triangle A078121 shifts left one column under matrix square.
Also number of distinct instances of the one-in-three monotone 3SAT problem for n variables. - Paul Tarau (paul.tarau(AT)gmail.com), Jan 25 2008
Hankel transform of aerated 2-Catalan numbers (A015083). [Paul Barry, Dec 15 2010]

Michael De Vlieger, Table of n, a(n) for n = 1..28
Pakawut Jiradilok, Some Combinatorial Formulas Related to Diagonal Ramsey Numbers, arXiv:2404.02714 [math.CO], 2024. See p. 19.

Cf. A125790, A078121; A002577, A000292.

seq(2^(binomial(n, n-3)), n=1..10); # Zerinvary Lajos, Jun 16 2007 [modified by Georg Fischer, Nov 09 2023]

A125791[n_]:=2^Binomial[n,n-3];Array[A125791,15] (* Paolo Xausa, Nov 05 2023 *)

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

/* As determinant of n X n matrix: */
{a(n)=local(q=2,A=Mat(1), B); for(m=1, n, B=matrix(m, m);
for(i=1, m, for(j=1, i, if(j==i||j==1, B[i, j]=1, B[i, j]=(A^q)[i-1, j-1]); )); A=B);
return(matdet(matrix(n,n,r,c,(A^c)[r,1])))}
for(n=1,15,print1(a(n),", "))

% This generates all 3SAT problem instances
test:-test(4).
test(Max):-
between(1,Max,N),
nl,
one_in_three_monotone_3sat(N,Pss),
write(N:Pss),nl,
fail
; nl.
% generates all one-in-three monotone 3SAT problems involving N variables
one_in_three_monotone_3sat(N,Pss):-
ints(1,N,Is),
findall(Xs,ksubset(3,Is,Xs),Xss),
subset_of(Xss,Pss).
% subset generator
subset_of([],[]).
subset_of([X|Xs],Zs):-
subset_of(Xs,Ys),
add_element(X,Ys,Zs).
add_element(_,Ys,Ys).
add_element(X,Ys,[X|Ys]).
% subsets of K elements
ksubset(0,_,[]).
ksubset(K,[X|Xs],[X|Rs]):-K>0,K1 is K-1,ksubset(K1,Xs,Rs).
ksubset(K,[_|Xs],Rs):-K>0,ksubset(K,Xs,Rs).
% list of integers in [From..To]
ints(From,To,Is):-findall(I,between(From,To,I),Is).
% Paul Tarau (paul.tarau(AT)gmail.com), Jan 25 2008

Determinant of n X n upper left corner submatrix of table A125790.

a(n) = 2^(binomial(n,n-3)). - Zerinvary Lajos, Jun 16 2007, modified to reflect the new offset by Paolo Xausa, Nov 06 2023.

Name simplified; determinant formula moved out of name into formula section by Paul D. Hanna, Oct 16 2013

Offset changed to 1 by Paolo Xausa, Nov 06 2023

A125800 Rectangular table where column k equals row sums of matrix power A078122^k, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 23, 12, 4, 1, 1, 239, 93, 22, 5, 1, 1, 5828, 1632, 238, 35, 6, 1, 1, 342383, 68457, 5827, 485, 51, 7, 1, 1, 50110484, 7112055, 342382, 15200, 861, 70, 8, 1, 1, 18757984046, 1879090014, 50110483, 1144664, 32856, 1393, 92, 9, 1

Offset: 0

Paul D. Hanna, Dec 10 2006

Determinant of n X n upper left submatrix is 3^(n*(n-1)*(n-2)/6).
This table is related to partitions of numbers into powers of 3 (see A078122).
Triangle A078122 shifts left one column under matrix cube.
Column 1 is A078125, which equals row sums of A078122;
column 2 is A078124, which equals row sums of A078122^2.

			Recurrence T(n,k) = T(n,k-1) + T(n-1,3*k) is illustrated by:
  T(3,3) = T(3,2) + T(2,9) = 93 + 145 = 238;
  T(4,3) = T(4,2) + T(3,9) = 1632 + 4195 = 5827;
  T(5,3) = T(5,2) + T(4,9) = 68457 + 273925 = 342382.
Rows of this table begin:
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...;
  1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, ...;
  1, 23, 93, 238, 485, 861, 1393, 2108, 3033, 4195, 5621, ...;
  1, 239, 1632, 5827, 15200, 32856, 62629, 109082, 177507, 273925,...;
  1, 5828, 68457, 342382, 1144664, 3013980, 6769672, 13570796, ...;
  1, 342383, 7112055, 50110483, 215155493, 690729981, 1828979530, ...;
  1, 50110484, 1879090014, 18757984045, 103674882878, 406279238154,..;
  1, 18757984046, 1287814075131, 18318289003447, 130648799730635, ...;
Triangle A078122 begins:
  1;
  1,     1;
  1,     3,      1;
  1,    12,      9,     1;
  1,    93,    117,    27,    1;
  1,  1632,   3033,  1080,   81,   1;
  1, 68457, 177507, 86373, 9801, 243, 1; ...
where row sums form column 1 of this table A125790,
and column k of A078122 equals column 3^k - 1 of this table A125800.
Matrix square A078122^2 begins:
     1;
     2,     1;
     5,     6,     1;
    23,    51,    18,    1;
   239,   861,   477,   54,   1;
  5828, 32856, 25263, 4347, 162, 1; ...
where row sums form column 2 of this table A125790,
and column 0 of A078122^2 forms column 1 of this table A125790.

Robert Israel, Table of n, a(n) for n = 0..2484 (antidiagonals 0 to 69, flattened)

Cf. A078122; columns: A078125, A078124, A125801, A125802, A125803; A125804 (diagonal), A125805 (antidiagonal sums); related table: A125800 (q=2).

f[0]:= 1/(1-z):
S[0]:= series(f[0],z,21):
for n from 1 to 20 do
  ff:= unapply(f[n-1],z);
  f[n]:= simplify(1/3*sum(ff(w*z^(1/3)),w=RootOf(Z^3-1,Z)))/(1-z);
  S[n]:= series(f[n],z,21-n)
od:
seq(seq(coeff(S[s-i],z,i),i=0..s),s=0..20); # Robert Israel, Jun 02 2019

T[0, ] = T[, 0] = 1; T[n_, k_] := T[n, k] = T[n, k-1] + T[n-1, 3 k]; Table[T[n-k, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 08 2016 *)

T(n,k,p=0,q=3)=local(A=Mat(1), B); if(n

T(n,k) = T(n,k-1) + T(n-1,3*k) for n > 0, k > 0, with T(0,n)=T(n,0)=1 for n >= 0.

G.f. of row n is g_n(z) where g_{n+1}(z) = (1-z)^(-1)*Sum_{w^3=1} g_n(w*z^(1/3)) (the sum being over the cube roots of unity). - Robert Israel, Jun 02 2019

A125860 Rectangular table where column k equals row sums of matrix power A097712^k, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 17, 12, 4, 1, 1, 86, 69, 22, 5, 1, 1, 698, 612, 178, 35, 6, 1, 1, 9551, 8853, 2251, 365, 51, 7, 1, 1, 226592, 217041, 46663, 5990, 651, 70, 8, 1, 1, 9471845, 9245253, 1640572, 161525, 13131, 1057, 92, 9, 1, 1, 705154187

Offset: 0

Paul D. Hanna, Dec 13 2006

Triangle A097712 satisfies: A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1) for n > 0, k > 0, with A097712(n,0)=A097712(n,n)=1 for n >= 0. Column 1 equals A016121, which counts the sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.

T(2, n) = (n+1)*A005408(n) - Sum_{i=0..n} A001477(i) = (n+1)*(2*n+1) - A000217(n) = (n+1)*(3*n+2)/2; T(3, n) = (n+1)*A001106(n+1) - Sum_{i=0..n} A001477(i) = (n+1)*((n+1)*(7*n+2)/2) - A000217(n) = (n+1)*(7*n^2 + 8*n + 2)/2. - Bruno Berselli, Apr 25 2010

			Recurrence is illustrated by:
  T(4,1) = T(3,1) + T(3,2) = 17 + 69 = 86;
  T(4,2) = T(3,2) + T(3,3) + T(3,4) = 69 + 178 + 365 = 612;
  T(4,3) = T(3,3) + T(3,4) + T(3,5) + T(3,6) = 178 + 365 + 651 + 1057 = 2251.
Rows of this table begin:
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,...;
  1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, ...;
  1, 17, 69, 178, 365, 651, 1057, 1604, 2313, 3205, 4301, 5622, 7189,..;
  1, 86, 612, 2251, 5990, 13131, 25291, 44402, 72711, 112780, 167486,..;
  1, 698, 8853, 46663, 161525, 435801, 996583, 2025458, 3768273, ...;
  1, 9551, 217041, 1640572, 7387640, 24530016, 66593821, 156664796, ...;
  1, 226592, 9245253, 100152049, 586285040, 2394413286, 7713533212, ...;
  1, 9471845, 695682342, 10794383587, 82090572095, 412135908606, ...;
  1, 705154187, 93580638024, 2079805452133, 20540291522675, ...;
  1, 94285792211, 22713677612832, 723492192295786, 9278896006526795,...;
  1, 22807963405043, 10025101876435413, 458149292979837523, ...;
  ...
where column k equals the row sums of matrix power A097712^k for k >= 0.
Triangle A097712 begins:
  1;
  1,      1;
  1,      3,       1;
  1,      8,       7,       1;
  1,     25,      44,      15,       1;
  1,    111,     346,     208,      31,      1;
  1,    809,    4045,    3720,     912,     63,     1;
  1,  10360,   77351,   99776,   35136,   3840,   127,   1;
  1, 236952, 2535715, 4341249, 2032888, 308976, 15808, 255; ...
where A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1);
e.g., A097712(5,2) = A097712(4,2) + [A097712^2](4,1) = 44 + 302 = 346.
Matrix square A097712^2 begins:
     1;
     2,     1;
     5,     6,     1;
    17,    37,    14,     1;
    86,   302,   193,    30,    1;
   698,  3699,  3512,   881,   62,   1;
  9551, 73306, 96056, 34224, 3777, 126, 1; ...
Matrix cube A097712^3 begins:
       1;
       3,      1;
      12,      9,      1;
      69,     87,     21,      1;
     612,   1146,    447,     45,    1;
    8853,  22944,  12753,   2019,   93,   1;
  217041, 744486, 549453, 120807, 8595, 189, 1; ...

Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See p. 16.

Cf. A097712; columns: A016121, A125862, A125863, A125864, A125865; A125861 (diagonal), A125859 (antidiagonal sums). Variants: A125790, A125800.

Cf. for recursive method [Ar(m) is the m-th term of a sequence in the OEIS] a(n) = n*Ar(n) - A000217(n-1) or a(n) = (n+1)*Ar(n+1) - A000217(n) and similar: A081436, A005920, A005945, A006003. - Bruno Berselli, Apr 25 2010

T[n_, k_] := T[n, k] = If[Or[n == 0, k == 0], 1, Sum[T[n - 1, j + k], {j, 0, k}]];
Table[T[#, k] &[n - k + 1], {n, 0, 9}, {k, 0, n + 1}] (* Michael De Vlieger, Dec 10 2024, after PARI *)

T(n,k)=if(n==0 || k==0,1,sum(j=0,k,T(n-1,j+k)))

T(n,k) = Sum_{j=0..k} T(n-1, j+k) for n > 0, with T(0,n)=T(n,0)=1 for n >= 0.

cp's OEIS Frontend

A002577 Number of partitions of 2^n into powers of 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A125791 a(n) = 2^(n*(n-1)*(n-2)/6) for n>=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Prolog

Formula

Extensions

A125800 Rectangular table where column k equals row sums of matrix power A078122^k, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A125860 Rectangular table where column k equals row sums of matrix power A097712^k, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A125791 a(n) = 2^(n(n-1)(n-2)/6) for n>=1.