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,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

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

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

Cf. A001147, A053530, A290847.

Sequence in context: A187787 A290717 A019009 * A347998 A162441 A001803

Adjacent sequences: A290713 A290714 A290715 * A290717 A290718 A290719

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