A376531 - OEIS

A376531

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

1, 1, 4, 4, 14, 19, 24, 32, 40, 47, 66, 69, 90, 101, 110, 116, 144, 162, 174, 186, 230, 221, 270, 275, 318, 352, 362, 391, 428, 442, 480, 494, 526, 568, 602, 648, 682, 712, 784, 814, 846, 866, 928, 951, 1028, 1061, 1096, 1133, 1206, 1256, 1296, 1378, 1434, 1441, 1504, 1577, 1616, 1697, 1734, 1837

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Paul D. Hanna, Table of n, a(n) for n = 1..235

EXAMPLE

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

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

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

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

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

(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];

(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];

(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];

...

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

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

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

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

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

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;

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;

...

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, ...].

MATHEMATICA

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

PROG

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

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

(Python)

def A376531(n):

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

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

c += b//d&m

b *= r-k

d *= k+1