The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 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 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. 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() A340312_row = A340312() 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. A054669, A058878. 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 Adjacent sequences: A340309 A340310 A340311 * A340313 A340314 A340315 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.

Last modified May 25 09:23 EDT 2024. Contains 372786 sequences. (Running on oeis4.)