A347539 -id:A347539 - cp's OEIS frontend

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

Kevin Ryde, Aug 07 2021

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.

			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.

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

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

PARI
```
\\ See links.
```

A347540 Position within Beyer and Hedetniemi's rooted tree iteration (A346913) of the tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 6, 8, 15, 12, 9, 16, 11, 14, 29, 17, 10, 35, 13, 30, 33, 22, 26, 36, 71, 28, 82, 34, 21, 73, 18, 37, 55, 25, 72, 83, 27, 32, 69, 74, 20, 80, 24, 56, 183, 66, 52, 84, 79, 180, 63, 70, 31, 197, 144, 81, 77, 54, 19, 184, 65, 43, 194, 85, 176, 146

Offset: 1

Kevin Ryde, Sep 06 2021

nonn

This sequence is a permutation of the natural numbers, with inverse A347539.

			For n=21, the tree with Matula-Goebel number 21 is as follows, shown with siblings ordered per Beyer and Hedetniemi's canonical form,
  root      1           pre-order levels = 1,2,3,3,2,3
            |  \        which is row 33 of A346913
  level=2   2    2      so a(21) = 33
            |\   |
  level=3   3 3  3

Cf. A346913, A347539 (inverse).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI