OFFSET
0,2
COMMENTS
An increasing interval-labeled restricted ternary tree (IRT for short) on the label set [0, n] is a vertex-labeled tree satisfying the following rules:
- The underlying tree is a ternary rooted tree in which middle children do not have any siblings.
- Each vertex v in the tree is assigned an interval of integer labels L_v = {i_1,...,i_2} with 0 <= i_1 <= i_2 <= n such that for each label 0 <= i <= n there exists exactly one vertex v with i contained in L_v. Thus, the collection of vertex labels forms an interval-partition of [0, n].
- If a vertex v has a middle child, then |L_v| = 1; i.e., the vertex v gets a single label.
- The labels are increasingly assigned; i.e., for every pair of vertices v, w such that v is the parent of w, we impose that max(L_v) < min(L_w).
- The root (which is the vertex containing 0 in its label set) can only have a left child, not a middle or right child.
a(n) is the number of IRTs on the label set [0,n].
LINKS
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024.
FORMULA
G.f. (Thron-type continued fraction): 1/(1 - delta(1)*x - alpha(1)*x/(1 - delta(2)*x - alpha(2)*x/(1 - ... where delta(2k-1) = 1, delta_(2k) = k and alpha(2k-1) = alpha(2k) = k.
EXAMPLE
See Figure 3 in arXiv:2412.10214 for all IRTs for the label set [0,n] for n=1,2,3.
MATHEMATICA
(*Convert a list to a T-type continued fraction.Module written by Alan Sokal.*)
ListToTContFrac[mylist_List, var_] := Module[{mylist2}, If[mylist == {}, Return[1]];
mylist2 = mylist;
If[OddQ[Length[mylist2]], AppendTo[mylist2, 0]];
1/(1 - mylist2[[1]]*var - mylist2[[2]]*var*ListToTContFrac[Drop[mylist2, 2], var])]
myCoeffSeq[maxn_] := Flatten[Table[{1, n, n, n}, {n, 1, maxn}]]
mySeq[maxn_] := CoefficientList[Series[ListToTContFrac[myCoeffSeq[maxn], t], {t, 0, maxn}], t]
CROSSREFS
KEYWORD
nonn
AUTHOR
Bishal Deb, Nov 04 2025
STATUS
approved