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,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

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

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[n_] := Block[{p = Range[n] - 1, j, d, k},
    Reap[
    While[True,
        Sow[p];
        If[p[[n]] > 0,
            p[[n]] = p[[p[[n]]]],
            k = n; While[k > 0 && p[[--k]] == 0];
            If[k == 0, Break[]];
            j = p[[k]]; d = k-- -j;
            While[++k <= n, 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

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

Sequence in context: A348536 A245963 A291375 * A033778 A091586 A363037

Adjacent sequences: A346911 A346912 A346913 * A346915 A346916 A346917

Keyword

nonn,tabf

Author

Kevin Ryde, Aug 07 2021

Status

approved