

A340312


Triangle read by rows: T(n,k) is the number of subsets of {0..2^n1} with k elements such that the bitwisexor 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 bitwisexor of all the subset members zero. There are in total 2^(2^n  n) such subsets of {0, 1, ..., 2^n1}, 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^nk) for k = 0..2^n, since if the bitwisexor of the members in S is zero, then the complement of S in {0, 1, ..., 2^n1} also has this property.


LINKS



FORMULA

T(n, k) = [x^k] p(n; x) where p(n; x) = (x + 1)^c*(b(n1)  (c1)*a(n2)), 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^(n1), 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
First take any subset of k1 elements and append the bitwisexor 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,k2) with binomial(2^n,k1).
T(n, k) = (1/k)*(binomial(2^n,k1)  (2^n(k2))*T(n,k2)) 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)*(11/2^n)*binomial(2^(n1), k/2) for even k.
T(n, k) = [x^k] ((1+x)^(2^n) + (2^n1)*(1x^2)^(2^(n1)))/2^n.
(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 bitwisexor of all the elements in the empty set is the identity of bitwisexor (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^n1)*(2^n2), and the total number of subsets {a, b, c} is (2^n1)*(2^n2)/3! = A006095(n).
T(n,4) = A016290(n2): 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^n1)*(2^n2), and the total number of subsets {a, b, c, d} is 2^n*(2^n1)*(2^n2)/4! = A016290(n2).


MAPLE

A340312_row := proc(n) local a, b, c; c := 2^(n1);
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(n1)  (c1)*a(n2));
[seq(coeff(expand(%), x, j), j = 0..2*c)] end:


MATHEMATICA

T[n_, k_] := Binomial[2^n, k]/2^n + If[EvenQ[k], (1)^(k/2)*(11/2^n)* Binomial[2^(n1), k/2], 0];


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)*(11/2^n)*binomial(2^(n1), k/2))} \\ Andrew Howroyd, Jan 09 2021
(SageMath)
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):


CROSSREFS

Cf. A340263 (irreducible (?) factor if T(n,k) is seen as representing polynomials).
Cf. A340259(n) = T(n, 2^(n1)), the central term of row n.
Cf. A340030 (case that only nonzero elements allowed).


KEYWORD

nonn,tabf


AUTHOR



EXTENSIONS



STATUS

approved



