A199012 - OEIS

%I #20 Jul 05 2024 17:13:22

%S 0,3,48,1308,96080,23114160,18522702240,50214057399744,

%T 469006445678383872,15356719437883766115840,

%U 1788760016178073736115859200,750205198434476437912637004278784,1144188684031608529784893493874665232384,6398724751986384956446081096594171272300830720

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

%F a(n) = A000273(n) * n(n-1)/2.

%F a(n) = Sum_{k=1..n*(n-1)} k*A052283(n,k). - _Andrew Howroyd_, Nov 05 2017

%p b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(

%p       igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),

%p       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))

%p     end:

%p a:= n-> b(n$2, [])*n*(n-1)/2:

%p seq(a(n), n=1..16);  # _Alois P. Heinz_, Sep 04 2019

%t Table[D[GraphPolynomial[n,x,Directed],x]/.x->1, {n,1,15}]

%t (* Second program: *)

%t 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 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 a[n_] := (s = 0; Do[s += permcount[p]*(D[edges[p, 1 + x^# &], x] /. x -> 1), {p, IntegerPartitions[n]}]; s/n!);

%t Array[a, 15] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)

%o (PARI)

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

%o from itertools import combinations

%o from math import prod, factorial, gcd

%o from fractions import Fraction

%o from sympy.utilities.iterables import partitions

%o 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 Cf. A000273, A052283, A086314.

%K nonn

%O 1,2

%A _Geoffrey Critzer_, Nov 01 2011