A340312 -id:A340312 - cp's OEIS frontend

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

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

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.

Original entry on oeis.org

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.

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

Original entry on oeis.org

1, 1, -1, 1, 1, -3, 6, -3, 1, 1, -7, 28, -49, 70, -49, 28, -7, 1, 1, -15, 120, -525, 1820, -4095, 8008, -10725, 12870, -10725, 8008, -4095, 1820, -525, 120, -15, 1

Offset: 0

Peter Luschny, Jan 06 2021

Conjecture: for n >= 1 the polynomials are irreducible.

			Polynomials begin:
[0] 1;
[1] x^2 - x + 1;
[2] x^4 - 3*x^3 + 6*x^2 - 3*x + 1;
[3] x^8 - 7*x^7 + 28*x^6 - 49*x^5 + 70*x^4 - 49*x^3 + 28*x^2 - 7*x + 1;
Triangle begins:
[0] [1]
[1] [1, -1, 1]
[2] [1, -3, 6, -3, 1]
[3] [1, -7, 28, -49, 70, -49, 28, -7, 1]
[4] [1, -15, 120, -525, 1820, -4095, 8008, -10725, 12870, -10725, 8008, -4095, 1820, -525, 120, -15, 1]

Peter Luschny, Table of n, a(n) for n = 0..1031

Row sums are 2^(2^n - n - 1) = A016031(n-1).
Central terms of the rows are A037293(n) for n >= 2.
Cf. A340312.

A340263_row := proc(n) local a, b;
if n = 0 then return [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);
expand(b(n) - (2^n-1)*a(n-1));
[seq(coeff(%, x, j), j = 0..2^n)] end:
for n from 0 to 5 do A340263_row(n) od;
# Alternatively:
CoeffList := p -> [op(PolynomialTools:-CoefficientList(p, x))]:
Tpoly := n -> ((1-x)^(2^n) + 2^(-n)*((2^n-1)*(x-1)^(2^n) + (x + 1)^(2^n)))/2:
seq(print(CoeffList(Tpoly(n))), n=0..5); # Peter Luschny, Feb 03 2021

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

Let p_n(x) = b(n) - (2^n-1)*a(n-1), b(n) = Sum_{k=0..2^n} binomial(2^n, 2*k)* x^(2*k), and a(n) = x*Product_{k=0..n} b(k). Then T(n, k) = [x^k] p_n(x).

Shorter name by Peter Luschny, Feb 03 2021

A362905 Array read by antidiagonals: T(n,k) is the number of n element multisets of length k vectors over GF(2) that sum to zero.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 8, 5, 3, 1, 1, 1, 16, 15, 11, 3, 1, 1, 1, 32, 51, 50, 14, 4, 1, 1, 1, 64, 187, 276, 99, 24, 4, 1, 1, 1, 128, 715, 1768, 969, 232, 30, 5, 1, 1, 1, 256, 2795, 12496, 11781, 3504, 429, 45, 5, 1, 1, 1, 512, 11051, 93600, 162877, 73440, 10659, 835, 55, 6, 1

Offset: 0

Andrew Howroyd, May 27 2023

Equivalently, T(n,k) is the number multisets with n elements drawn from {0..2^k-1} such that the bitwise-xor of all the elements gives zero.
T(n,k) is the number of equivalence classes of n X k binary matrices with an even number of 1's in each column under permutation of rows.
T(n,k) is the number of equivalence classes of n X k binary matrices under permutation of rows and complementation of columns.

			Array begins:
=========================================
n/k| 0 1  2   3     4      5        6 ...
---+-------------------------------------
0  | 1 1  1   1     1      1        1 ...
1  | 1 1  1   1     1      1        1 ...
2  | 1 2  4   8    16     32       64 ...
3  | 1 2  5  15    51    187      715 ...
4  | 1 3 11  50   276   1768    12496 ...
5  | 1 3 14  99   969  11781   162877 ...
6  | 1 4 24 232  3504  73440  1878976 ...
7  | 1 4 30 429 10659 394383 18730855 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).

Columns k=0..4 are A000012, A004526(n+2), A053307, A362906, A363350.
Rows n=2..3 are A000079, A007581.
Main diagonal is A363351.
Cf. A054724, A340030, A340312, A363349.

A362905[n_,k_]:=(Binomial[2^k+n-1,n]+If[EvenQ[n],(2^k-1)Binomial[2^(k-1)+n/2-1,n/2],0])/2^k;Table[A362905[n-k,k],{n,0,15},{k,n,0,-1}] (* Paolo Xausa, Nov 19 2023 *)

T(n,k)={(binomial(2^k+n-1, n) + if(n%2==0, (2^k-1)*binomial(2^(k-1)+n/2-1,n/2)))/2^k}

