cp's OEIS Frontend

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

%I A054669 #47 Jan 05 2025 01:23:37
%S A054669 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 A054669 160,240,195,120,96,60,15,1,0,0,35,105,252,805,1935,3255,4515,5481,
%U A054669 5481,4515,3255,1935,805,252,105,35,0,0,1,1,0,0,56,210,672,2800,9320,24087
%N 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).
%C A054669 From _Petros Hadjicostas_, Feb 18 2021: (Start)
%C A054669 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 A054669 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 A054669 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 A054669 For a discussion about the confusion in defining Euler graphs, see the comments for A058878. (End)
%D A054669 F. Harary and E. Palmer, Graphical Enumeration, Academic Press, New York, 1973; pp. 13-15.
%H A054669 Andrew Howroyd, <a href="/A054669/b054669.txt">Table of n, a(n) for n = 0..1295</a>
%H A054669 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 A054669 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 A054669 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 A054669 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 A054669 From _Petros Hadjicostas_, Feb 18 2021: (Start)
%F A054669 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 A054669 T(n, n*(n-1)/2) = 1 if n is odd.
%F A054669 T(n, n*(n-2)/2) = A001147(n/2) if n is even.
%F A054669 T(n,k) = A058878(n,k) for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2. (End)
%e A054669 Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1-[0==n mod 2])/2) begins:
%e A054669   1;
%e A054669   1;
%e A054669   1;
%e A054669   1, 0, 0,  1;
%e A054669   1, 0, 0,  4,  3;
%e A054669   1, 0, 0, 10, 15, 12,  15,  10,   0,   0,  1;
%e A054669   1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15;
%e A054669   ...
%p A054669 CoeffList := p -> op(PolynomialTools:-CoefficientList(p, x)):
%p A054669 w := p -> factor(2^(-p)*(1 + x)^(p*(p - 1)/2)*
%p A054669           add(binomial(p, n)*((1 - x)/(1 + x))^(n*(p - n)), n=0..p)):
%p A054669 seq(print(CoeffList(w(n))), n = 0..6); # _Peter Luschny_, Feb 18 2021
%t A054669 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 A054669 T /@ Range[0, 8] // Flatten (* _Jean-François Alcover_, Feb 20 2021, after _Andrew Howroyd_ *)
%o A054669 (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 A054669 Row sums are A006125(n-1).
%Y A054669 Essentially the same table as A058878.
%Y A054669 Cf. A001147, A033678, A340312.
%K A054669 easy,nonn,tabf
%O A054669 0,11
%A A054669 _Vladeta Jovovic_, Apr 18 2000
%E A054669 T(0,0) = 1 prepended by _Andrew Howroyd_, Jan 09 2021
%E A054669 Name edited by _Petros Hadjicostas_, Feb 18 2021