login
The OEIS is supported by the many generous donors to the OEIS 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 * 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 23 03:40 EDT 2023. Contains 361434 sequences. (Running on oeis4.)