This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A373436 #31 Jul 01 2024 13:13:09
%S A373436 1,1,2,2,1,3,6,3,1,4,12,12,8,2,5,20,30,25,10,2,6,30,60,66,42,12,2,7,
%T A373436 42,105,147,126,63,21,3,8,56,168,288,312,216,96,24,3,9,72,252,513,675,
%U A373436 594,351,135,27,3,10,90,360,850,1320,1410,1050,540,180,40,4
%N A373436 Triangle read by rows: T(n,k) is the sum of domination numbers of spanning subgraphs with k edges in the n-cycle graph.
%C A373436 From A365327(domination number k replaced by m, function T replaced by F) we have the average domination number given by (Sum_{m=1..n} m*F(n,m))/2^n.
%C A373436 In this case, each subgraph has the same probability, or each edge in the subgraph has a probability of occurrence p = 0.5.
%C A373436 The probability of the subgraph with k edges, where the occurrence of the edge has a probability p is p^k*(1-p)^(n-k).
%C A373436 If we want to vary with this probability and calculate the average value of the domination number, then we have to split the subgraphs according to the number of edges.
%C A373436 By this probability, we weigh the domination number over all subgraphs and then the average domination number is given by Sum_{k=0..n} (p^k*(1-p)^(n-k)*(Sum_{m=1..n} m*F(n,m,k))).
%C A373436 Here F(n,m,k) is a number of subgraphs of the n-cycle graph with k edges and domination number m.
%C A373436 So we need a three-dimensional table for the numbers of subgraphs now.
%C A373436 We can reduce this dimensionality by precalculating the sum of domination numbers of spanning subgraphs with k edges in the n-cycle graph.
%C A373436 Now we get E(n,p) = Sum_{k=0..n} (p^k*(1-p)^(n-k)*(T(n,k))), where T(n,k) = Sum_{m=1..n} m*F(n,m,k).
%C A373436 We used R package Ryacas to simplify equations for each n, see the FORMULA.
%C A373436 Also, we can conclude (Sum_{m=1..n} m*F(n,m))/2^n = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n for p = 0.5.
%H A373436 Paolo Xausa, <a href="/A373436/b373436.txt">Table of n, a(n) for n = 1..11475</a> (rows 1..150 of the triangle, flattened).
%F A373436 T(n,k) = n for k = 0.
%F A373436 T(n,k) = n*(T(n-1,k)+T(n-1,k-1))/(n-1) for 0 < k < n-1.
%F A373436 T(n,k) = n*ceiling(n/3) for k = n-1.
%F A373436 T(n,k) = ceiling(n/3) for k = n.
%F A373436 Average value of the domination number E(n,p) = Sum_{k=0..n} (p^k*(1-p)^(n-k)*(T(n,k))).
%F A373436 E(1,p) = 1*p^0*(1-p)^1 + 1*p^1*(1-p)^0 = 1 - 1*p + p^1 = 1.
%F A373436 E(2,p) = 2*p^0*(1-p)^2 + 2*p^1*(1-p)^1 + 1*p^2*(1-p)^0 = 2 - 2*p + p^2.
%F A373436 E(3,p) = 3*p^0*(1-p)^3 + 6*p^1*(1-p)^2 + 3*p^2*(1-p)^1 + 1*p^3*(1-p)^0 = 3 - 3*p + p^3.
%F A373436 E(4,p) = 4*(1-p)^4 + 12*p*(1-p)^3 + 12*p^2*(1-p)^2 + 8*p^3*(1-p) + 2*p^4 = 4 - 4*p + 4*p^3 - 4*p^4 + 2*p^4.
%F A373436 E(5,p) = 5 - 5*p + 5*p^3 - 5*p^4 + 2*p^5.
%F A373436 E(6,p) = 6 - 6*p + 6*p^3 - 6*p^4 + 2*p^6.
%F A373436 E(7,p) = 7 - 7*p + 7*p^3 - 7*p^4 + 7*p^6 - 7*p^7 + 3*p^7.
%F A373436 E(8,p) = 8 - 8*p + 8*p^3 - 8*p^4 + 8*p^6 - 8*p^7 + 3*p^8.
%F A373436 E(9,p) = 9 - 9*p + 9*p^3 - 9*p^4 + 9*p^6 - 9*p^7 + 3*p^9.
%F A373436 E(10,p) = 10 - 10*p + 10*p^3 - 10*p^4 + 10*p^6 - 10*p^7 + 10*p^9 - 10*p^10 + 4*p^10.
%F A373436 We can see a pattern:
%F A373436 E(n,p) = n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i)) - n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i+1)) + ceiling(n/3)*p^n.
%F A373436 n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i)) = n*(1-p^(3*ceiling(n/3)))/(1-p^3) = n*(1-p^(3*ceiling(n/3)))/((1-p)*(p^2+p+1)).
%F A373436 n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i+1)) = n*p*(1-p^(3*ceiling(n/3)))/((1-p)*(p^2+p+1)).
%F A373436 n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i)) - n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i+1)) = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1).
%F A373436 E(n,p) = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n.
%F A373436 E(n,p) = n for p = 0.
%F A373436 E(n,p) = ceiling(n/3) for p = 1.
%F A373436 Relative average domination number:
%F A373436 E'(n,p) = E(n,p)/n.
%F A373436 E'(n,p) = (1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n/n.
%F A373436 Limit_{n->oo} E'(n,p) = lim_{n->oo} (1-p^(3*ceiling(n/3)))/(p^2+p+1) + lim_{n->oo} ceiling(n/3)*p^n/n = 1/(p^2+p+1).
%F A373436 Limit_{n->oo} E'(n,0) = 1.
%F A373436 Limit_{n->oo} E'(n,0.5) = 4/7.
%F A373436 Limit_{n->oo} E'(n,1) = 1/3.
%e A373436 Example of spanning subgraphs of cycle with 2 vertices:
%e A373436 Domination number: 2 1 1 1
%e A373436 /\ /\
%e A373436 . . . . . . . .
%e A373436 \/ \/
%e A373436 Number of edges: 0 1 1 2
%e A373436 Number of spanning subgraphs with k edges and domination number m in cycle with n = 3 vertices:
%e A373436 k\m 1 2 3
%e A373436 0 0 0 1
%e A373436 1 0 3 0
%e A373436 2 3 0 0
%e A373436 3 1 0 0
%e A373436 T(3,k) = Sum_{m=1..3} m*F(3,m,k)
%e A373436 T(3,0) = 3, T(3,1) = 6, T(3,2) = 3, T(3,3) = 1
%e A373436 The triangle T(n,k) begins:
%e A373436 n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
%e A373436 1: 1 1
%e A373436 2: 2 2 1
%e A373436 3: 3 6 3 1
%e A373436 4: 4 12 12 8 2
%e A373436 5: 5 20 30 25 10 2
%e A373436 6: 6 30 60 66 42 12 2
%e A373436 7: 7 42 105 147 126 63 21 3
%e A373436 8: 8 56 168 288 312 216 96 24 3
%e A373436 9: 9 72 252 513 675 594 351 135 27 3
%e A373436 10: 10 90 360 850 1320 1410 1050 540 180 40 4
%e A373436 11: 11 110 495 1331 2387 3003 2706 1749 792 242 44 4
%e A373436 12: 12 132 660 1992 4056 5880 6228 4860 2772 1128 312 48 4
%t A373436 A373436[n_, k_] := A373436[n, k] = Which[k == 0, n, k < n-1, n*(A373436[n-1, k] + A373436[n-1, k-1])/(n-1), True, Ceiling[n/3]*If[k == n, 1, n]];
%t A373436 Table[A373436[n, k], {n, 10}, {k, 0, n}] (* _Paolo Xausa_, Jul 01 2024 *)
%Y A373436 Cf. A365327.
%K A373436 nonn,tabf
%O A373436 1,3
%A A373436 _Roman Hros_, Jun 22 2024