cp's OEIS Frontend

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

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

Knuth's algorithm O adapts Beyer and Hedetniemi's rooted tree iteration (A346913) to rooted forests in vertex parent array form.

In a vertex parent array (vpar), with vertices numbered 1..N, vpar[v] is the parent of v, or if v has no parent (so a root) then vpar[v] = 0.

Forests are indexed here starting from n=2 so that forest n corresponds to tree n in A346913 (by removing the root from the tree). An empty row n=1 could be reckoned here corresponding to the singleton row n=1 in A346913.

Rows of N vertices are in lexicographically decreasing order, the same as the level sequences of A346913 are in lexicographically decreasing order.

The first row of N vertices is the path 0,1,2,...,N-1 and the last row of N vertices is the forest of N singletons 0,0,...,0,0.

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.