login
A287231
Number of matchings in the n-triangular graph.
2
1, 4, 51, 2460, 513619, 509709696, 2590569730617, 71972142178289680, 11572569464349559854105, 11332749125368045400133079296, 70775590368575601248957366910425851, 2939823814188321813975498471683171002746816, 844162736935477006294039214093750952242356035727995, 1736712038520659436678773853448507425382701807453031820800000
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
Sequence in context: A220282 A235326 A210834 * A289708 A000516 A182044
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