login
A290847
Number of dominating sets in the n-triangular graph.
4
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
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
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Aug 12 2017
STATUS
approved