login
Square array T(n,k) (n >= 0, k >= 2) read by antidiagonals, where T(n,k) is the number of ways of writing n as Sum_{i>=0} c_i 2^i, c_i in {0,1,...,k-1}.
13

%I #30 Feb 20 2021 03:43:08

%S 1,1,1,1,1,1,1,2,1,1,1,1,2,1,1,1,3,2,2,1,1,1,2,3,2,2,1,1,1,3,3,4,2,2,

%T 1,1,1,1,4,3,4,2,2,1,1,1,4,4,5,4,4,2,2,1,1,1,3,5,4,5,4,4,2,2,1,1,1,5,

%U 5,8,5,6,4,4,2,2,1,1,1,2,6,6,8,5,6,4,4,2,2,1,1,1,5,6,9,8,9,6,6,4,4,2,2,1,1

%N Square array T(n,k) (n >= 0, k >= 2) read by antidiagonals, where T(n,k) is the number of ways of writing n as Sum_{i>=0} c_i 2^i, c_i in {0,1,...,k-1}.

%C k-th column is k-th binary partition function.

%C The sequence data corresponds (via the table link) to the transpose of the array shown in example and given by the definition. - _M. F. Hasler_, Feb 14 2019

%H Alois P. Heinz, <a href="/A072170/b072170.txt">Antidiagonals n = 0..140, flattened</a>

%H B. Reznick, <a href="https://doi.org/10.1007/978-1-4612-3464-7_29">Some binary partition functions</a>, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990.

%F T(n,k) = T(n,n+1) = T(n,n)+1 = A000123(floor(n/2)) for all k >= n+1. - _M. F. Hasler_, Feb 14 2019

%e Array begins: (rows n >= 0, columns k >= 2)

%e 1 1 1 1 1 1 1 1 ...

%e 1 1 1 1 1 1 1 1 ...

%e 1 2 2 2 2 2 2 2 ...

%e 1 1 2 2 2 2 2 2 ...

%e 1 3 3 4 4 4 4 4 ...

%e 1 2 3 3 4 4 4 4 ...

%e 1 3 4 5 5 6 6 6 ...

%p b:= proc(n, i, k) option remember;

%p `if`(n=0, 1, `if`(i<0, 0, add(`if`(n-j*2^i<0, 0,

%p b(n-j*2^i, i-1, k)), j=0..k-1)))

%p end:

%p T:= (n, k)-> b(n, ilog2(n), k):

%p seq(seq(T(d+2-k, k), k=2..d+2), d=0..14); # _Alois P. Heinz_, Jun 21 2012

%t b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 0, 0, Sum[If[n-j*2^i < 0, 0, b[n-j*2^i, i-1, k]], {j, 0, k-1}]]];

%t t[n_, k_] := b[n, Length[IntegerDigits[n, 2]] - 1, k];

%t Table[Table[t[d+2-k, k], {k, 2, d+2}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Jan 14 2014, translated from _Alois P. Heinz_'s Maple code *)

%o (PARI) M72170=[[]]; A072170(n,k,i=logint(n+!n,2),r=1)={if( !i, k>n, r&&(k<5||k>=n),if(k>4, A000123(n\2)-(k==n), k<3, 1, k<4, A002487(n), n\2+1), M72170[r=setsearch(M72170,[n,k,i,""],1)-1][^-1]==[n,k,i], M72170[r][4], M72170=setunion(M72170,[[n,k,i,r=sum(j=0,min(k-1,n>>i),A072170(n-j*2^i,k,i-1,0))]]);r)} \\ Code for k<5 (using A002487 for k=3) and k>=n (using A000123) is optional but makes it about 3x faster. - _M. F. Hasler_, Feb 14 2019

%Y k=3 column is A002487, k=4 is A008619 (positive integers repeated), k = 5, 6, 7 are A007728, A007729, A007730, limiting (infinity) column is A000123 doubled up.

%K nonn,tabl

%O 0,8

%A _N. J. A. Sloane_, Jun 29 2002