|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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)
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
