login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
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 (list; graph; refs; listen; history; text; internal format)
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
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
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)
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. 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. A006095 (k=3 column), A016290 (k=4 column); cf. also A010080-A010084 and A281123. - Jon E. Schoenfield, Jan 06 2021
Sequence in context: A169845 A302972 A115146 * A029844 A000730 A160534
KEYWORD
nonn,tabf
AUTHOR
Jianing Song, Jan 04 2021
EXTENSIONS
More terms from Andrew Howroyd and Jon E. Schoenfield.
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)