A287231 Number of matchings in the n-triangular graph.

1, 4, 51, 2460, 513619, 509709696, 2590569730617, 71972142178289680, 11572569464349559854105, 11332749125368045400133079296, 70775590368575601248957366910425851, 2939823814188321813975498471683171002746816, 844162736935477006294039214093750952242356035727995, 1736712038520659436678773853448507425382701807453031820800000

Offset: 2

Author

Eric W. Weisstein, May 22 2017

Keywords

• nonn

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

Programs

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

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