login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 * A162441 A001803 A161738

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 05:33 EDT 2020. Contains 336438 sequences. (Running on oeis4.)