cp's OEIS Frontend

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.

%I A340312 #62 Jan 06 2025 21:51:50
%S A340312 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,
%T A340312 715,448,273,140,35,0,1,1,1,1,0,155,1240,6293,27776,105183,330460,
%U A340312 876525,2011776,4032015,7063784,10855425,14721280,17678835,18796230,17678835,14721280,10855425,7063784,4032015,2011776,876525,330460,105183,27776,6293,1240,155,0,1,1
%N 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.
%C A340312 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.
%C A340312 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.
%C A340312 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.
%H A340312 Peter Luschny, <a href="/A340312/b340312.txt">Table of n, a(n) for n = 0..1032</a>
%H A340312 Katrina Honigs and Graham McDonald, <a href="https://arxiv.org/abs/2307.13129">Theta characteristics and the fixed locus of [-1] on some varieties of Kummer type</a>, arXiv:2307.13129 [math.AG], 2023. See pp. 6 and 22.
%H A340312 Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/1158584/count-subsets-with-zero-sum-of-xors">Count subsets with zero sum of xors</a>
%H A340312 Jianing Song, <a href="/A340312/a340312.c.txt">C Program for A340312, case n = 4</a>
%F A340312 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
%F A340312 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
%F A340312 From _Andrew Howroyd_, Jan 09 2021: (Start)
%F A340312 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).
%F A340312 T(n, k) = (1/k)*(binomial(2^n,k-1) - (2^n-(k-2))*T(n,k-2)) for k >= 2.
%F A340312 T(n, k) = binomial(2^n, k)/2^n for odd k.
%F A340312 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.
%F A340312 T(n, k) = [x^k] ((1+x)^(2^n) + (2^n-1)*(1-x^2)^(2^(n-1)))/2^n.
%F A340312 T(n, k) = A340030(n,k-1) + A340030(n,k).
%F A340312 (End)
%e A340312 Triangle begins:
%e A340312 [0]  1, 1;
%e A340312 [1]  1, 1, 0;
%e A340312 [2]  1, 1, 0, 1, 1;
%e A340312 [3]  1, 1, 0, 7, 14, 7, 0, 1, 1;
%e A340312 [4]  1, 1, 0, 35, 140, 273, 448, 715, 870, 715, 448, 273, 140, 35, 0, 1, 1;
%e A340312 [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;
%e A340312 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.
%e A340312 T(n,1) = 1 since the only such subset is {0}.
%e A340312 T(n,2) = 0 since no distinct a, b have a ^ b = 0.
%e A340312 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).
%e A340312 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).
%p A340312 A340312_row := proc(n) local a, b, c; c := 2^(n-1);
%p A340312 if n = 0 then return [1, 1] fi;
%p A340312 b := n -> add(binomial(2^n, 2*k)*x^(2*k), k = 0..2^n);
%p A340312 a := n -> x*mul(b(k), k = 0..n);
%p A340312 (x + 1)^c*(b(n-1) - (c-1)*a(n-2));
%p A340312 [seq(coeff(expand(%), x, j), j = 0..2*c)] end:
%p A340312 for n from 0 to 6 do A340312_row(n) od; # _Peter Luschny_, Jan 06 2021
%t A340312 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];
%t A340312 Table[T[n, k], {n, 0, 5}, {k, 0, 2^n}] // Flatten (* _Jean-François Alcover_, Jan 14 2021, after _Andrew Howroyd_ *)
%o A340312 (C) /* Generating program for T(4,k), see link. */
%o A340312 (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
%o A340312 (SageMath)
%o A340312 def A340312():
%o A340312     a, b, c = 1, 1, 1
%o A340312     yield [1, 1]
%o A340312     yield [1, 1, 0]
%o A340312     while True:
%o A340312         c *= 2
%o A340312         a *= b
%o A340312         b = sum(binomial(c, 2 * k) * x^(2 * k) for k in range(c + 1))
%o A340312         p = (x + 1)^c * (b - (c - 1) * x * a)
%o A340312         yield expand(p).list()
%o A340312 A340312_row = A340312()
%o A340312 for _ in range(6):
%o A340312     print(next(A340312_row)) # _Peter Luschny_, Jan 07 2021
%Y A340312 Cf. A000120 (hamming weight of n), A300361 (row sums).
%Y A340312 Cf. A340263 (irreducible (?) factor if T(n,k) is seen as representing polynomials).
%Y A340312 Cf. A340259(n) = T(n, 2^(n-1)), the central term of row n.
%Y A340312 Cf. A340030 (case that only nonzero elements allowed).
%Y A340312 Cf. A054669, A058878.
%Y A340312 Cf. A006095 (k=3 column), A016290 (k=4 column); cf. also A010080-A010084 and A281123. - _Jon E. Schoenfield_, Jan 06 2021
%K A340312 nonn,tabf
%O A340312 0,14
%A A340312 _Jianing Song_, Jan 04 2021
%E A340312 More terms from _Andrew Howroyd_ and _Jon E. Schoenfield_.