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).
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
KEYWORD
nonn
AUTHOR
Brendan McKay, May 13 2022
STATUS
approved