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

%I #44 Feb 20 2021 04:48:32

%S 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,

%T 160,240,195,120,96,60,15,1,0,0,35,105,252,805,1935,3255,4515,5481,

%U 5481,4515,3255,1935,805,252,105,35,0,0,1,1,0,0,56,210,672,2800,9320,24087

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

%C From _Petros Hadjicostas_, Feb 18 2021: (Start)

%C 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.

%C 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.

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

%C For a discussion about the confusion in defining Euler graphs, see the comments for A058878. (End)

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

%H Andrew Howroyd, <a href="/A054669/b054669.txt">Table of n, a(n) for n = 0..1295</a>

%H P. J. Cameron, <a href="https://doi.org/10.1007/BF01215145">Cohomological aspects of two-graphs</a>, Math. Zeit., 157 (1977), 101-119. [See pp. 116-117, where he uses the informal term "labelled Eulerian graph" for "labelled even graph".]

%H math.stackexchange.com, <a href="https://math.stackexchange.com/questions/1414667/is-it-possible-disconnected-graph-has-euler-circuit">Is it possible disconnected graph has euler circuit? [sic]</a>, August 30, 2015.

%H Ronald C. Read, <a href="https://doi.org/10.4153/CJM-1962-039-0">Euler graphs on labelled nodes</a>, Canadian Journal of Mathematics, 14 (1962), 482-486.

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

%F From _Petros Hadjicostas_, Feb 18 2021: (Start)

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

%F T(n, n*(n-1)/2) = 1 if n is odd.

%F T(n, n*(n-2)/2) = A001147(n/2) if n is even.

%F T(n,k) = A058878(n,k) for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2. (End)

%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1-[0==n mod 2])/2 begins:

%e 1;

%e 1;

%e 1;

%e 1, 0, 0, 1;

%e 1, 0, 0, 4, 3;

%e 1, 0, 0, 10, 15, 12, 15, 10, 0, 0, 1;

%e 1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15;

%e ...

%p CoeffList := p -> op(PolynomialTools:-CoefficientList(p, x)):

%p w := p -> factor(2^(-p)*(1 + x)^(p*(p - 1)/2)*

%p add(binomial(p, n)*((1 - x)/(1 + x))^(n*(p - n)), n=0..p)):

%p seq(print(CoeffList(w(n))), n = 0..6); # _Peter Luschny_, Feb 18 2021

%t 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 T /@ Range[0, 8] // Flatten (* _Jean-François Alcover_, Feb 20 2021, after _Andrew Howroyd_ *)

%o (PARI) 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

%Y Row sums are A006125(n-1).

%Y Essentially the same table as A058878.

%Y Cf. A001147, A033678, A340312.

%K easy,nonn,tabf

%O 0,11

%A _Vladeta Jovovic_, Apr 18 2000

%E T(0,0) = 1 prepended by _Andrew Howroyd_, Jan 09 2021

%E Name edited by _Petros Hadjicostas_, Feb 18 2021

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 07:41 EDT 2024. Contains 370958 sequences. (Running on oeis4.)