OFFSET
0,14
COMMENTS
Sum_{k=0..2^n} T(n, k) gives the total number of subsets with bitwise-xor of all the subset members zero. There are in total 2^(2^n - n) such subsets of {0, 1, ..., 2^n-1}, see A300361 and the Mathematics Stack Exchange link below.
Equivalently, T(n, k) is the number of subsets of the vector space (F_2)^n such that the sum of elements in the subset is the zero vector.
T(n, k) is symmetric, that is, T(n, k) = T(n, 2^n-k) for k = 0..2^n, since if the bitwise-xor of the members in S is zero, then the complement of S in {0, 1, ..., 2^n-1} also has this property.
LINKS
Peter Luschny, Table of n, a(n) for n = 0..1032
Katrina Honigs and Graham McDonald, Theta characteristics and the fixed locus of [-1] on some varieties of Kummer type, arXiv:2307.13129 [math.AG], 2023. See pp. 6 and 22.
Mathematics Stack Exchange, Count subsets with zero sum of xors
Jianing Song, C Program for A340312, case n = 4
FORMULA
T(n, k) = [x^k] p(n; x) where p(n; x) = (x + 1)^c*(b(n-1) - (c-1)*a(n-2)), b(n) = Sum_{k=0..2^n} binomial(2^n, 2*k)*x^(2*k), a(n) = x*Product_{k=0..n} b(k) and c = 2^(n-1), for n >= 1. - Peter Luschny, Jan 06 2021
T(n+1, k) = [x^k] (x+1)^(2^n)*p_n(x) where p_n(x) are the polynomials defined in A340263. - Peter Luschny, Jan 06 2021
From Andrew Howroyd, Jan 09 2021: (Start)
First take any subset of k-1 elements and append the bitwise-xor of the elements. The final element will either be a duplicate or not and consideration of the two cases leads to a formula linking T(n,k) and T(n,k-2) with binomial(2^n,k-1).
T(n, k) = (1/k)*(binomial(2^n,k-1) - (2^n-(k-2))*T(n,k-2)) for k >= 2.
T(n, k) = binomial(2^n, k)/2^n for odd k.
T(n, k) = binomial(2^n, k)/2^n + (-1)^(k/2)*(1-1/2^n)*binomial(2^(n-1), k/2) for even k.
T(n, k) = [x^k] ((1+x)^(2^n) + (2^n-1)*(1-x^2)^(2^(n-1)))/2^n.
(End)
EXAMPLE
Triangle begins:
[0] 1, 1;
[1] 1, 1, 0;
[2] 1, 1, 0, 1, 1;
[3] 1, 1, 0, 7, 14, 7, 0, 1, 1;
[4] 1, 1, 0, 35, 140, 273, 448, 715, 870, 715, 448, 273, 140, 35, 0, 1, 1;
[5] 1, 1, 0, 155, 1240, 6293, 27776, 105183, 330460, 876525, 2011776, 4032015, 7063784, 10855425, 14721280, 17678835, 18796230, 17678835, 14721280, 10855425, 7063784, 4032015, 2011776, 876525, 330460, 105183, 27776, 6293, 1240, 155, 0, 1, 1;
T(n,0) = 1 since the bitwise-xor of all the elements in the empty set is the identity of bitwise-xor (0), hence the empty set meets the requirement.
T(n,1) = 1 since the only such subset is {0}.
T(n,2) = 0 since no distinct a, b have a ^ b = 0.
T(n,3) = A006095(n): if distinct a, b, c have a ^ b ^ c = 0, then c = a ^ b, and a, b must both be nonzero since a = 0 implies b = c. On the other hand, if a, b are nonequal and are both nonzero, then c = a ^ b has c != a and c != b since c = a implies b = 0. So the total number of triples (a, b, c) is (2^n-1)*(2^n-2), and the total number of subsets {a, b, c} is (2^n-1)*(2^n-2)/3! = A006095(n).
T(n,4) = A016290(n-2): if distinct a, b, c, d have a ^ b ^ c ^ d = 0, then d = a ^ b ^ c. On the other hand, if a, b, c are distinct, then d = a ^ b ^ c has d != a, d != b, d != c since d = a implies b = c. So the total number of quadruples (a, b, c, d) is 2^n*(2^n-1)*(2^n-2), and the total number of subsets {a, b, c, d} is 2^n*(2^n-1)*(2^n-2)/4! = A016290(n-2).
MAPLE
A340312_row := proc(n) local a, b, c; c := 2^(n-1);
if n = 0 then return [1, 1] fi;
b := n -> add(binomial(2^n, 2*k)*x^(2*k), k = 0..2^n);
a := n -> x*mul(b(k), k = 0..n);
(x + 1)^c*(b(n-1) - (c-1)*a(n-2));
[seq(coeff(expand(%), x, j), j = 0..2*c)] end:
for n from 0 to 6 do A340312_row(n) od; # Peter Luschny, Jan 06 2021
MATHEMATICA
T[n_, k_] := Binomial[2^n, k]/2^n + If[EvenQ[k], (-1)^(k/2)*(1-1/2^n)* Binomial[2^(n-1), k/2], 0];
Table[T[n, k], {n, 0, 5}, {k, 0, 2^n}] // Flatten (* Jean-François Alcover, Jan 14 2021, after Andrew Howroyd *)
PROG
(C) /* Generating program for T(4, k), see link. */
(PARI) T(n, k)={binomial(2^n, k)/2^n + if(k%2==0, (-1)^(k/2)*(1-1/2^n)*binomial(2^(n-1), k/2))} \\ Andrew Howroyd, Jan 09 2021
(SageMath)
def A340312():
a, b, c = 1, 1, 1
yield [1, 1]
yield [1, 1, 0]
while True:
c *= 2
a *= b
b = sum(binomial(c, 2 * k) * x^(2 * k) for k in range(c + 1))
p = (x + 1)^c * (b - (c - 1) * x * a)
yield expand(p).list()
for _ in range(6):
print(next(A340312_row)) # Peter Luschny, Jan 07 2021
CROSSREFS
Cf. A340263 (irreducible (?) factor if T(n,k) is seen as representing polynomials).
Cf. A340259(n) = T(n, 2^(n-1)), the central term of row n.
Cf. A340030 (case that only nonzero elements allowed).
KEYWORD
nonn,tabf
AUTHOR
Jianing Song, Jan 04 2021
EXTENSIONS
More terms from Andrew Howroyd and Jon E. Schoenfield.
STATUS
approved