cp's OEIS Frontend

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.

Showing 1-3 of 3 results.

A290689 Number of transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 143, 229, 370, 592, 955, 1527, 2457, 3929, 6304, 10081
Offset: 1

Views

Author

Gus Wiseman, Oct 19 2017

Keywords

Comments

A rooted tree is transitive if every proper terminal subtree is also a branch of the root. First differs from A206139 at a(13) = 143.
Regarding the notation, a rooted tree is a finite multiset of rooted trees. For example, the rooted tree (o(o)(oo)) is short for {{},{{}},{{},{}}}. Each "o" is a leaf. Each pair of parentheses corresponds to a non-leaf node (such as the root). Its contents "(...)" represent a branch. - Gus Wiseman, Nov 16 2024

Examples

			The a(7) = 8 7-node transitive rooted trees are: (o(oooo)), (oo(ooo)), (o(o)((o))), (o(o)(oo)), (ooo(oo)), (oo(o)(o)), (oooo(o)), (oooooo).

Links

Crossrefs

The restriction to identity trees (A004111) is A279861, ranks A290760.
These trees are ranked by A290822.
The anti-transitive version is A306844, ranks A324758.
The totally transitive case is A318185 (by leaves A318187), ranks A318186.
A version for integer partitions is A324753, for subsets A324736.
The ordered version is A358453, ranks A358457, undirected A358454.
Cf. A000081, A001192, A001678, A324770, A324969, A325705, A358455, A358460.

Programs

  • Mathematica
    nn=18;
rtall[n_]:=If[n===1,{{}},Module[{cas},Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])]]];
Table[Length[Select[rtall[n],Complement[Union@@#,#]==={}&]],{n,nn}]

Extensions

a(20) from Robert Price, Sep 13 2018
a(21)-a(22) from Robert P. P. McKone, Dec 16 2023

A358453 Number of transitive ordered rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 17, 37, 83, 190, 444, 1051, 2518, 6090, 14852
Offset: 1

Views

Author

Gus Wiseman, Nov 18 2022

Keywords

Comments

We define an unlabeled ordered rooted tree to be transitive if every branch of a branch of the root already appears farther to the left as a branch of the root. An undirected version is A358454.

Examples

			The a(1) = 1 through a(7) = 17 trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)
                (o(o))  (o(o)o)  (o(o)oo)   (o(o)ooo)
                        (o(oo))  (o(oo)o)   (o(oo)oo)
                        (oo(o))  (o(ooo))   (o(ooo)o)
                                 (oo(o)o)   (o(oooo))
                                 (oo(oo))   (oo(o)oo)
                                 (ooo(o))   (oo(oo)o)
                                 (o(o)(o))  (oo(ooo))
                                            (ooo(o)o)
                                            (ooo(oo))
                                            (oooo(o))
                                            (o(o)(o)o)
                                            (o(o)(oo))
                                            (o(o)o(o))
                                            (o(oo)(o))
                                            (oo(o)(o))
                                            (o(o)((o)))

Crossrefs

The unordered version is A290689, ranked by A290822.
The undirected version is A358454, ranked by A358458.
These trees are ranked by A358457.
A000081 counts rooted trees.
A306844 counts anti-transitive rooted trees.
Cf. A318185, A324695, A324751, A324756, A324758, A324764-A324768, A324838, A324840, A324844, A358456.

Programs

  • Mathematica
    aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Function[t,And@@Table[Complement[t[[k]],Take[t,k]]=={},{k,Length[t]}]]]],{n,10}]

A358458 Numbers k such that the k-th standard ordered rooted tree is weakly transitive (counted by A358454).

Original entry on oeis.org

1, 2, 4, 6, 7, 8, 12, 14, 15, 16, 18, 22, 23, 24, 25, 27, 28, 30, 31, 32, 36, 38, 39, 42, 44, 45, 46, 47, 48, 50, 51, 53, 54, 55, 56, 57, 59, 60, 62, 63, 64, 70, 71, 72, 76, 78, 79, 82, 84, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 99, 100, 102, 103, 105
Offset: 1

Views

Author

Gus Wiseman, Nov 18 2022

Keywords

Comments

We define an unlabeled ordered rooted tree to be weakly transitive if every branch of a branch of the root is itself a branch of the root.
We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

Examples

			The terms together with their corresponding ordered trees begin:
   1: o
   2: (o)
   4: (oo)
   6: ((o)o)
   7: (o(o))
   8: (ooo)
  12: ((o)oo)
  14: (o(o)o)
  15: (oo(o))
  16: (oooo)
  18: ((oo)o)
  22: ((o)(o)o)
  23: ((o)o(o))
  24: ((o)ooo)

Links

Crossrefs

The unordered version is A290822, counted by A290689.
These trees are counted by A358454.
The directed version is A358457, counted by A358453.
A000108 counts ordered rooted trees, unordered A000081.
A306844 counts anti-transitive rooted trees.
A324766 ranks recursively anti-transitive rooted trees, counted by A324765.
A358455 counts recursively anti-transitive ordered rooted trees.
Cf. A004249, A032027, A318185, A324695, A324758, A324766, A324840, A358373-A358377, A358456.

Programs

  • Mathematica
    stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[100],Complement[Union@@srt[#],srt[#]]=={}&]
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.