A290716 Number of minimal dominating sets in the n-triangular (Johnson) graph.

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

Author

Eric W. Weisstein, Aug 09 2017

Keywords

• nonn

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

• Vincenzo Librandi, Table of n, a(n) for n = 0..100
• 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

Crossrefs

Cf. A001147, A053530, A290847.

Programs

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 *)

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

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

Extensions

a(8)-a(24) from formula by Andrew Howroyd, Aug 13 2017

a(0)-a(1) prepended by Andrew Howroyd, Apr 21 2018