cp's OEIS Frontend

A199012 The total number of edges in all unlabeled directed graphs (no self loops allowed) on n nodes.

%I A199012 #20 Jul 05 2024 17:13:22
%S A199012 0,3,48,1308,96080,23114160,18522702240,50214057399744,
%T A199012 469006445678383872,15356719437883766115840,
%U A199012 1788760016178073736115859200,750205198434476437912637004278784,1144188684031608529784893493874665232384,6398724751986384956446081096594171272300830720
%N A199012 The total number of edges in all unlabeled directed graphs (no self loops allowed) on n nodes.
%F A199012 a(n) = A000273(n) * n(n-1)/2.
%F A199012 a(n) = Sum_{k=1..n*(n-1)} k*A052283(n,k). - _Andrew Howroyd_, Nov 05 2017
%p A199012 b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
%p A199012       igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
%p A199012       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
%p A199012     end:
%p A199012 a:= n-> b(n$2, [])*n*(n-1)/2:
%p A199012 seq(a(n), n=1..16);  # _Alois P. Heinz_, Sep 04 2019
%t A199012 Table[D[GraphPolynomial[n,x,Directed],x]/.x->1, {n,1,15}]
%t A199012 (* Second program: *)
%t A199012 permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
%t A199012 edges[v_, t_] := Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^(2*g), {i, 2, Length[v]}, {j, 1, i - 1}] * Product[ t[v[[i]]]^(v[[i]] - 1), {i, 1, Length[v]}]
%t A199012 a[n_] := (s = 0; Do[s += permcount[p]*(D[edges[p, 1 + x^# &], x] /. x -> 1), {p, IntegerPartitions[n]}]; s/n!);
%t A199012 Array[a, 15] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)
%o A199012 (PARI)
%o A199012 permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
%o A199012 edges(v,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^(2*g))) * prod(i=1, #v, t(v[i])^(v[i]-1))}
%o A199012 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*subst(deriv(edges(p,i->1+x^i)),x,1)); s/n!} \\ _Andrew Howroyd_, Nov 05 2017
%o A199012 (Python)
%o A199012 from itertools import combinations
%o A199012 from math import prod, factorial, gcd
%o A199012 from fractions import Fraction
%o A199012 from sympy.utilities.iterables import partitions
%o A199012 def A199012(n): return (n*(n-1)>>1)*int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s)<<1 for r,s in combinations(p.keys(),2))+sum(r*(q*r-1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # _Chai Wah Wu_, Jul 05 2024
%Y A199012 Cf. A000273, A052283, A086314.
%K A199012 nonn
%O A199012 1,2
%A A199012 _Geoffrey Critzer_, Nov 01 2011