A346914 Irregular triangle read by rows where each row is the vertex parent array of a rooted forest in Knuth's form of Beyer and Hedetniemi's iteration.

0, 0, 1, 0, 0, 0, 1, 2, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 0, 1, 2, 2, 0, 1, 2, 1, 0, 1, 2, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 0, 1, 2, 3, 3, 0, 1, 2, 3, 2, 0, 1, 2, 3, 1, 0, 1, 2, 3, 0, 0, 1, 2, 2, 2, 0, 1, 2, 2, 1

Offset: 2

Author

Kevin Ryde, Aug 07 2021

Keywords

• nonn
• tabf

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.

Examples

			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
		

Links

• Kevin Ryde, Table of n, a(n) for rows 2 to 1205 (forests <= 9 vertices), flattened
• 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

Crossrefs

Cf. A346913 (level sequences), A346915 (mems per forest), A373072 (row sums).

Programs

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 *)

PARI

\\ See links.