The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #33 Jul 20 2024 09:02:31
%S 2,3,1,4,3,1,0,11,4,1,0,11,15,5,1,0,10,26,21,6,1,0,0,43,49,28,7,1,0,0,
%T 33,98,80,36,8,1,0,0,22,126,189,120,45,9,1,0,0,0,141,322,325,170,55,
%U 10,1,0,0,0,89,462,671,517,231,66,11,1,0,0,0,46,480,1162,1236,777,304,78,12,1,0,0,0,0,417,1586,2483,2093,1118,390,91,13,1
%N Triangle read by rows: T(n,k) is the number of spanning subgraphs of the n-cycle graph with domination number k.
%C For n >= 3 the n-cycle graph is a simple graph. In the case of n=1 the graph is a loop and for n=2 a double edge.
%C The number of spanning subgraphs of the n-cycle graph is given by 2^n which is also the sum of the n-th row Sum_{k=1..n} T(n,k).
%C The average domination number is given by (Sum_{k=1..n} k*T(n,k))/2^n.
%C The relative average domination number is given by ((Sum_{k=1..n} k*T(n,k))/2^n)/n.
%H Roman Hros, <a href="/A365327/b365327.txt">Table of n, a(n) for n = 1..253 (Rows n = 1..22)</a>
%H Roman Hros, <a href="http://www2.fiit.stuba.sk/iitsrc/iit-src2020-proceedings.pdf#page=66">Effective Enumeration of Selected Graph Characteristics</a>, IIT.SRC 2020: 16th Student Research Conference in Informatics and Information Technologies.
%F T(n,n) = 1 for n > 1.
%F T(n,n-1) = T(n-1, n-2) + 1 for n > 3.
%F T(n,n-2) = T(n-1, n-3) + T(n, n-1) for n > 5.
%F T(n,n-3) = T(n-1, n-4) + T(n, n-2) - 5 for n > 6.
%F T(n,n-4) = T(n-1, n-5) + T(n-1, n-4) + 11 + Sum_{i=1..n-9} (i+4) for n > 8.
%F G.f.:
%F For n > 3; G(n) = x*(G(n-1) + G(n-2) + 2*G(n-3)) + g(n); where
%F 2*(1-x)*x^(n/3) for n mod 3 = 0.
%F g(n) = { 0 for n mod 3 = 1.
%F (1-x)*x^((n+1)/3) for n mod 3 = 2.
%F For n mod 3 = 0:
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) + 2 for k = n/3.
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) - 2 for k = n/3 + 1.
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) for k >= n/3 + 2.
%F For n mod 3 = 1:
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) for k >= (n+2)/3.
%F For n mod 3 = 2:
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) + 1 for k = (n+1)/3.
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) - 1 for k = (n+1)/3 + 1.
%F T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) for k >= (n+1)/3 + 2.
%e Example of spanning subgraphs of cycle with 2 vertices:
%e Domination number: 2 1 1 1
%e /\ /\
%e . . . . . . . .
%e \/ \/
%e The triangle T(n,k) begins:
%e n\k 1 2 3 4 5 6 7 8 9 10 11 12 ...
%e 1: 2
%e 2: 3 1
%e 3: 4 3 1
%e 4: 0 11 4 1
%e 5: 0 11 15 5 1
%e 6: 0 10 26 21 6 1
%e 7: 0 0 43 49 28 7 1
%e 8: 0 0 33 98 80 36 8 1
%e 9: 0 0 22 126 189 120 45 9 1
%e 10: 0 0 0 141 322 325 170 55 10 1
%e 11: 0 0 0 89 462 671 517 231 66 11 1
%e 12: 0 0 0 46 480 1162 1236 777 304 78 12 1
%Y Row sums are A000079.
%Y Column sums are A002063(k-1).
%Y Cf. A373436.
%K nonn,tabl
%O 1,1
%A _Roman Hros_, Sep 01 2023