login
A297565
Number of maximum matchings in the n-triangular graph.
1
1, 3, 8, 144, 47520, 16656192, 3321907200, 21173194506240, 7866775374741504000, 1714731229742768455680000, 149617202324844553489612800000, 1023015704130692419403265343488000000, 822671651496871196689402715812984258560000000, 267398413297417500827783894166564037306456473600000000
OFFSET
2,2
LINKS
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Triangular Graph
PROG
(PARI)
\\ groups all orientations of n-complete graph by out degree configuration.
CompleteOrientationsByOutDegrees(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, acc(x^e+q, 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))); if(r%2, n*r/2, 1)*if(r<2, 1, v[r\2])*prod(i=1, h, v[i]^(polcoeff(p, 2*i)+polcoeff(p, 2*i-1))));
my(M=CompleteOrientationsByOutDegrees(n-1));
sum(i=1, matsize(M)[1], M[i, 2]*c(M[i, 1]))
} \\ Andrew Howroyd, Jan 02 2018
CROSSREFS
Sequence in context: A132491 A083112 A053605 * A289884 A076147 A132563
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Dec 31 2017
EXTENSIONS
a(10)-a(15) and offset corrected by Andrew Howroyd, Jan 02 2018
a(16)-a(18) from Eric W. Weisstein, Jan 06-08 2018
STATUS
approved