A110200 Triangle, read by rows, where T(n,k) equals the sum of squares of numbers < 2^n having exactly k ones in their binary expansion.

1, 5, 9, 21, 70, 49, 85, 395, 535, 225, 341, 1984, 3906, 3224, 961, 1365, 9429, 24066, 29274, 17241, 3969, 5461, 43434, 135255, 215900, 188595, 86106, 16129, 21845, 196095, 717825, 1412275, 1628175, 1106445, 411995, 65025, 87381, 872788

Offset

1,2

Comments

Compare to triangle A110205 (sum of cubes).

Links

Paul D. Hanna, Rows n = 1..45, flattened.

Formula

T(n,k) = (4^n-1)/3 * C(n-2, k-1) + (2^n-1)^2 * C(n-2, k-2).

G.f.: A(x,y) = x*y*(1-2*x*(1-y)) / ((1-x*(1+y))*(1-2*x*(1+y))*(1-4*x*(1+y))).

G.f. for row n: ((4^n-1)/3 + (2^n-1)^2*x)*(1+x)^(n-2).

Example

Row 4 is formed by sums of squares of numbers < 2^4:
T(4,1) = 1^2 + 2^2 + 4^2 + 8^2 = 85;
T(4,2) = 3^2 + 5^2 + 6^2 + 9^2 + 10^2 + 12^2 = 395;
T(4,3) = 7^2 + 11^2 + 13^2 + 14^2 = 535;
T(4,4) = 15^2 = 225.
Triangle begins:
1;
5, 9;
21, 70, 49;
85, 395, 535, 225;
341, 1984, 3906, 3224, 961;
1365, 9429, 24066, 29274, 17241, 3969;
5461, 43434, 135255, 215900, 188595, 86106, 16129;
21845, 196095, 717825, 1412275, 1628175, 1106445, 411995, 65025;
87381, 872788, 3662848, 8541876, 12197570, 10974236, 6095208, 1915228, 261121; ...
Row g.f.s are:
row 1: (1 + 1*x)/(1+x);
row 2: (5 + 9*x);
row 3: (21 + 49*x)*(1+x);
row 4: (85 + 225*x)*(1+x)^2.
G.f. for row n is:
((4^n-1)/3 + (2^n-1)^2*x)*(1+x)^(n-2).

Prog

(PARI) T(n, k)=(4^n-1)/3*binomial(n-2, k-1)+(2^n-1)^2*binomial(n-2, k-2)
for(n=1, 15, for(k=1, n, print1(T(n, k), ", ")); print(""))
(PARI) /* Using G.f. of A(x, y): */
T(n, k)=local(X=x+x*O(x^n), Y=y+y*O(y^k)); if(n<k|k<1, 0, polcoeff(polcoeff(x*y*(1-2*x*(1-y))/((1-X*(1+Y))*(1-2*X*(1+Y))*(1-4*X*(1+Y))), n, x), k, y))
for(n=1, 15, for(k=1, n, print1(T(n, k), ", ")); print(""))
(PARI) /* Sum of Squares of numbers<2^n with k 1-bits: */
T(n, k)=local(B=vector(n+1)); if(n<k|k<1, 0, for(m=1, 2^n-1, B[1+sum(i=1, #binary(m), (binary(m))[i])]+=m^2); B[k+1])
for(n=1, 15, for(k=1, n, print1(T(n, k), ", ")); print(""))

Crossrefs

Cf. A110201 (central terms), A002450 (column 1), A110202 (column 2), A110203 (column 3), A110204 (column 4), A016290 (row sums), A110205.

Sequence in context: A082676 A146932 A146476 * A063404 A102177 A299266

Adjacent sequences: A110197 A110198 A110199 * A110201 A110202 A110203

Keyword

nonn,tabl

Author

Paul D. Hanna, Jul 16 2005

Status

approved