login
A290716
Number of minimal dominating sets in the n-triangular (Johnson) graph.
5
1, 1, 1, 3, 15, 35, 225, 1197, 6881, 45369, 327375, 2460755, 19925367, 171368067, 1551364997, 14763620445, 147405166785, 1538113071857, 16732908859599, 189413984297187, 2226589748578775, 27130592749003275, 342118450334269917, 4458168165784234253, 59952936723606219009
OFFSET
0,4
COMMENTS
A minimal dominating set on the triangular graph corresponds either with a minimal edge cover on the complete graph minus one vertex or with a perfect matching on the complete graph. Perfect matchings on the complete graph exists only for even n. - Andrew Howroyd, Aug 13 2017
Also the number of maximal irredundant sets in the n-triangular graph. - Eric W. Weisstein, Dec 31 2017
LINKS
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Triangular Graph
FORMULA
a(n) = n*A053530(n-1) for n odd, a(n) = (n-1)!! + n*A053530(n-1) for n even. - Andrew Howroyd, Aug 13 2017
E.g.f.: exp(x^2/2) + x*exp(x*exp(x) - (x+x^2/2)). - Andrew Howroyd, Apr 21 2018
MATHEMATICA
b[n_]:=n! Sum[1/k! (Binomial[k, n - k] 2^(k - n) (-1)^k + Sum[Binomial[k, j] Sum[j^(i - j)/(i - j)! Binomial[k - j, n - i - k + j] 2^(i - j + k - n) (-1)^(k - j), {i, j, n - k + j}], {j, k}]), {k, n}]; Join[{1, 1}, Table[n b[n - 1] + If[Mod[n, 2] == 0, (n - 1)!!, 0], {n, 2, 20}]] (* Eric W. Weisstein, Aug 14 2017 *)
Range[0, 20]! CoefficientList[Series[Exp[x^2/2] + x Exp[x Exp[x] - (x + x^2/2)], {x, 0, 20}], x] (* Eric W. Weisstein, Apr 23 2018 *)
PROG
(PARI) \\ here b(n) is A053530, df(n) is (2*n-1)!! = A001147
b(n)=polcoeff(serlaplace(exp(-x-1/2*x^2+x*exp(x+O(x^(n+1))))), n, x);
df(n)=polcoeff(serlaplace((1-2*x+O(x^(n+1)))^(-1/2)), n, x);
a(n) = n*b(n-1) + if(n%2==0, df(n/2), 0); \\ Andrew Howroyd, Aug 13 2017
(PARI) seq(n)={Vec(serlaplace(exp(x^2/2 + O(x*x^n)) + x*exp(x*exp(x + O(x^n)) - (x+x^2/2))))} \\ Andrew Howroyd, Apr 21 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Aug 09 2017
EXTENSIONS
a(8)-a(24) from formula by Andrew Howroyd, Aug 13 2017
a(0)-a(1) prepended by Andrew Howroyd, Apr 21 2018
STATUS
approved