%I #19 Oct 09 2024 12:18:56

%S 1,1,4,4,14,19,24,32,40,47,66,69,90,101,110,116,144,162,174,186,230,

%T 221,270,275,318,352,362,391,428,442,480,494,526,568,602,648,682,712,

%U 784,814,846,866,928,951,1028,1061,1096,1133,1206,1256,1296,1378,1434,1441,1504,1577,1616,1697,1734,1837

%N a(n) = (1/2^n) * Sum_{k=0..n^2} ( binomial(n^2,k) (mod 2^n) ).

%H Paul D. Hanna, <a href="/A376531/b376531.txt">Table of n, a(n) for n = 1..235</a>

%e The table of residues of the binomial coefficients in (1 + x)^(n^2) modulo 2^n begins:

%e (1+x) (mod 2): [1, 1];

%e (1+x)^4 (mod 2^2): [1, 0, 2, 0, 1];

%e (1+x)^9 (mod 2^3): [1, 1, 4, 4, 6, 6, 4, 4, 1, 1];

%e (1+x)^16 (mod 2^4): [1, 0, 8, 0, 12, 0, 8, 0, 6, 0, 8, 0, 12, 0, 8, 0, 1];

%e (1+x)^25 (mod 2^5): [1, 25, 12, 28, 10, 10, 12, 28, 7, 31, 24, 24, 12, 12, 24, 24, 31, 7, 28, 12, 10, 10, 28, 12, 25, 1];

%e (1+x)^36 (mod 2^6): [1, 36, 54, 36, 25, 32, 16, 32, 52, 48, 40, 48, 4, 32, 48, 32, 46, 24, 4, 24, 46, 32, 48, 32, 4, 48, 40, 48, 52, 32, 16, 32, 25, 36, 54, 36, 1];

%e (1+x)^49 (mod 2^7): [1, 49, 24, 120, 36, 68, 72, 40, 18, 82, 72, 104, 52, 20, 88, 120, 95, 79, 112, 48, 72, 8, 80, 16, 60, 60, 16, 80, 8, 72, 48, 112, 79, 95, 120, 88, 20, 52, 104, 72, 82, 18, 40, 72, 68, 36, 120, 24, 49, 1];

%e ...

%e where a(n) equals the sum of row n divided by 2^n:

%e a(1) = (1 + 1)/2 = 1;

%e a(2) = (1 + 0 + 2 + 0 + 1)/2^2 = 1;

%e a(3) = (1 + 1 + 4 + 4 + 6 + 6 + 4 + 4 + 1 + 1)/2^3 = 4;

%e a(4) = (1 + 0 + 8 + 0 + 12 + 0 + 8 + 0 + 6 + 0 + 8 + 0 + 12 + 0 + 8 + 0 + 1)/2^4 = 4;

%e a(5) = (1 + 25 + 12 + 28 + 10 + 10 + 12 + 28 + 7 + 31 + 24 + 24 + 12 + 12 + 24 + 24 + 31 + 7 + 28 + 12 + 10 + 10 + 28 + 12 + 25 + 1)/2^5 = 14;

%e a(6) = (1 + 36 + 54 + 36 + 25 + 32 + 16 + 32 + 52 + 48 + 40 + 48 + 4 + 32 + 48 + 32 + 46 + 24 + 4 + 24 + 46 + 32 + 48 + 32 + 4 + 48 + 40 + 48 + 52 + 32 + 16 + 32 + 25 + 36 + 54 + 36 + 1)/2^6 = 19;

%e ...

%e Odd terms occur at positions: [1, 2, 6, 10, 12, 14, 22, 24, 28, 44, 46, 48, 54, 56, 58, 60, 66, 72, 74, 78, 82, 84, 86, 90, 94, 96, 102, 106, 116, 122, 136, 142, 144, 146, 150, ...].

%t Table[(1/2^n)*Sum[Mod[Binomial[n^2,k],2^n],{k,0,n^2}],{n,60}] (* _James C. McMahon_, Oct 07 2024 *)

%o (PARI) {a(n) = sum(k=0,n^2, binomial(n^2,k) % (2^n) )/2^n}

%o for(n=1,60,print1(a(n),", "))

%o (Python)

%o def A376531(n):

%o m, r, c, b, d = (1<<n)-1, n**2, 1, n**2, 1

%o for k in range(1,r+1):

%o c += b//d&m

%o b *= r-k

%o d *= k+1

%o return c>>n # _Chai Wah Wu_, Oct 09 2024

%Y Cf. A376532, A376533, A376534, A376535, A376536.

%K nonn

%O 1,3

%A _Paul D. Hanna_, Oct 06 2024