Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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