OFFSET
2,2
LINKS
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Triangular Graph
PROG
(PARI)
\\ groups all labeled oriented graphs on n vertices by out degree configuration.
OrientedByOutDegrees(n)={ \\ high memory usage and slow for n > 10
local(M=Map());
my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
my(recurse(p, i, q, v, e)=if(i<0, for(k=0, e, acc(x^k+q, binomial(e, k)*v)), my(t=polcoeff(p, i)); for(k=0, t, self()(p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+t-k))));
my(iterate(v, k, f)=for(i=1, k, v=f(v)); v);
iterate(Mat([1, 1]), n-1, src->M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(p, poldegree(p), 0, src[i, 2], 0)); Mat(M))
}
a(n)={
my(v=vector(n\2, n, (2*n)!/(2^n*n!)));
my(c(p)=my(h=(poldegree(p)+1)\2); my(r=n-1-sum(i=1, h, polcoeff(p, 2*i-1))); (1+sum(i=1, r\2, binomial(r, 2*i)*v[i]))*prod(i=1, h, v[i]^(polcoeff(p, 2*i)+polcoeff(p, 2*i-1))));
my(M=OrientedByOutDegrees(n-1));
sum(i=1, matsize(M)[1], M[i, 2]*c(M[i, 1]))
} \\ Andrew Howroyd, Aug 25 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, May 22 2017
EXTENSIONS
a(9)-a(12) from Andrew Howroyd, Aug 25 2017
a(13)-a(14) from Eric W. Weisstein, Oct 01 2017
a(15) from Eric W. Weisstein, Oct 15 2017
STATUS
approved