A340312 Triangle read by rows: T(n,k) is the number of subsets of {0..2^n-1} with k elements such that the bitwise-xor of all the subset members gives zero, 0 <= k <= 2^n.

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 7, 14, 7, 0, 1, 1, 1, 1, 0, 35, 140, 273, 448, 715, 870, 715, 448, 273, 140, 35, 0, 1, 1, 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

Offset: 0

Author

Jianing Song, Jan 04 2021

Keywords

• nonn
• tabf

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.

Examples

			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).
		

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

Crossrefs

Cf. A000120 (hamming weight of n), A300361 (row sums).

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).

Cf. A054669, A058878.

Cf. A006095 (k=3 column), A016290 (k=4 column); cf. also A010080-A010084 and A281123. - Jon E. Schoenfield, Jan 06 2021

Programs

C

/* Generating program for T(4,k), see link. */

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 *)

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()
A340312_row = A340312()
for _ in range(6):
    print(next(A340312_row)) # Peter Luschny, Jan 07 2021

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.

T(n, k) = A340030(n,k-1) + A340030(n,k).

(End)

Extensions

More terms from Andrew Howroyd and Jon E. Schoenfield.