OFFSET
2,8
COMMENTS
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.
LINKS
Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, section 7.2.1.6, algorithm O (Oriented forests). Also in Pre-Fascicle 4A, Draft of Section 7.2.1.6, Generating All Trees, page 22.
Kevin Ryde, PARI/GP Code for Iterating
EXAMPLE
Triangle begins:
v=1 v=2 v=3 v=4
n=2: 0
n=3: 0, 1
n=4: 0, 0
n=5: 0, 1, 2
n=6: 0, 1, 1
n=7: 0, 1, 0
n=8: 0, 0, 0
n=9: 0, 1, 2, 3
n=10: 0, 1, 2, 2
Row n=1156 is 0,1,2,1,0,5,5,0,8 which is forest:
roots 1 5 8 vertex 1 2 3 4 5 6 7 8 9
|\ |\ | vpar 0,1,2,1,0,5,5,0,8
children 2 4 6 7 9
|
3
MATHEMATICA
(* 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]]];
Map[Delete[#, 0] &, Array[olist, 5]] (* Paolo Xausa, Apr 05 2024 *)
PROG
(PARI) \\ See links.
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Kevin Ryde, Aug 07 2021
STATUS
approved