cp's OEIS Frontend

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.

%I A346914 #30 May 23 2024 09:19:38
%S A346914 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,
%T A346914 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,
%U A346914 0,1,2,3,1,0,1,2,3,0,0,1,2,2,2,0,1,2,2,1
%N 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.
%C A346914 Knuth's algorithm O adapts Beyer and Hedetniemi's rooted tree iteration (A346913) to rooted forests in vertex parent array form.
%C A346914 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.
%C A346914 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.
%C A346914 Rows of N vertices are in lexicographically decreasing order, the same as the level sequences of A346913 are in lexicographically decreasing order.
%C A346914 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.
%H A346914 Kevin Ryde, <a href="/A346914/b346914.txt">Table of n, a(n) for rows 2 to 1205 (forests <= 9 vertices), flattened</a>
%H A346914 Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/taocp.html">The Art of Computer Programming</a>, Volume 4A, Combinatorial Algorithms, Part 1, section 7.2.1.6, algorithm O (Oriented forests).  Also in <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz">Pre-Fascicle 4A, Draft of Section 7.2.1.6, Generating All Trees</a>, page 22.
%H A346914 Kevin Ryde, <a href="/A346913/a346913.gp.txt">PARI/GP Code for Iterating</a>
%e A346914 Triangle begins:
%e A346914         v=1 v=2 v=3 v=4
%e A346914   n=2:   0
%e A346914   n=3:   0,  1
%e A346914   n=4:   0,  0
%e A346914   n=5:   0,  1,  2
%e A346914   n=6:   0,  1,  1
%e A346914   n=7:   0,  1,  0
%e A346914   n=8:   0,  0,  0
%e A346914   n=9:   0,  1,  2,  3
%e A346914   n=10:  0,  1,  2,  2
%e A346914 Row n=1156 is 0,1,2,1,0,5,5,0,8 which is forest:
%e A346914     roots   1    5    8     vertex 1 2 3 4 5 6 7 8 9
%e A346914             |\   |\   |     vpar   0,1,2,1,0,5,5,0,8
%e A346914   children  2 4  6 7  9
%e A346914             |
%e A346914             3
%t A346914 (* Uses Algorithm O from Knuth's TAOCP section 7.2.1.6 *)
%t A346914 olist[m_] := Block[{p = Range[m] - 1, j, d, k},
%t A346914     Reap[
%t A346914     While[True,
%t A346914         Sow[p];
%t A346914         If[p[[m]] > 0,
%t A346914             p[[m]] = p[[p[[m]]]],
%t A346914             k = m; While[k > 0 && p[[--k]] == 0];
%t A346914             If[k == 0, Break[]];
%t A346914             j = p[[k]]; d = k-- -j;
%t A346914             While[++k <= m, p[[k]] = If[p[[k-d]] == p[[j]], p[[j]], p[[k-d]] + d]]
%t A346914     ]]][[2, 1]]];
%t A346914 Map[Delete[#, 0] &, Array[olist, 5]] (* _Paolo Xausa_, Apr 05 2024 *)
%o A346914 (PARI) \\ See links.
%Y A346914 Cf. A346913 (level sequences), A346915 (mems per forest), A373072 (row sums).
%K A346914 nonn,tabf
%O A346914 2,8
%A A346914 _Kevin Ryde_, Aug 07 2021