A346913 Irregular triangle read by rows where each row is the level sequence of a rooted tree in Beyer and Hedetniemi's iteration.

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

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

Kevin Ryde, Table of n, a(n) for rows 1 to 1205 (trees <= 10 vertices), flattened

Terry Beyer and Sandra Mitchell Hedetniemi, Constant Time Generation of Rooted Trees, SIAM Journal of Computing, volume 9, 1980, pages 706-712.

Kevin Ryde, PARI/GP Code for Iterating

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

Cf. A346914 (as vpar forests), A087803 (number of rooted trees), A347539 (Matula-Goebel number).

Sequence in context: A280052 A183198 A249160 * A269970 A333518 A252230

Adjacent sequences: A346910 A346911 A346912 * A346914 A346915 A346916

Keyword

nonn,tabf

Author

Kevin Ryde, Aug 07 2021

Status

approved