A340263 -id:A340263 - cp's OEIS frontend

A340030 Triangle read by rows: T(n,k) is the number of hypergraphs on n labeled vertices with k edges and all vertices having even degree, 0 <= k < 2^n.

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 7, 7, 0, 0, 1, 1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1, 1, 0, 0, 155, 1085, 5208, 22568, 82615, 247845, 628680, 1383096, 2648919, 4414865, 6440560, 8280720, 9398115, 9398115, 8280720, 6440560, 4414865, 2648919, 1383096, 628680, 247845, 82615, 22568, 5208, 1085, 155, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 09 2021

Hypergraphs are graphs in which an edge is connected to a nonempty subset of vertices rather than exactly two of them. An edge is a nonempty subset of vertices.
Equivalently, T(n,k) is the number of subsets of {1..2^n-1} with k elements such that the bitwise-xor of the elements is zero.
Also the coefficients of polynomials p_{n}(x) which have the representation
  p_{n}(x) = (x + 1)^(2*(n - 1) - 1)*q_{n - 1}(x), where q_{n}(x) are the polynomials defined in A340263, and n >= 2. - Peter Luschny, Jan 10 2021

			Triangle begins:
[0]  1;
[1]  1, 0;
[2]  1, 0, 0,  1;
[3]  1, 0, 0,  7,   7,   0,   0,   1;
[4]  1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..2046 (rows 0..10)
Wikipedia, Hypergraph.

Rows 3..8 are A002394, A010085, A010086, A010087, A010088, A010089.
Row sums are A016031(n+1).
Column k=3 gives A006095.
Cf. A058878, A281123, A340312, A340263.

T(n,k) = {(binomial(2^n-1, k) + (-1)^((k+1)\2)*(2^n-1)*binomial(2^(n-1)-1, k\2))/2^n}
{ for(n=0, 5, print(vector(2^n, k, T(n,k-1)))) }

T(n,k) = (binomial(2^n-1, k) + (-1)^ceiling(k/2)*(2^n-1)*binomial(2^(n-1)-1, floor(k/2)))/2^n.
T(n,2*k) + T(n,2*k+1) = binomial(2^n-1, k)/2^n = A281123(n,k).
T(n, k) = T(n, 2^n-1-k) for n >= 2.

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.

Original entry on oeis.org

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

Offset: 0

Jianing Song, Jan 04 2021

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.

			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).

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

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

/* Generating program for T(4,k), see link. */

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

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 *)

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

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

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)

More terms from Andrew Howroyd and Jon E. Schoenfield.

A340259 a(n) = A340312(n, 2^(n-1)). a(n) is the central term of row n of A340312.

Original entry on oeis.org

1, 0, 14, 870, 18796230, 28634752793916486, 187118328452563149209991044344449606, 22533823529098462258163079522899558179092788838542277982316450977506091590

Offset: 1

Peter Luschny, Jan 06 2021

nonn

a(9) = 2299131884087642202247291403507120751687796592498104258 * C, where C is a composite factor with 96 digits.
C = P47*P49, with P47 = 88967307877356450624418823383132738084943851019 and
P49 = 4512180962860489443011495305279720577473472225641. - Hugo Pfoertner, Jan 09 2021

Andrew Howroyd, Table of n, a(n) for n = 1..11

Cf. A340312, A340263.

seq(A340312_row(n)[2^(n-1)+1], n = 1..8);

a(n) = {if(n<=2, n==1, (2*binomial(2^n-1, 2^(n-1)) + (2^n-1)*binomial(2^(n-1), 2^(n-2)))/2^n)} \\ Andrew Howroyd, Jan 09 2021

a(n) = (2*binomial(2^n-1, 2^(n-1)) + (2^n-1)*binomial(2^(n-1), 2^(n-2)))/2^n for n >= 3. - Andrew Howroyd, Jan 09 2021

A340555 T(n, k) = [x^k] (2^n-1)2^(-n-1)((x+1)^(2^n) - (x-1)^(2^n)). Irregular triangle read by rows, for n >= 0 and 0 <= k <= 2^n.

Original entry on oeis.org

0, 0, 1, 0, 0, 3, 0, 3, 0, 0, 7, 0, 49, 0, 49, 0, 7, 0, 0, 15, 0, 525, 0, 4095, 0, 10725, 0, 10725, 0, 4095, 0, 525, 0, 15, 0, 0, 31, 0, 4805, 0, 195083, 0, 3260673, 0, 27172275, 0, 124992465, 0, 336518175, 0, 548043885, 0, 548043885, 0, 336518175, 0, 124992465, 0, 27172275, 0, 3260673, 0, 195083, 0, 4805, 0, 31, 0

Offset: 0

Peter Luschny, Jan 11 2021

			Triangle begins:
[0] [0]
[1] [0, 1, 0]
[2] [0, 3, 0, 3, 0]
[3] [0, 7, 0, 49, 0, 49, 0, 7, 0]
[4] [0, 15, 0, 525, 0, 4095, 0, 10725, 0, 10725, 0, 4095, 0, 525, 0, 15, 0]
[5] [0, 31, 0, 4805, 0, 195083, 0, 3260673, 0, 27172275, 0, 124992465, 0, 336518175, 0, 548043885, 0, 548043885, 0, 336518175, 0, 124992465, 0, 27172275, 0, 3260673, 0, 195083, 0, 4805, 0, 31, 0]

Cf. A340263.

CoeffList := p -> [op(PolynomialTools:-CoefficientList(p, x)),0]:
Tpoly := proc(n) (2^n-1)*2^(-n-1)*((x+1)^(2^n) - (x-1)^(2^n)) end:
seq(print(CoeffList(Tpoly(n))), n=0..5);

def A340555():
    a, b, c = 1, 1, 1
    yield [0]
    while True:
        c *= 2
        a *= b
        b = sum(binomial(c, 2 * k) * x ^ (2 * k) for k in range(c + 1))
        q = ((b - (c - 1) * x * a)).list()
        yield [-q[i] * (i % 2) for i in range(c + 1)]
A340555_row = A340555()
for _ in range(6):
    print(next(A340555_row))

A340555(n, k) = -A340263(n, k) * (k mod 2).

cp's OEIS Frontend

A340030 Triangle read by rows: T(n,k) is the number of hypergraphs on n labeled vertices with k edges and all vertices having even degree, 0 <= k < 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A340259 a(n) = A340312(n, 2^(n-1)). a(n) is the central term of row n of A340312.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A340555 T(n, k) = [x^k] (2^n-1)*2^(-n-1)*((x+1)^(2^n) - (x-1)^(2^n)). Irregular triangle read by rows, for n >= 0 and 0 <= k <= 2^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

SageMath

Formula

A340555 T(n, k) = [x^k] (2^n-1)2^(-n-1)((x+1)^(2^n) - (x-1)^(2^n)). Irregular triangle read by rows, for n >= 0 and 0 <= k <= 2^n.