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

Author

Paul D. Hanna, Jul 16 2005

Keywords

• nonn
• tabl

Comments

Compare to triangle A110205 (sum of cubes).

Examples

			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).
		

Links

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

Crossrefs

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

Programs

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)=my(X=x+x*O(x^n),Y=y+y*O(y^k));if(n
				

PARI

/* Sum of Squares of numbers<2^n with k 1-bits: */
T(n,k)=my(B=vector(n+1));if(n
				

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).