|
|
A346913
|
|
Irregular triangle read by rows where each row is the level sequence of a rooted tree in Beyer and Hedetniemi's iteration.
|
|
5
|
|
|
1, 1, 2, 1, 2, 3, 1, 2, 2, 1, 2, 3, 4, 1, 2, 3, 3, 1, 2, 3, 2, 1, 2, 2, 2, 1, 2, 3, 4, 5, 1, 2, 3, 4, 4, 1, 2, 3, 4, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 3, 1, 2, 3, 3, 2, 1, 2, 3, 2, 3, 1, 2, 3, 2, 2, 1, 2, 2, 2, 2, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 5, 1, 2, 3, 4, 5, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Beyer and Hedetniemi represent a rooted tree by the sequence of levels (depths) of each vertex in a pre-order traversal of the tree, and they take as a canonical form the lexicographically greatest level sequence among possible orderings of siblings in the tree.
The root of each tree is at level 1, its children are at level 2, and so on.
The number of rooted trees of <= N vertices is A087803(N) so rows n = 1 .. A087803(N) inclusive are the trees of <= N vertices.
Beyer and Hedetniemi's successor function, for transforming a given levels sequence (of N vertices) to the next, is:
- find the end-most vertex p with levels[p] >= 3
- find vertex q which is the parent of p, being the end-most q < p with levels[q] = levels[p] - 1
- change terms levels[p..N] to copies of levels[q..p-1], including a final partial copy if necessary
If no p has levels[p] >= 3 then this is the last tree of N vertices (star 1,2,2,...,2,2) and the next tree is the first of N+1 vertices which is 1,2,3,...,N+1 (path down).
Rows of a given N vertices are in lexicographically decreasing order. The successor function finds the end-most levels entry able to decrease, decreases it, and fills the rest with the greatest values permitted by the canonical form and thus the lexicographically smallest overall decrease.
Beyer and Hedetniemi show the successor function takes constant amortized time, meaning that the number of vertices examined and changed per tree, averaged over all trees of N vertices, has a constant upper bound.
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins
v=1 v=2 v=3 v=4 v=5
n=1: 1
n=2: 1, 2
n=3: 1, 2, 3
n=4: 1, 2, 2
n=5: 1, 2, 3, 4
n=6: 1, 2, 3, 3
n=7: 1, 2, 3, 2
n=8: 1, 2, 2, 2
n=9: 1, 2, 3, 4, 5
n=10: 1, 2, 3, 4, 4
Row n=35 is levels sequence 1,2,3,2,3,2 which is tree:
level 1: 1 root
| \ \
level 2: 2 4 6 children of root
| |
level 3: 3 5
Beyer and Hedetniemi give the following example of the successor function (except a misprint omits one end-most 2), which here is row n=7726:
q p end
row n: 1,2,3,4,3,2,2,2,2,2,2,2
^^^^^ block q..p-1
row n+1: 1,2,3,4,2,3,4,2,3,4,2,3
^^^^^ ^^^^^ ^^^ block copies
Vertices p..end are not a multiple of q..p-1 block length 3, so a final partial block copy.
|
|
PROG
|
(PARI) See links.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|