login
A260095
This sequence is obtained from the concatenation of certain representative members of a family of related sequences, each of which enumerates weight products along vertex paths.
1
1, 2, 2, 4, 6, 3, 6, 9, 12, 4, 8, 12, 16, 20, 5, 10, 15, 20, 25, 30, 6, 12, 18, 24, 30, 36, 42, 7, 14, 21, 28, 35, 42, 49, 56, 8, 16, 24, 32, 40, 48, 56, 64, 72, 1, 2, 2, 4, 6, 2, 4, 4, 8, 12, 6, 12, 18, 24, 3, 6, 6, 12, 18, 9, 18, 27, 36, 12, 24, 36, 48, 60
OFFSET
1,2
COMMENTS
See the referenced paper in the "Links" section for the proof.
The sequences in this family are related to a problem in computer security relating to the randomized allocation of memory.
They are also related to this problem: A restaurant has n tables, each with 2 chairs. Each customer is randomly assigned to a chair. Given r customers, what is the probability distribution of the number of empty tables?
Each sequence in this family also enumerates the product of weights along all possible paths from a vertex to the root of a partial, directed, square grid graph. Vertical edges in the graph point down and have weights of 1. Horizontal edges point left and have weights given by (y - x + 1), where (x, y) refers to the coordinates of the corresponding right vertex. Only edges with positive weights are included in the partial graph. Each sequence in the family (and consequently the corresponding graph) is identified by 2 parameters. The width of the square grid graph depends only on the first parameter x. The height depends on both parameters (x and y).
In the following graphs, unlabeled edges have a weight of 1. The symbol "+" refers to a vertex, "V" refers to the starting vertex, "R" refers to the ending (root) vertex.
T(2, 4) is related to the set of weight product along all paths from V to R in this graph:
+-5-+-4-V
| | |
+-4-+-3-+
| | |
+-3-+-2-+
| | |
+-2-+-1-+
| |
R-1-+
T(3,1) is related to the set of weight product along all paths from V to R in this graph:
+-3-+-2-+-1-V
| | |
+-2-+-1-+
| |
R-1-+
T(3,2) is related to the set of weight product along all paths from V to R in this graph:
+-4-+-3-+-2-V
| | | |
+-3-+-2-+-1-+
| | |
+-2-+-1-+
| |
R-1-+
T(4, 1) is related to the set of weight product along all paths from V to R in this graph:
+-4-+-3-+-2-+-1-V
| | | |
+-3-+-2-+-1-+
| | |
+-2-+-1-+
| |
R-1-+
LINKS
Chee Meng Tey and Debin Gao, Defending against heap overflow by using randomization in nested virtual clusters. (2015). Information and Communications Security: 15th International Conference, ICICS 2013, Beijing, China, November 20-22: Proceedings, 8233, 1. Research Collection School Of Information Systems.
FORMULA
T(2,4) = 1*1, 1*2,
2*1, 2*2, 2*3
3*1, 3*2, 3*3, 3*4,
4*1, 4*2, 4*3, 4*4, 5*4
= 1, 2, 2, 4, 6, 3, 6, 9, 12, 4, 8, 12, 16, 20
T(3,2) = 1*1*1, 1*1*2,
1*2*1, 1*2*2, 1*2*3,
2*1*1, 2*1*2,
2*2*1, 2*2*2, 2*2*3,
2*3*1, 2*3*2, 2*3*3, 2*3*4
= 1, 2, 2, 4, 6, 2, 4, 4, 8, 12, 6, 12, 18, 24
For x >= 4, y >= 2,
T(x,y) = 1^(x-1) * 1, 1^(x-1) * 2,
1^(x-2) * 2 * 1, 1^(x-2) * 2 * 2, 1^(x-2) * 2 * 3,
...,
y(y+1)(...)(y+x-2)*1, y(y+1)(...)(y+x-2)*2, ..., y(y+1)(...)(y+x-2)(y+x-1)
The sum of all the terms in the sequence is given by:
S(x, y) = (y)(y + 1)(...)(2x + y - 1)/((2^x)x!)
See reference for the proof.
EXAMPLE
T(1, y) is the arithmetic sequence with common difference of 1:
T(1, y) = 1, 2, 3, ..., y
T(2, y) is defined by:
T(2, 1) = 1, 2 T(2, y) = T(2, y-1), y, 2y, 3y, ..., (y+1)y
More generally, for y > 1, the initial terms in T(x, y) are the terms in T(x, y-1).
For example:
T(3, 1) = 1, 2, 2, 4, 6
T(3, 2) = 1, 2, 2, 4, 6, 2, 4, 4, 8, 12, 6, 12, 18, 24
T(3, 3) = 1, 2, 2, 4, 6, 2, 4, 4, 8, 12, 6, 12, 18, 24, 3, 6, 6, 12, 18, 9, 18, 27, 36, 12, 24, 36, 48, 60
T(3, 4) = 1, 2, 2, 4, 6, 2, 4, 4, 8, 12, 6, 12, 18, 24, 3, 6, 6, 12, 18, 9, 18, 27, 36, 12, 24, 36, 48, 60, 4, 8, 8, 16, 24, 12, 24, 36, 48, 16, 32, 48, 64, 80, 20, 40, 60, 80, 100, 120
Also, the following relation holds:
T(x, 1) = T(x-1, 2)
For example:
T(5, 1) = T (4, 2) = 1, 2, 2, 4, 6, 2, 4, 4, 8, 12, 6, 12, 18, 24, 2, 4, 4, 8, 12, 4, 8, 8, 16, 24, 12, 24, 36, 48, 6, 12, 12, 24, 36, 18, 36, 54, 72, 24, 48, 72, 96, 120
PROG
(Perl) See Tey link.
CROSSREFS
Sequence in context: A286243 A368259 A305125 * A209999 A127718 A115068
KEYWORD
nonn
AUTHOR
Tey, Chee Meng, Jul 15 2015
STATUS
approved