cp's OEIS Frontend

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.

%I A110200 #18 Jul 22 2024 15:18:19
%S A110200 1,5,9,21,70,49,85,395,535,225,341,1984,3906,3224,961,1365,9429,24066,
%T A110200 29274,17241,3969,5461,43434,135255,215900,188595,86106,16129,21845,
%U A110200 196095,717825,1412275,1628175,1106445,411995,65025,87381,872788
%N 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.
%C A110200 Compare to triangle A110205 (sum of cubes).
%H A110200 Paul D. Hanna, <a href="/A110200/b110200.txt">Rows n = 1..45, flattened.</a>
%F A110200 T(n,k) = (4^n-1)/3 * C(n-2, k-1) + (2^n-1)^2 * C(n-2, k-2).
%F A110200 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))).
%F A110200 G.f. for row n: ((4^n-1)/3 + (2^n-1)^2*x)*(1+x)^(n-2).
%e A110200 Row 4 is formed by sums of squares of numbers < 2^4:
%e A110200 T(4,1) = 1^2 + 2^2 + 4^2 + 8^2 = 85;
%e A110200 T(4,2) = 3^2 + 5^2 + 6^2 + 9^2 + 10^2 + 12^2 = 395;
%e A110200 T(4,3) = 7^2 + 11^2 + 13^2 + 14^2 = 535;
%e A110200 T(4,4) = 15^2 = 225.
%e A110200 Triangle begins:
%e A110200 1;
%e A110200 5, 9;
%e A110200 21, 70, 49;
%e A110200 85, 395, 535, 225;
%e A110200 341, 1984, 3906, 3224, 961;
%e A110200 1365, 9429, 24066, 29274, 17241, 3969;
%e A110200 5461, 43434, 135255, 215900, 188595, 86106, 16129;
%e A110200 21845, 196095, 717825, 1412275, 1628175, 1106445, 411995, 65025;
%e A110200 87381, 872788, 3662848, 8541876, 12197570, 10974236, 6095208, 1915228, 261121; ...
%e A110200 Row g.f.s are:
%e A110200 row 1: (1 + 1*x)/(1+x);
%e A110200 row 2: (5 + 9*x);
%e A110200 row 3: (21 + 49*x)*(1+x);
%e A110200 row 4: (85 + 225*x)*(1+x)^2.
%e A110200 G.f. for row n is:
%e A110200 ((4^n-1)/3 + (2^n-1)^2*x)*(1+x)^(n-2).
%o A110200 (PARI) T(n,k)=(4^n-1)/3*binomial(n-2,k-1)+(2^n-1)^2*binomial(n-2,k-2)
%o A110200 for(n=1, 15, for(k=1, n, print1(T(n, k), ", ")); print(""))
%o A110200 (PARI) /* Using G.f. of A(x,y): */
%o A110200 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))
%o A110200 for(n=1, 15, for(k=1, n, print1(T(n, k), ", ")); print(""))
%o A110200 (PARI) /* Sum of Squares of numbers<2^n with k 1-bits: */
%o A110200 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])
%o A110200 for(n=1, 15, for(k=1, n, print1(T(n, k), ", ")); print(""))
%Y A110200 Cf. A110201 (central terms), A002450 (column 1), A110202 (column 2), A110203 (column 3), A110204 (column 4), A016290 (row sums), A110205.
%K A110200 nonn,tabl
%O A110200 1,2
%A A110200 _Paul D. Hanna_, Jul 16 2005