Roman Hros - cp's OEIS frontend

User: Roman Hros

Roman Hros has authored 4 sequences.

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

Roman Hros, Jun 22 2024

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.

			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

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

Cf. A365327.

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

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.

A365327 Triangle read by rows: T(n,k) is the number of spanning subgraphs of the n-cycle graph with domination number k.

Original entry on oeis.org

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, 33, 98, 80, 36, 8, 1, 0, 0, 22, 126, 189, 120, 45, 9, 1, 0, 0, 0, 141, 322, 325, 170, 55, 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

Offset: 1

Roman Hros, Sep 01 2023

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.
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).
The average domination number is given by (Sum_{k=1..n} k*T(n,k))/2^n.
The relative average domination number is given by ((Sum_{k=1..n} k*T(n,k))/2^n)/n.

			Example of spanning subgraphs of cycle with 2 vertices:
Domination number: 2      1      1      1
                          /\            /\
                  .  .   .  .   .  .   .  .
                                 \/     \/
The triangle T(n,k) begins:
n\k 1   2   3    4    5     6     7    8    9  10  11  12 ...
1:  2
2:  3   1
3:  4   3   1
4:  0  11   4    1
5:  0  11  15    5    1
6:  0  10  26   21    6     1
7:  0   0  43   49   28     7     1
8:  0   0  33   98   80    36     8    1
9:  0   0  22  126  189   120    45    9    1
10: 0   0   0  141  322   325   170   55   10   1
11: 0   0   0   89  462   671   517  231   66  11   1
12: 0   0   0   46  480  1162  1236  777  304  78  12   1

Roman Hros, Table of n, a(n) for n = 1..253 (Rows n = 1..22)
Roman Hros, Effective Enumeration of Selected Graph Characteristics, IIT.SRC 2020: 16th Student Research Conference in Informatics and Information Technologies.

Row sums are A000079.
Column sums are A002063(k-1).
Cf. A373436.

T(n,n) = 1 for n > 1.
T(n,n-1) = T(n-1, n-2) + 1 for n > 3.
T(n,n-2) = T(n-1, n-3) + T(n, n-1) for n > 5.
T(n,n-3) = T(n-1, n-4) + T(n, n-2) - 5 for n > 6.
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.
G.f.:
For n > 3; G(n) = x*(G(n-1) + G(n-2) + 2*G(n-3)) + g(n); where
         2*(1-x)*x^(n/3)   for n mod 3 = 0.
g(n) = { 0                 for n mod 3 = 1.
         (1-x)*x^((n+1)/3) for n mod 3 = 2.
For n mod 3 = 0:
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) + 2 for k =  n/3.
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.
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1)     for k >= n/3 + 2.
For n mod 3 = 1:
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1)     for k >= (n+2)/3.
For n mod 3 = 2:
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.
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.
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.

A353028 Number of subgraphs of the directed square lattice with n vertices and all vertices reachable from the origin.

Original entry on oeis.org

0, 1, 2, 5, 15, 47, 156, 527, 1826, 6407, 22762, 81587, 294711, 1070973, 3912808, 14358493, 52893647, 195498831, 724704974, 2693397035, 10033263089, 37452388361, 140063288728

Offset: 0

Roman Hros, Apr 18 2022

Similar to A344571 but here n is the number of vertices.

			In the following examples, the origin is in the bottom left corner and graph edges are directed upwards and to the right.
The a(1) = 1 graph is:
.
The a(2) = 2 graphs are:
  |   __
.
The a(3) = 5 graphs are:
  |   __
  |  |     __.__    __|   |__
.
The a(4) = 15 graphs are:
  |    __
  |   |     |__    __|    __.__    |      __
  |   |     |     |      |         |__   |__
.
                               __    |                  __
  __.__.__   __.__|  __|__  __|    __|   |__.__  |__|  |__|
.
Other examples with 5, 6, and 7 vertices respectively include:
    |        __.__      __|__|
    |__|    |__.__|    |__|

Cf. A344571.

a(n) >= 2*a(n-1) for n > 0.

A344571 Number of subgraphs of the directed square lattice with n edges and all vertices reachable from the origin.

Original entry on oeis.org

1, 2, 5, 14, 42, 130, 412, 1326, 4318, 14188, 46950, 156258, 522523, 1754254, 5909419, 19964450, 67618388, 229526054, 780633253, 2659600616, 9075301990, 31010850632, 106100239080, 363428599306, 1246172974048, 4277163883744, 14693260749888, 50516757992258

Offset: 0

Roman Hros, May 23 2021

nonn

Equivalently, the number of fixed polysticks (see A096267) that can be constructed starting from a fixed vertex by only adding edges on top of an existing vertex or to the right of an existing vertex. If the polystick is rotated counterclockwise by 45 degrees, then the polystick is supported from the starting vertex. - Andrew Howroyd, May 24 2021

			In the following examples, the origin is in the bottom left corner and graph edges are directed upwards and to the right.
The a(1) = 2 graphs are:
  |   __
.
The a(2) = 5 graphs are:
  |   __
  |  |     __.__    __|   |__
.
The a(3) = 14 graphs are:
  |    __
  |   |     |__    __|    __.__    |      __
  |   |     |     |      |         |__   |__
.
                               __    |
  __.__.__   __.__|  __|__  __|    __|   |____  |_|
.
Other examples with 4, 6, and 7 edges respectively include:
     __      __.__      __|__|
    |__|    |__.__|    |__|

Roman Hros, Generating Subgraphs of Finite Grids, IIT.SRC 2018: 14th Student Research Conference in Informatics and Information Technologies.
Eric Weisstein's World of Mathematics, Polystick
Wikipedia, Polystick

Cf. A096267, A353028.

a(n)={
  local(M=Map());
  my(acc(hk, r)=my(z); mapput(M, hk, if(mapisdefined(M,hk,&z),z+r,r)));
  my(recurse(w,f,b,r) =
    if(w<=0, if(w==0, acc([w,1],r)), if(f==0, if(b, acc([w,b>>valuation(b,2)],r)),
    my(t=1<Andrew Howroyd, May 24 2021

a(n) >= 2*a(n-1) for n > 0.

Terms a(25) and beyond from Andrew Howroyd, May 24 2021

cp's OEIS Frontend

User: Roman Hros

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A365327 Triangle read by rows: T(n,k) is the number of spanning subgraphs of the n-cycle graph with domination number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A353028 Number of subgraphs of the directed square lattice with n vertices and all vertices reachable from the origin.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A344571 Number of subgraphs of the directed square lattice with n edges and all vertices reachable from the origin.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions