|
%I #60 Aug 08 2023 14:23:07
%S 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 715,448,273,140,35,0,1,1,1,1,0,155,1240,6293,27776,105183,330460,
%U 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 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 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 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 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 Peter Luschny, <a href="/A340312/b340312.txt">Table of n, a(n) for n = 0..1032</a>
%H 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 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 Jianing Song, <a href="/A340312/a340312.c.txt">C Program for A340312, case n = 4</a>
%F 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 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 From _Andrew Howroyd_, Jan 09 2021: (Start)
%F 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 T(n, k) = (1/k)*(binomial(2^n,k-1) - (2^n-(k-2))*T(n,k-2)) for k >= 2.
%F T(n, k) = binomial(2^n, k)/2^n for odd k.
%F 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 T(n, k) = [x^k] ((1+x)^(2^n) + (2^n-1)*(1-x^2)^(2^(n-1)))/2^n.
%F T(n, k) = A340030(n,k-1) + A340030(n,k).
%F (End)
%e Triangle begins:
%e [0] 1, 1;
%e [1] 1, 1, 0;
%e [2] 1, 1, 0, 1, 1;
%e [3] 1, 1, 0, 7, 14, 7, 0, 1, 1;
%e [4] 1, 1, 0, 35, 140, 273, 448, 715, 870, 715, 448, 273, 140, 35, 0, 1, 1;
%e [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 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 T(n,1) = 1 since the only such subset is {0}.
%e T(n,2) = 0 since no distinct a, b have a ^ b = 0.
%e 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 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_row := proc(n) local a, b, c; c := 2^(n-1);
%p if n = 0 then return [1, 1] fi;
%p b := n -> add(binomial(2^n, 2*k)*x^(2*k), k = 0..2^n);
%p a := n -> x*mul(b(k), k = 0..n);
%p (x + 1)^c*(b(n-1) - (c-1)*a(n-2));
%p [seq(coeff(expand(%), x, j), j = 0..2*c)] end:
%p for n from 0 to 6 do A340312_row(n) od; # _Peter Luschny_, Jan 06 2021
%t 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 Table[T[n, k], {n, 0, 5}, {k, 0, 2^n}] // Flatten (* _Jean-François Alcover_, Jan 14 2021, after _Andrew Howroyd_ *)
%o (C) Generating program for T(4,k), see link.
%o (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 (SageMath)
%o def A340312():
%o a, b, c = 1, 1, 1
%o yield [1, 1]
%o yield [1, 1, 0]
%o while True:
%o c *= 2
%o a *= b
%o b = sum(binomial(c, 2 * k) * x^(2 * k) for k in range(c + 1))
%o p = (x + 1)^c * (b - (c - 1) * x * a)
%o yield expand(p).list()
%o A340312_row = A340312()
%o for _ in range(6):
%o print(next(A340312_row)) # _Peter Luschny_, Jan 07 2021
%Y Cf. A000120 (hamming weight of n), A300361 (row sums).
%Y Cf. A340263 (irreducible (?) factor if T(n,k) is seen as representing polynomials).
%Y Cf. A340259(n) = T(n, 2^(n-1)), the central term of row n.
%Y Cf. A340030 (case that only nonzero elements allowed).
%Y Cf. A054669, A058878.
%Y Cf. A006095 (k=3 column), A016290 (k=4 column); cf. also A010080-A010084 and A281123. - _Jon E. Schoenfield_, Jan 06 2021
%K nonn,tabf
%O 0,14
%A _Jianing Song_, Jan 04 2021
%E More terms from _Andrew Howroyd_ and _Jon E. Schoenfield_.
|