T(n,k) = binomial(2^k+n-1, n)/2^k for odd n;
T(n,k) = (binomial(2^k+n-1, n) + (2^k-1)*binomial(2^(k-1)+n/2-1, n/2))/2^k for even n.
G.f. of column k: (1/(1-x)^(2^k) + (2^k-1)/(1-x^2)^(2^(k-1)))/2^k.

A054669 Triangular array T(n,k) giving the number of labeled even graphs with n nodes and k edges for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2 (with no trailing zeros).

Original entry on oeis.org

1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 4, 3, 1, 0, 0, 10, 15, 12, 15, 10, 0, 0, 1, 1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15, 1, 0, 0, 35, 105, 252, 805, 1935, 3255, 4515, 5481, 5481, 4515, 3255, 1935, 805, 252, 105, 35, 0, 0, 1, 1, 0, 0, 56, 210, 672, 2800, 9320, 24087

Offset: 0

Vladeta Jovovic, Apr 18 2000

From Petros Hadjicostas, Feb 18 2021: (Start)
This is the same as irregular array A058878 but without the (n/2)*[0 == n mod 2] trailing zeros at the end of each row n.
For n odd, we have T(n,n*(n-1)/2) = 1 at end of row n because a complete graph with n nodes and n*(n-1)/2 edges is even and has only one labeling.
For n even, the maximum number of edges an even graph with n nodes can have is n*(n-2)/2 = n*(n-1)/2 - n/2. We have T(n,n*(n-2)/2) = A001147(n/2) because each labeling of an even graph that has n nodes and n*(n-2)/2 edges corresponds to a perfect matching of the complete graph with n vertices (by considering the pairs of vertices that are not connected).
For a discussion about the confusion in defining Euler graphs, see the comments for A058878. (End)

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1-[0==n mod 2])/2) begins:
  1;
  1;
  1;
  1, 0, 0,  1;
  1, 0, 0,  4,  3;
  1, 0, 0, 10, 15, 12,  15,  10,   0,   0,  1;
  1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15;
  ...

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, New York, 1973; pp. 13-15.

Andrew Howroyd, Table of n, a(n) for n = 0..1295
P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119. [See pp. 116-117, where he uses the informal term "labelled Eulerian graph" for "labelled even graph".]
math.stackexchange.com, Is it possible disconnected graph has euler circuit? [sic], August 30, 2015.
Ronald C. Read, Euler graphs on labelled nodes, Canadian Journal of Mathematics, 14 (1962), 482-486.

Row sums are A006125(n-1).
Essentially the same table as A058878.
Cf. A001147, A033678, A340312.

CoeffList := p -> op(PolynomialTools:-CoefficientList(p, x)):
w := p -> factor(2^(-p)*(1 + x)^(p*(p - 1)/2)*
          add(binomial(p, n)*((1 - x)/(1 + x))^(n*(p - n)), n=0..p)):
seq(print(CoeffList(w(n))), n = 0..6); # Peter Luschny, Feb 18 2021

T[n_] := (1/2^n)(1+x)^Binomial[n, 2] Sum[Binomial[n, k] ((1-x)/(1+x))^(k(n-k)), {k, 0, n}] // CoefficientList[#, x]&;
T /@ Range[0, 8] // Flatten (* Jean-François Alcover, Feb 20 2021, after Andrew Howroyd *)

Row(n)=Vecrev(2^(-n)*(1+x)^binomial(n, 2)*sum(k=0, n, binomial(n, k)*((1-x)/(1+x))^(k*(n-k)))) \\ Andrew Howroyd, Jan 05 2021

T(n,k) = [y^k] 2^(-n)*(1+y)^C(n, 2)*Sum_{s=0..n} C(n, s)*((1-y)/(1+y))^(s*(n-s)).
From Petros Hadjicostas, Feb 18 2021: (Start)
T(n,k) = (1/2^n) * Sum_{s=0..n} binomial(n,s) * Sum_{t=0..k} (-1)^t * binomial(s*(n-s), t) * binomial(binomial(s,2) + binomial(n-s, 2), k-t).
T(n, n*(n-1)/2) = 1 if n is odd.
T(n, n*(n-2)/2) = A001147(n/2) if n is even.
T(n,k) = A058878(n,k) for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2. (End)

T(0,0) = 1 prepended by Andrew Howroyd, Jan 09 2021

Name edited by Petros Hadjicostas, Feb 18 2021

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

SageMath

Formula

Extensions

A362905 Array read by antidiagonals: T(n,k) is the number of n element multisets of length k vectors over GF(2) that sum to zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054669 Triangular array T(n,k) giving the number of labeled even graphs with n nodes and k edges for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2 (with no trailing zeros).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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