A373436 - OEIS

%I #31 Jul 01 2024 13:13:09

%S 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 42,105,147,126,63,21,3,8,56,168,288,312,216,96,24,3,9,72,252,513,675,

%U 594,351,135,27,3,10,90,360,850,1320,1410,1050,540,180,40,4

%N 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 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 In this case, each subgraph has the same probability, or each edge in the subgraph has a probability of occurrence p = 0.5.

%C 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 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 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 Here F(n,m,k) is a number of subgraphs of the n-cycle graph with k edges and domination number m.

%C So we need a three-dimensional table for the numbers of subgraphs now.

%C We can reduce this dimensionality by precalculating the sum of domination numbers of spanning subgraphs with k edges in the n-cycle graph.

%C 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 We used R package Ryacas to simplify equations for each n, see the FORMULA.

%C 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 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 T(n,k) = n for k = 0.

%F T(n,k) = n*(T(n-1,k)+T(n-1,k-1))/(n-1) for 0 < k < n-1.

%F T(n,k) = n*ceiling(n/3) for k = n-1.

%F T(n,k) = ceiling(n/3) for k = n.

%F Average value of the domination number E(n,p) = Sum_{k=0..n} (p^k*(1-p)^(n-k)*(T(n,k))).

%F E(1,p) = 1*p^0*(1-p)^1 + 1*p^1*(1-p)^0 = 1 - 1*p + p^1 = 1.

%F 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 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 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 E(5,p) = 5 - 5*p + 5*p^3 - 5*p^4 + 2*p^5.

%F E(6,p) = 6 - 6*p + 6*p^3 - 6*p^4 + 2*p^6.

%F E(7,p) = 7 - 7*p + 7*p^3 - 7*p^4 + 7*p^6 - 7*p^7 + 3*p^7.

%F E(8,p) = 8 - 8*p + 8*p^3 - 8*p^4 + 8*p^6 - 8*p^7 + 3*p^8.

%F E(9,p) = 9 - 9*p + 9*p^3 - 9*p^4 + 9*p^6 - 9*p^7 + 3*p^9.

%F 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 We can see a pattern:

%F 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 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 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 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 E(n,p) = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n.

%F E(n,p) = n for p = 0.

%F E(n,p) = ceiling(n/3) for p = 1.

%F Relative average domination number:

%F E'(n,p) = E(n,p)/n.

%F E'(n,p) = (1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n/n.

%F 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 Limit_{n->oo} E'(n,0) = 1.

%F Limit_{n->oo} E'(n,0.5) = 4/7.

%F Limit_{n->oo} E'(n,1) = 1/3.

%e Example of spanning subgraphs of cycle with 2 vertices:

%e Domination number: 2      1      1      1

%e                           /\            /\

%e                   .  .   .  .   .  .   .  .

%e                                  \/     \/

%e Number of edges:   0      1      1      2

%e Number of spanning subgraphs with k edges and domination number m in cycle with n = 3 vertices:

%e  k\m 1 2 3

%e  0   0 0 1

%e  1   0 3 0

%e  2   3 0 0

%e  3   1 0 0

%e T(3,k) = Sum_{m=1..3} m*F(3,m,k)

%e T(3,0) = 3, T(3,1) = 6, T(3,2) = 3, T(3,3) = 1

%e The triangle T(n,k) begins:

%e  n\k 0   1   2    3    4    5    6    7    8    9  10  11  12 ...

%e  1:  1   1

%e  2:  2   2   1

%e  3:  3   6   3    1

%e  4:  4  12  12    8    2

%e  5:  5  20  30   25   10    2

%e  6:  6  30  60   66   42   12    2

%e  7:  7  42 105  147  126   63   21    3

%e  8:  8  56 168  288  312  216   96   24    3

%e  9:  9  72 252  513  675  594  351  135   27    3

%e 10: 10  90 360  850 1320 1410 1050  540  180   40   4

%e 11: 11 110 495 1331 2387 3003 2706 1749  792  242  44   4

%e 12: 12 132 660 1992 4056 5880 6228 4860 2772 1128 312  48   4

%t 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 Table[A373436[n, k], {n, 10}, {k, 0, n}] (* _Paolo Xausa_, Jul 01 2024 *)

%Y Cf. A365327.

%K nonn,tabf

%O 1,3

%A _Roman Hros_, Jun 22 2024