A290847 Number of dominating sets in the n-triangular graph.

1, 7, 57, 973, 32057, 2079427, 267620753, 68649126489, 35172776136145, 36025104013571583, 73784683970720501897, 302228664636911612364581, 2475873390079769597467385417, 40564787539999607393632514635067, 1329227699017403425105119604848703905

Offset

2,2

Comments

A dominating set on the triangular graph corresponds with an edge cover on the complete graph with optionally one vertex removed.

Links

Table of n, a(n) for n=2..16.

Eric Weisstein's World of Mathematics, Dominating Set

Eric Weisstein's World of Mathematics, Johnson Graph

Eric Weisstein's World of Mathematics, Triangular Graph

Formula

a(n) = A006129(n) + n * A006129(n-1).

a(n) = 2^binomial(n,2) - Sum_{k=2..n} binomial(n,k)*A006129(n-k).

Mathematica

b[n_]:=Sum[(-1)^(n - k)*Binomial[n, k]*2^Binomial[k, 2], {k, 0, n}]; a[n_]:=b[n] + n*b[n - 1]; Table[a[n], {n, 2, 20}] (* Indranil Ghosh, Aug 12 2017 *)

Prog

(PARI) \\ here b(n) is A006129
b(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2));
a(n) = b(n) + n*b(n-1);
(Python)
from sympy import binomial
def b(n): return sum((-1)**(n - k)*binomial(n, k)*2**binomial(k, 2) for k in range(n + 1))
def a(n): return b(n) + n*b(n - 1)
print([a(n) for n in range(2, 21)]) # Indranil Ghosh, Aug 13 2017

Crossrefs

Cf. A000085, A006129, A193154, A287231, A287689, A290056, A290716.

Sequence in context: A337022 A316442 A289876 * A324420 A225160 A219974

Adjacent sequences: A290844 A290845 A290846 * A290848 A290849 A290850

Keyword

nonn

Author

Andrew Howroyd, Aug 12 2017

Status

approved