%I #44 Mar 17 2023 20:52:28
%S 1,3,9,35,201,1827,27337,692003,30251721,2320518947,316359580361,
%T 77477180493603,34394869942983369,27893897106768940835,
%U 41603705003444309596873,114788185359199234852802339,588880400923055731115178072777,5642645813427132737155703265972003
%N Column 2 of table A125790; also equals row sums of matrix power A078121^2.
%C Triangle A078121 shifts left one column under matrix square and is related to partitions into powers of 2.
%C Number of partitions of 2^n into powers of 2, excluding the trivial partition 2^n=2^n. [_Valentin Bakoev_, Feb 15 2009]
%H Alois P. Heinz, <a href="/A125792/b125792.txt">Table of n, a(n) for n = 0..86</a>
%H V. Bakoev, <a href="https://core.ac.uk/download/pdf/82206223.pdf">Algorithmic approach to counting of certain types m-ary partitions</a>, Discrete Mathematics, 275 (2004) pp. 17-41.
%F Is this sequence the same as A002575 (coefficients of Bell's formula)?
%F Denote the sum m^n + m^n + ... + m^n, k times, by k*m^n (m > 1, n > 0 and k are natural numbers). The general formula for the number of all partitions of the sum k*m^n into powers of m, smaller than m^n, is t_m(n, k)= 1 when n=1 or k=0, or = t_m(n, k-1) + Sum_{j=1..m} t_m(n-1, (k-1)*n+j), when n > 1 and k > 0. A125792 is obtained for m=2 and n=1,2,3,... [_Valentin Bakoev_, Feb 15 2009]
%F a(n) = A145515(n+1,2)-1. - _Alois P. Heinz_, Feb 27 2009
%F From _Benedict W. J. Irwin_, Nov 16 2016: (Start)
%F Conjecture: a(n+1) = Sum_{i_1=1..3} Sum_{i_2=1..2*i_1-1} ... Sum_{i_n=1..2*i_(n-1)-1} (2*i_n - 1). For example:
%F a(2) = Sum_{i=1..3} 2*i-1.
%F a(3) = Sum_{i=1..3} Sum_{j=1..2*i-1} 2*j-1.
%F a(4) = Sum_{i=1..3} Sum_{j=1..2*i-1} Sum_{k=1..2*j-1} 2*k-1. (End)
%e G.f.: 1 + 3*x + 9*x^2 + 35*x^3 + 201*x^4 + 1827*x^5 + 27337*x^6 + 692003*x^7 + ...
%e To obtain t_2(5,1) we use the table T, defined as T[i,j]= t_2(i,j), for i=1,2,...,5(=n), and j= 0,1,2,...,16(= k*m^{n-1}). It is 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 1,3,5,7,9,11,13,15,17 1,9,25,49,81 1,35,165 1,201 Column 1 contains the first 5 members of A125792. [_Valentin Bakoev_, Feb 15 2009]
%p g:= proc(b, n, k) option remember; local t; if b<0 then 0 elif b=0 or n=0 or k<=1 then 1 elif b>=n then add(g(b-t, n, k) *binomial(n+1, t) *(-1)^(t+1), t=1..n+1); else g(b-1, n, k) +g(b*k, n-1, k) fi end: a:= n-> g(1, n+1,2)-1: seq(a(n), n=0..25); # _Alois P. Heinz_, Feb 27 2009
%t T[n_, k_] := T[n, k] = T[n, k-1] + T[n-1, 2*k]; T[0, _] = T[_, 0] = 1; Table[T[n, 2], {n, 0, 20} ] (* _Jean-François Alcover_, Jun 15 2015 *)
%o (PARI) {a(n)=local(p=2,q=2,A=Mat(1), B); for(m=1, n+1, 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(sum(c=0,n,(A^p)[n+1,c+1]))}
%o for(n=0,25,print1(a(n),", "))
%o (PARI) {a(n, k=3) = if(n<1, n==0, sum(i=1, k, a(n-1, 2*i-1)))}; /* _Michael Somos_, Nov 24 2016 */
%Y Cf. A125790, A078121; A002575; columns: A002577, A125793, A125794, A125795, A125796; diagonals: A125797, A125798.
%Y Adding 1 to the members of A125792 we obtain A002577. [_Valentin Bakoev_, Feb 15 2009]
%Y A diagonal of A152977.
%K nonn
%O 0,2
%A _Paul D. Hanna_, Dec 10 2006