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

Author

Andrew Howroyd, Aug 12 2017

Keywords

• nonn

Comments

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

Links

• Eric Weisstein's World of Mathematics, Dominating Set
• Eric Weisstein's World of Mathematics, Johnson Graph
• Eric Weisstein's World of Mathematics, Triangular Graph

Crossrefs

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

Programs

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

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

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