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.

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, 42, 105, 147, 126, 63, 21, 3, 8, 56, 168, 288, 312, 216, 96, 24, 3, 9, 72, 252, 513, 675, 594, 351, 135, 27, 3, 10, 90, 360, 850, 1320, 1410, 1050, 540, 180, 40, 4

Offset: 1

Author

Roman Hros, Jun 22 2024

Keywords

• nonn
• tabf

Comments

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.

In this case, each subgraph has the same probability, or each edge in the subgraph has a probability of occurrence p = 0.5.

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).

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.

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))).

Here F(n,m,k) is a number of subgraphs of the n-cycle graph with k edges and domination number m.

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

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

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).

We used R package Ryacas to simplify equations for each n, see the FORMULA.

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.

Examples

			Example of spanning subgraphs of cycle with 2 vertices:
Domination number: 2      1      1      1
                          /\            /\
                  .  .   .  .   .  .   .  .
                                 \/     \/
Number of edges:   0      1      1      2
Number of spanning subgraphs with k edges and domination number m in cycle with n = 3 vertices:
 k\m 1 2 3
 0   0 0 1
 1   0 3 0
 2   3 0 0
 3   1 0 0
T(3,k) = Sum_{m=1..3} m*F(3,m,k)
T(3,0) = 3, T(3,1) = 6, T(3,2) = 3, T(3,3) = 1
The triangle T(n,k) begins:
 n\k 0   1   2    3    4    5    6    7    8    9  10  11  12 ...
 1:  1   1
 2:  2   2   1
 3:  3   6   3    1
 4:  4  12  12    8    2
 5:  5  20  30   25   10    2
 6:  6  30  60   66   42   12    2
 7:  7  42 105  147  126   63   21    3
 8:  8  56 168  288  312  216   96   24    3
 9:  9  72 252  513  675  594  351  135   27    3
10: 10  90 360  850 1320 1410 1050  540  180   40   4
11: 11 110 495 1331 2387 3003 2706 1749  792  242  44   4
12: 12 132 660 1992 4056 5880 6228 4860 2772 1128 312  48   4
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..11475 (rows 1..150 of the triangle, flattened).

Crossrefs

Cf. A365327.

Programs

Mathematica

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]];
Table[A373436[n, k], {n, 10}, {k, 0, n}] (* Paolo Xausa, Jul 01 2024 *)

Formula

T(n,k) = n for k = 0.

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

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

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

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

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

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.

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.

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.

E(5,p) = 5 - 5*p + 5*p^3 - 5*p^4 + 2*p^5.

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

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

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

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

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.

We can see a pattern:

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.

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)).

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)).

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).

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

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

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

Relative average domination number:

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

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

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).

Limit_{n->oo} E'(n,0) = 1.

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

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