login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of maximum matchings in the n-triangular graph.
1

%I #21 Jan 14 2018 03:57:14

%S 1,3,8,144,47520,16656192,3321907200,21173194506240,

%T 7866775374741504000,1714731229742768455680000,

%U 149617202324844553489612800000,1023015704130692419403265343488000000,822671651496871196689402715812984258560000000,267398413297417500827783894166564037306456473600000000

%N Number of maximum matchings in the n-triangular graph.

%H Eric W. Weisstein, <a href="/A297565/b297565.txt">Table of n, a(n) for n = 2..18</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumIndependentEdgeSet.html">Maximum Independent Edge Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TriangularGraph.html">Triangular Graph</a>

%o (PARI)

%o \\ groups all orientations of n-complete graph by out degree configuration.

%o CompleteOrientationsByOutDegrees(n)={ \\ high memory usage and slow for n > 10

%o local(M=Map());

%o my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));

%o 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))));

%o my(iterate(v, k, f)=for(i=1, k, v=f(v)); v);

%o 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))

%o }

%o a(n)={

%o my(v=vector(n\2, n, (2*n)!/(2^n*n!)));

%o 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))));

%o my(M=CompleteOrientationsByOutDegrees(n-1));

%o sum(i=1, matsize(M)[1], M[i, 2]*c(M[i, 1]))

%o } \\ _Andrew Howroyd_, Jan 02 2018

%Y Cf. A287231, A297484.

%K nonn

%O 2,2

%A _Eric W. Weisstein_, Dec 31 2017

%E a(10)-a(15) and offset corrected by _Andrew Howroyd_, Jan 02 2018

%E a(16)-a(18) from _Eric W. Weisstein_, Jan 06-08 2018