This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A346913 #20 Dec 19 2024 11:46:19 %S A346913 1,1,2,1,2,3,1,2,2,1,2,3,4,1,2,3,3,1,2,3,2,1,2,2,2,1,2,3,4,5,1,2,3,4, %T A346913 4,1,2,3,4,3,1,2,3,4,2,1,2,3,3,3,1,2,3,3,2,1,2,3,2,3,1,2,3,2,2,1,2,2, %U A346913 2,2,1,2,3,4,5,6,1,2,3,4,5,5,1,2,3,4,5,4 %N A346913 Irregular triangle read by rows where each row is the level sequence of a rooted tree in Beyer and Hedetniemi's iteration. %C A346913 Beyer and Hedetniemi represent a rooted tree by the sequence of levels (depths) of each vertex in a pre-order traversal of the tree, and they take as a canonical form the lexicographically greatest level sequence among possible orderings of siblings in the tree. %C A346913 The root of each tree is at level 1, its children are at level 2, and so on. %C A346913 The number of rooted trees of <= N vertices is A087803(N) so rows n = 1 .. A087803(N) inclusive are the trees of <= N vertices. %C A346913 Beyer and Hedetniemi's successor function, for transforming a given levels sequence (of N vertices) to the next, is: %C A346913 - find the end-most vertex p with levels[p] >= 3 %C A346913 - find vertex q which is the parent of p, being the end-most q < p with levels[q] = levels[p] - 1 %C A346913 - change terms levels[p..N] to copies of levels[q..p-1], including a final partial copy if necessary %C A346913 If no p has levels[p] >= 3 then this is the last tree of N vertices (star 1,2,2,...,2,2) and the next tree is the first of N+1 vertices which is 1,2,3,...,N+1 (path down). %C A346913 Rows of a given N vertices are in lexicographically decreasing order. The successor function finds the end-most levels entry able to decrease, decreases it, and fills the rest with the greatest values permitted by the canonical form and thus the lexicographically smallest overall decrease. %C A346913 Beyer and Hedetniemi show the successor function takes constant amortized time, meaning that the number of vertices examined and changed per tree, averaged over all trees of N vertices, has a constant upper bound. %H A346913 Kevin Ryde, <a href="/A346913/b346913.txt">Table of n, a(n) for rows 1 to 1205 (trees <= 10 vertices), flattened</a> %H A346913 Terry Beyer and Sandra Mitchell Hedetniemi, <a href="https://doi.org/10.1137/0209055">Constant Time Generation of Rooted Trees</a>, SIAM Journal of Computing, volume 9, 1980, pages 706-712. %H A346913 Kevin Ryde, <a href="/A346913/a346913.gp.txt">PARI/GP Code for Iterating</a> %e A346913 Triangle begins %e A346913 v=1 v=2 v=3 v=4 v=5 %e A346913 n=1: 1 %e A346913 n=2: 1, 2 %e A346913 n=3: 1, 2, 3 %e A346913 n=4: 1, 2, 2 %e A346913 n=5: 1, 2, 3, 4 %e A346913 n=6: 1, 2, 3, 3 %e A346913 n=7: 1, 2, 3, 2 %e A346913 n=8: 1, 2, 2, 2 %e A346913 n=9: 1, 2, 3, 4, 5 %e A346913 n=10: 1, 2, 3, 4, 4 %e A346913 Row n=35 is levels sequence 1,2,3,2,3,2 which is tree: %e A346913 level 1: 1 root %e A346913 | \ \ %e A346913 level 2: 2 4 6 children of root %e A346913 | | %e A346913 level 3: 3 5 %e A346913 Beyer and Hedetniemi give the following example of the successor function (except a misprint omits one end-most 2), which here is row n=7726: %e A346913 q p end %e A346913 row n: 1,2,3,4,3,2,2,2,2,2,2,2 %e A346913 ^^^^^ block q..p-1 %e A346913 row n+1: 1,2,3,4,2,3,4,2,3,4,2,3 %e A346913 ^^^^^ ^^^^^ ^^^ block copies %e A346913 Vertices p..end are not a multiple of q..p-1 block length 3, so a final partial block copy. %o A346913 (PARI) \\ See links. %Y A346913 Cf. A346914 (as vpar forests), A087803 (number of rooted trees), A347539 (Matula-Goebel number). %K A346913 nonn,tabf %O A346913 1,3 %A A346913 _Kevin Ryde_, Aug 07 2021