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, Table of n, a(n) for n = 1..20474 obtained by concatenating T(2,8), T(3,8), T(4,8), T(5,8), T(6,8)
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.
Chee Meng Tey, Perl program to generate each sequence
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
KEYWORD
nonn
AUTHOR
Tey, Chee Meng, Jul 15 2015
STATUS
approved