A346914 -id:A346914 - cp's OEIS frontend

A373072 Row sums of A346914.

0, 1, 0, 3, 2, 1, 0, 6, 5, 4, 3, 3, 2, 4, 1, 0, 10, 9, 8, 7, 6, 7, 6, 5, 8, 5, 4, 7, 3, 4, 3, 6, 2, 4, 1, 0, 15, 14, 13, 12, 11, 10, 12, 11, 10, 9, 13, 10, 9, 8, 12, 8, 7, 11, 6, 9, 8, 7, 11, 7, 6, 10, 5, 9, 8, 6, 5, 9, 4, 12, 11, 7, 3, 5, 4, 8, 3, 10, 6, 2, 9, 4, 1, 0

Offset: 2

Paolo Xausa, May 22 2024

nonn

See A346914 for more information.

Paolo Xausa, Table of n, a(n) for n = 2..7813

Cf. A346914.

(* Uses Algorithm O from Knuth's TAOCP section 7.2.1.6 *)
olist[m_] := Block[{p = Range[m] - 1, j, d, k},
    Reap[
    While[True,
        Sow[p];
        If[p[[m]] > 0,
            p[[m]] = p[[p[[m]]]],
            k = m; While[k > 0 && p[[--k]] == 0];
            If[k == 0, Break[]];
            j = p[[k]]; d = k-- -j;
            While[++k <= m, p[[k]] = If[p[[k-d]] == p[[j]], p[[j]], p[[k-d]] + d]]
    ]]][[2, 1]]];
Flatten[Total[Array[olist, 6], {3}]]

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

Original entry on oeis.org

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.
```

A346915 Decimal expansion of the limit as N->oo of the mean number of mems per forest taken by Knuth's algorithm O when generating the rooted forests of N vertices.

Original entry on oeis.org

3, 5, 3, 3, 9, 2, 6, 3, 9, 8, 0, 2, 3, 7, 2, 1, 7, 9, 6, 9, 1, 5, 9, 9, 9, 7, 5, 6, 9, 0, 0, 2, 7, 2, 7, 8, 4, 5, 1, 0, 8, 6, 7, 6, 0, 3, 2, 5, 7, 3, 7, 7, 2, 9, 1, 8, 0, 6, 7, 3, 4, 5, 8, 9, 4, 6, 0, 3, 4, 1, 2, 0, 6, 2, 1, 8, 6, 9, 2, 4, 9, 4, 1, 9, 7, 5, 0, 7, 7, 2, 5, 1, 2, 6, 3, 1, 2, 7, 2, 8, 7, 3, 0, 5, 5

Offset: 1

Kevin Ryde, Aug 07 2021

Knuth volume 4A section 7.2.1.6 algorithm O adapts the rooted tree iteration algorithm of Beyer and Hedetniemi (A346913) to become a forests iteration in vertex parent array form (A346914).
Knuth's exercise 88 is to count mems (memory reads + memory writes) in algorithm O.  Per Knuth's answer, the present constant is 2 + 3/(d-1) where d=A051491 is the growth power of rooted trees (and forests).
Also equals 3*S+2 where S=A346916 is the (limit) mean number of singletons in a rooted forest.  The mems are S reads to find the end-most vertex k which is not a singleton, then S+1 reads and S+1 writes to change k and the singletons to subtree copies.  Finding k examines S+1 array entries, but the algorithm holds the final p[N] in a register as well as in memory so no mem to examine it.

			3.533926398023721796915999756900272...

Kevin Ryde, Table of n, a(n) for n = 1..1799
Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, section 7.2.1.6, exercise 88. Also in Pre-Fascicle 4A, Draft of Section 7.2.1.6, Generating All Trees algorithm O page 22, exercise 88 page 40, and answer page 66.

Cf. A051491 (rooted tree growth), A346916 (mean singletons per forest).

Cf. A346913 (levels iteration), A346914 (vpar iteration).

Equals 2 + 3/(A051491 - 1). [Knuth]

Equals 3*A346916 + 2.

cp's OEIS Frontend

A373072 Row sums of A346914.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A346915 Decimal expansion of the limit as N->oo of the mean number of mems per forest taken by Knuth's algorithm O when generating the rooted forests of N vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula