login
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.
6
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
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)=my(X=x+x*O(x^n), Y=y+y*O(y^k)); if(n<k||k<1, 0, polcoef(polcoef(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)=my(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 A375238
KEYWORD
nonn,tabl
AUTHOR
Paul D. Hanna, Jul 16 2005
STATUS
approved