login
Number of dominating sets in the n-triangular graph.
4

%I #27 Feb 16 2025 08:33:50

%S 1,7,57,973,32057,2079427,267620753,68649126489,35172776136145,

%T 36025104013571583,73784683970720501897,302228664636911612364581,

%U 2475873390079769597467385417,40564787539999607393632514635067,1329227699017403425105119604848703905

%N Number of dominating sets in the n-triangular graph.

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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/JohnsonGraph.html">Johnson Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TriangularGraph.html">Triangular Graph</a>

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

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

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

%o (PARI) \\ here b(n) is A006129

%o b(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2));

%o a(n) = b(n) + n*b(n-1);

%o (Python)

%o from sympy import binomial

%o def b(n): return sum((-1)**(n - k)*binomial(n, k)*2**binomial(k, 2) for k in range(n + 1))

%o def a(n): return b(n) + n*b(n - 1)

%o print([a(n) for n in range(2, 21)]) # _Indranil Ghosh_, Aug 13 2017

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

%K nonn,changed

%O 2,2

%A _Andrew Howroyd_, Aug 12 2017