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

Author

Kevin Ryde, Aug 07 2021

Keywords

• nonn
• tabf

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.

Examples

			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.
		

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

Crossrefs

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

Programs

PARI

\\ See links.