A353996 Rooted simple digraphs on n unlabeled vertices.

1, 4, 36, 752, 45960, 9133760, 6154473664, 14334221970688, 117222686206799936, 3412369204476033220608, 357745172369222114451432448, 136400229481294592916607770361856, 190697841181900458854914389940360337408

Offset

1,2

Comments

Loops and parallel edges are not permitted.

There are four ways that a vertex other than the root can be joined to the root: only towards, only away, both, neither. Remove the root and color the remaining vertices by four colors corresponding to how they were joined to the root. This gives a bijection with 4-colored digraphs on n-1 vertices, which is A329874(n-1,4).

Links

Table of n, a(n) for n=1..13.

Formula

a(n) = A329874(n-1,4).

Maple

with(Iterator):
RootedDig := proc(n)
        local i, j, ptn, ans, a, orb2, orb4, hasptn, nextptn;
   (hasptn, nextptn) := ModuleIterator(PartitionPartCount(n-1));
   ans := 0;
   while hasptn() do
      ptn := nextptn();
      a := 1 / mul(j^ptn[j]*ptn[j]!, j=1..n-1);
      orb2 := add(ptn[j], j=2..n-1, 2);
      orb4 := add(ptn[j]*j/2, j=2..n-1, 2)
         + add(ptn[j]*(j+1)/2, j=1..n-1, 2)
         + add(ptn[j]*(ptn[j]-1)*j/2, j=1..n-1)
         + add(add(ptn[i]*ptn[j]*igcd(i, j), i=1..j-1), j=2..n-1);
      ans := ans + a*2^orb2*4^orb4;
   end do;
   ans;
end proc;

Crossrefs

Cf. A329874.

Sequence in context: A360903 A214669 A126152 * A009446 A134052 A127901

Adjacent sequences: A353993 A353994 A353995 * A353997 A353998 A353999

Keyword

nonn

Author

Brendan McKay, May 13 2022

Status

approved