Tamari blossoming trees

This module implements the blossoming trees in bijection with Tamari intervals.

These blossoming trees are trees with half-edges bicolored following some local rules, each node has two buds, and each edge has two legs. Buds are matched with legs in a planar way, leaving only two dangling buds. The coloring can be replaced by marking one of the dangling buds. The blossoming tree is represented as a plane tree, in which a bud is exactly a leaf. We take the convention that the root bud is a dangling bud with red half-edges next to it in the counter-clockwise order.

REFERENCES:

[FFN2025]

AUTHORS:

• Wenjie Fang (2026): initial implementation

class sage.combinat.tamari_blossoming_tree.ModernBlossomingTreeFactory(size: int)

Bases: SageObject, UniqueRepresentation

This class is for uniform random generation of blossoming trees associated with modern Tamari intervals of a given size. As some precomputation is needed, it is the best practice to keep the same instance when generating multiple modern blossoming trees. For one-shot generation, we also provide a static method.

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     ModernBlossomingTreeFactory)
sage: MBTF = ModernBlossomingTreeFactory(100)
sage: MBTF
Random generator of modern blossoming trees of size 100
sage: MBTF.random_element()
Tamari blossoming tree ... of size 100
sage: MBTF.random_element().is_modern()
True

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     ModernBlossomingTreeFactory)
>>> MBTF = ModernBlossomingTreeFactory(Integer(100))
>>> MBTF
Random generator of modern blossoming trees of size 100
>>> MBTF.random_element()
Tamari blossoming tree ... of size 100
>>> MBTF.random_element().is_modern()
True

random_element()

Generate a uniformly random modern blossoming tree of a given size.

OUTPUT:

A uniformly random modern blossoming tree obtained using bijection with lattice paths.

ALGORITHM:

According to Section 5.5 of [FFN2025], the generating function of modern blossoming trees can be written as \((1 + C)^2\), with:

• \(C = \frac{A}{1 - B}\)

• \(B = \frac{z(1 + C)}{1 - B}\)

• \(A = \frac{z(1 + C)^2}{1 - B} = B (1 + C)\)

Each series counts a certain family of trees with buds.

By solving it, we know that

• \(C(z)\) is the series of Dyck paths with weight 2 on every non-initial up-step

• \(B(z)\) is the series of Dyck paths of C without touching the x-axis in middle

• \(A(z)\) is the series of Dyck paths with weight 2 on every up-step except the first and the second one on the x-axis (there may be only one such step)

We may then generate a modern blossoming tree by generating Dyck paths with the correct weights, then interpreting such weights in the proper way to obtain a modern blossoming tree according to the recursive decomposition. Details of the bijection for each family can be found in the documentation of the corresponding sub-functions.

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     ModernBlossomingTreeFactory)
sage: B = ModernBlossomingTreeFactory(100).random_element()
sage: B
Tamari blossoming tree ... of size 100
sage: B.is_modern()
True

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     ModernBlossomingTreeFactory)
>>> B = ModernBlossomingTreeFactory(Integer(100)).random_element()
>>> B
Tamari blossoming tree ... of size 100
>>> B.is_modern()
True

class sage.combinat.tamari_blossoming_tree.SynchronizedBlossomingTreeFactory(size: int)

Bases: SageObject, UniqueRepresentation

This class is for uniform random generation of synchronized blossoming trees, which are in bijection with modern Tamari intervals, of a given size. No precomputation is needed here, but we keep the same convention as ModernBlossomingTreeFactory for the methods.

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     SynchronizedBlossomingTreeFactory)
sage: SBTF = SynchronizedBlossomingTreeFactory(100)
sage: SBTF
Random generator of synchronized blossoming trees of size 100
sage: SBTF.random_element()
Tamari blossoming tree ... of size 100
sage: SBTF.random_element().is_synchronized()
True

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     SynchronizedBlossomingTreeFactory)
>>> SBTF = SynchronizedBlossomingTreeFactory(Integer(100))
>>> SBTF
Random generator of synchronized blossoming trees of size 100
>>> SBTF.random_element()
Tamari blossoming tree ... of size 100
>>> SBTF.random_element().is_synchronized()
True

random_element()

Generate a random synchronized blossoming tree of a given size.

OUTPUT:

A uniformly random synchronized blossoming tree, obtained through random generation of lattice paths.

ALGORITHM:

According to [FFN2025], a Tamari blossoming tree is synchronized if and only if the two buds of the same node is always side by side. In such a case, we may identify them, and what we need to generate is a plane tree where each node has one extra bud. Now, root such a plane tree with buds by one of the bud, we only need to generate a sequence of plane trees with a bud at each internal node. Let \(A\) be the set of such trees. A tree in \(A\) can be decomposed at the root as two sequences of trees in \(A\), separated by the bud.

It is clear that lattice paths with steps \((1, 2)\) and \((1, -1)\) starting and ending on the x-axis while staying weakly above it (also called 2-Dyck paths in some literature) are in bijection with such sequence of plane trees. Such a lattice path can be considered a sequence of primitive paths (touching only the x-axis at both ends), and each of them can be decomposed into two 2-Dyck paths by the last returning to the height 2 and 1. It is clear that \(A\) is in bijection with primitive paths by isomorphism of recursive decomposition.

We note that no cutting is needed here, as we simply generate one sequence instead of a pair of them. This is why precomputing is not needed here.

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     SynchronizedBlossomingTreeFactory)
sage: B = SynchronizedBlossomingTreeFactory(100).random_element()
sage: B
Tamari blossoming tree ... of size 100
sage: B.is_synchronized()
True

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     SynchronizedBlossomingTreeFactory)
>>> B = SynchronizedBlossomingTreeFactory(Integer(100)).random_element()
>>> B
Tamari blossoming tree ... of size 100
>>> B.is_synchronized()
True

class sage.combinat.tamari_blossoming_tree.TamariBlossomingTree(parent, tree: OrderedTree)

Bases: Element, UniqueRepresentation

The class of bicolored blossoming trees, which are in bijection with intervals in the Tamari lattice.

A (bicolored) blossoming tree is a plane unrooted tree satisfying:

• Each edge consists of two half-edges, one colored red and the other blue.

• Each node has two extra unpaired uncolored half-edges called buds, which separate cyclically its other adjacent half-edges into two monochromatic parts. In other words, for each node, when reading color of adjacent half-edges in the cyclic order, colors change exactly twice, and the buds are placed at such position of changes.

The size of a bicolored blossoming tree is the number of edges (not counting buds). They are in bijection with intervals in the Tamari lattice formed by binary trees of the same size (the number of internal nodes).

As a convention, although a blossoming tree is unrooted, we represent it by a rooted plane tree with the root as the node with the dangling bud with red half-edges next to it in the counter-clockwise order. As a consequence, all internal nodes of the rooted plane tree have two buds, except for the root which only has one, separating blue half-edges on the left and red ones on the right.

For usage, it is the best to use conversion functions provided by this class, instead of its constructor, which has less flexibility.

Note

The metaclass InheritComparisonClasscallMetaclass comes from a conjoint of the metaclass InheritComparisonMetaclass imposed by the base class UniqueRepresentation and the metaclass ClasscallMetaclass imposed by Element.

EXAMPLES:

Sage

sage: T = [[], [[[], []], [], []]]
sage: TB = TamariBlossomingTree.from_plane_tree(T)
sage: TB
Tamari blossoming tree [[], [[], []], [[], []]] of size 2
sage: B1, B2 = TB.to_tamari()
sage: B1, B2
([[., .], .], [[., .], .])
sage: TB is TamariBlossomingTree.from_tamari(B1, B2)
True
sage: TB.is_modern()
True
sage: TB.is_synchronized()
True

Python

>>> from sage.all import *
>>> T = [[], [[[], []], [], []]]
>>> TB = TamariBlossomingTree.from_plane_tree(T)
>>> TB
Tamari blossoming tree [[], [[], []], [[], []]] of size 2
>>> B1, B2 = TB.to_tamari()
>>> B1, B2
([[., .], .], [[., .], .])
>>> TB is TamariBlossomingTree.from_tamari(B1, B2)
True
>>> TB.is_modern()
True
>>> TB.is_synchronized()
True

static binary_tree_plot(btree)

Utility function for plotting binary trees in the “upside-down Chapoton” way, i.e., leaves are drawn on a horizontal line, but the root still on top.

INPUT:

• btree – a binary tree, not necessarily of type BinaryTree

OUTPUT:

A plot of btree, with leaves on a horizontal line, and edges all of slope \(1\) or \(-1\). Labels are ignored.

EXAMPLES:

Sage

sage: B3 = [[[[None, [None, []]], None], [[], None]], None]
sage: g = TamariBlossomingTree.binary_tree_plot(B3)

Python

>>> from sage.all import *
>>> B3 = [[[[None, [None, []]], None], [[], None]], None]
>>> g = TamariBlossomingTree.binary_tree_plot(B3)

static binary_tree_smooth_drawing(btree, color='blue')

Plot the smooth drawing of a binary tree, which is obtained by converting each internal node of a binary tree and its edges into an arc linking its leftmost and rightmost leaves. Such a drawing is planar. See [FFN2025] for more details.

INPUT:

• btree – a binary tree, not necessarily of type BinaryTree.

• color – color of the arcs. Default: blue.

OUTPUT:

The smooth drawing of a binary tree with the given color

EXAMPLES:

Sage

sage: B3 = [[[[None, [None, []]], None], [[], None]], None]
sage: g = TamariBlossomingTree.binary_tree_smooth_drawing(B3)

Python

>>> from sage.all import *
>>> B3 = [[[[None, [None, []]], None], [[], None]], None]
>>> g = TamariBlossomingTree.binary_tree_smooth_drawing(B3)

static from_TIP(tip)

Construct the blossoming tree in bijection with a given Tamari interval-poset.

INPUT:

• tip – a TamariIntervalPoset object representing a Tamari interval

EXAMPLES:

Sage

sage: B3 = [[[[None, [None, []]], None], [[], None]], None]
sage: B4 = [[None, [[None, []], None]], [None, [[], None]]]
sage: B3, B4 = BinaryTree(B3), BinaryTree(B4)
sage: tip = TamariIntervalPosets.from_binary_trees(B3, B4)
sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: TlB = TamariBlossomingTree(Tl)
sage: TlB == TamariBlossomingTree.from_TIP(tip)
True
sage: B0 = BinaryTree()
sage: tip2 = TamariIntervalPosets.from_binary_trees(B0, B0)
sage: TlB == TamariBlossomingTree.from_TIP(tip2)
False

Python

>>> from sage.all import *
>>> B3 = [[[[None, [None, []]], None], [[], None]], None]
>>> B4 = [[None, [[None, []], None]], [None, [[], None]]]
>>> B3, B4 = BinaryTree(B3), BinaryTree(B4)
>>> tip = TamariIntervalPosets.from_binary_trees(B3, B4)
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> TlB = TamariBlossomingTree(Tl)
>>> TlB == TamariBlossomingTree.from_TIP(tip)
True
>>> B0 = BinaryTree()
>>> tip2 = TamariIntervalPosets.from_binary_trees(B0, B0)
>>> TlB == TamariBlossomingTree.from_TIP(tip2)
False

static from_plane_tree(tree)

Return the blossoming tree corresponding to the given tree.

We suppose that the root of the tree is a bud. Comparing to the constructor, we do not fail when the buds are not matching, but tries to find the correct bud.

We assume that the root, which is a bud, has red half-edges next to it in counter-clockwise order (so the left one). We then find the unpaired bud with the opposite property, to simplify the reflection operation.

Note

This function is a thin wrapper of the internal function _from_plane_tree, which provides two extra functionalities by which end users should not be concerned.

INPUT:

• tree – a plane tree with two buds on each node (one for the root).

OUTPUT:

An object of type TamariBlossomingTree representing the blossoming tree given by tree.

EXAMPLES:

Sage

sage: pt = [[], [[[], []], [], []]]
sage: B1, B2 = TamariBlossomingTree.from_plane_tree(pt).to_tamari()
sage: B1 == BinaryTree([[], None])
True
sage: B1 == B2
True

Python

>>> from sage.all import *
>>> pt = [[], [[[], []], [], []]]
>>> B1, B2 = TamariBlossomingTree.from_plane_tree(pt).to_tamari()
>>> B1 == BinaryTree([[], None])
True
>>> B1 == B2
True

static from_tamari(ltree, htree)

Return the blossoming tree corresponding to the given Tamari interval, given as a pair of binary trees (not necessarily of type BinaryTree).

INPUT:

• ltree – the lower binary tree in the given Tamari interval.

• htree – the upper binary tree in the given Tamari interval.

OUTPUT:

A blossoming tree in bijection with the given Tamari interval

EXAMPLES:

Sage

sage: B0 = BinaryTree()
sage: TB0 = TamariBlossomingTree(OrderedTree([[]]))
sage: TamariBlossomingTree.from_tamari(B0, B0) == TB0
True
sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: TlB = TamariBlossomingTree(Tl)
sage: B3 = [[[[None, [None, []]], None], [[], None]], None]
sage: B4 = [[None, [[None, []], None]], [None, [[], None]]]
sage: TamariBlossomingTree.from_tamari(B3, B4) == TlB
True
sage: TamariBlossomingTree.from_tamari(B4, B3)
Traceback (most recent call last):
...
ValueError: not a Tamari interval

Python

>>> from sage.all import *
>>> B0 = BinaryTree()
>>> TB0 = TamariBlossomingTree(OrderedTree([[]]))
>>> TamariBlossomingTree.from_tamari(B0, B0) == TB0
True
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> TlB = TamariBlossomingTree(Tl)
>>> B3 = [[[[None, [None, []]], None], [[], None]], None]
>>> B4 = [[None, [[None, []], None]], [None, [[], None]]]
>>> TamariBlossomingTree.from_tamari(B3, B4) == TlB
True
>>> TamariBlossomingTree.from_tamari(B4, B3)
Traceback (most recent call last):
...
ValueError: not a Tamari interval

is_modern()

Return whether the Tamari interval associated to the current blossoming tree is modern, using the function is_modern() in TamariIntervalPoset.

OUTPUT:

True if the blossoming tree is modern, and False otherwise.

EXAMPLES:

Sage

sage: T1 = [[], [[], [], [[], []]]]
sage: TamariBlossomingTree.from_plane_tree(T1).is_modern()
True
sage: T2 = [[], [[[], [], [[], []]], [], []]]
sage: TamariBlossomingTree.from_plane_tree(T2).is_modern()
False

Python

>>> from sage.all import *
>>> T1 = [[], [[], [], [[], []]]]
>>> TamariBlossomingTree.from_plane_tree(T1).is_modern()
True
>>> T2 = [[], [[[], [], [[], []]], [], []]]
>>> TamariBlossomingTree.from_plane_tree(T2).is_modern()
False

is_synchronized()

Return whether the Tamari interval presented by the current blossoming tree is synchronized, i.e., two buds of the same node are adjacent.

OUTPUT:

True if the blossoming tree is synchronized, otherwise False

EXAMPLES:

Sage

sage: T1 = [[], [[], [], [[], []]]]
sage: TamariBlossomingTree.from_plane_tree(T1).is_synchronized()
True
sage: T2 = [[], [[], [[], []], []]]
sage: TamariBlossomingTree.from_plane_tree(T2).is_synchronized()
False

Python

>>> from sage.all import *
>>> T1 = [[], [[], [], [[], []]]]
>>> TamariBlossomingTree.from_plane_tree(T1).is_synchronized()
True
>>> T2 = [[], [[], [[], []], []]]
>>> TamariBlossomingTree.from_plane_tree(T2).is_synchronized()
False

plot_blossoming(aspect=1.0, layout='tree')

Plot the blossoming tree of self, using the plot of OrderedTree, but with buds better spaced.

INPUT:

• aspect – ratio of aspect, default to 1.0

• layout – the algorithm for layout, with three possible options:

  • 'tree': uses layout_tree of undirected graph in sage

  • 'planar': uses layout_planar of undirected graph in sage

OUTPUT:

A plot of the current blossoming tree.

EXAMPLES:

Sage

sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: g = TamariBlossomingTree(Tl).plot_blossoming()

Python

>>> from sage.all import *
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> g = TamariBlossomingTree(Tl).plot_blossoming()

plot_meandric(semicircle=True, arrow=True)

Plot the meandric tree of self.

The meandric tree is the blossoming tree drawn in a way such that the drawing is planar, with buds all on the same horizontal line, which separates the red half-edges above and the blue ones below. For more details, see [FFN2025].

INPUT:

• semicircle – optional, sets whether the arcs are drawn as semicircles or a Bezier arc. Default: True, which draws semicircles.

• arrow – optional, sets whether draw horizontal arrows tips. Default: True.

EXAMPLES:

Sage

sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: g = TamariBlossomingTree(Tl).plot_meandric()

Python

>>> from sage.all import *
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> g = TamariBlossomingTree(Tl).plot_meandric()

reflection()

Return the blossoming tree that is the mirror image of the current blossoming tree.

Note that the dangling buds change in general, so the root dangling bud will be the one with the correct color.

OUTPUT:

A blossoming tree that is the mirror image of the current one. Not to be confused with the Tamari dual computed by tamari_dual().

EXAMPLES:

Sage

sage: pt = [[], [[[], []], [], []]]
sage: TB = TamariBlossomingTree.from_plane_tree(pt)
sage: TB == TB.reflection().reflection()
True
sage: TB.reflection().to_plane_tree()
[[], [[], []], [[], []]]

Python

>>> from sage.all import *
>>> pt = [[], [[[], []], [], []]]
>>> TB = TamariBlossomingTree.from_plane_tree(pt)
>>> TB == TB.reflection().reflection()
True
>>> TB.reflection().to_plane_tree()
[[], [[], []], [[], []]]

size()

Return the size of the Tamari blossoming tree.

OUTPUT:

The size of the current blossoming tree, which is the number of edges excluding buds. This convention agrees with that of TamariIntervalPoset.

EXAMPLES:

Sage

sage: T = OrderedTree([[], [[], [], [[], []]]])
sage: T = TamariBlossomingTree(T)
sage: T.size()
2
sage: T.size() == T.to_TIP().size()
True

Python

>>> from sage.all import *
>>> T = OrderedTree([[], [[], [], [[], []]]])
>>> T = TamariBlossomingTree(T)
>>> T.size()
2
>>> T.size() == T.to_TIP().size()
True

smooth_drawing()

Plot the smooth drawing of self.

The smooth drawing of a blossoming tree is the combination of the smooth drawings of the two binary trees of the Tamari interval represented by the current blossoming tree, with that of the larger element above and that of the smaller one below, reflected by the horizontal axis.

See [FFN2025] for more details.

EXAMPLES:

Sage

sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: g = TamariBlossomingTree(Tl).smooth_drawing()

Python

>>> from sage.all import *
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> g = TamariBlossomingTree(Tl).smooth_drawing()

tamari_dual()

Return the current blossoming tree with colors exchanged.

This is equivalent to taking the dual in the Tamari lattice for the corresponding interval. Not to be confused with the mirror symmetric of blossoming trees, which is implemented in reflection().

Note

We use a feature of from_plane_tree() instead of using the usual left_right_symmetry() in BinaryTree to avoid exceeding the limit on the number of recursions when tree size is large.

EXAMPLES:

Sage

sage: B3 = [[[[None, [None, []]], None], [[], None]], None]
sage: B4 = [[None, [[None, []], None]], [None, [[], None]]]
sage: B3, B4 = BinaryTree(B3), BinaryTree(B4)
sage: TB = TamariBlossomingTree.from_tamari(B3, B4)
sage: B4d, B3d = TB.tamari_dual().to_tamari()
sage: B4d == B4.left_right_symmetry()
True
sage: B3d == B3.left_right_symmetry()
True

Python

>>> from sage.all import *
>>> B3 = [[[[None, [None, []]], None], [[], None]], None]
>>> B4 = [[None, [[None, []], None]], [None, [[], None]]]
>>> B3, B4 = BinaryTree(B3), BinaryTree(B4)
>>> TB = TamariBlossomingTree.from_tamari(B3, B4)
>>> B4d, B3d = TB.tamari_dual().to_tamari()
>>> B4d == B4.left_right_symmetry()
True
>>> B3d == B3.left_right_symmetry()
True

to_TIP()

Return the corresponding Tamari interval-poset in bijection with the current instance of blossoming tree.

OUTPUT:

An object of type TamariIntervalPoset representing the corresponding Tamari interval poset

EXAMPLES:

Sage

sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: TlB = TamariBlossomingTree(Tl)
sage: tip = TlB.to_TIP()
sage: B3 = [[[[None, [None, []]], None], [[], None]], None]
sage: B4 = [[None, [[None, []], None]], [None, [[], None]]]
sage: tip.lower_binary_tree() == BinaryTree(B3)
True
sage: tip.upper_binary_tree() == BinaryTree(B4)
True

Python

>>> from sage.all import *
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> TlB = TamariBlossomingTree(Tl)
>>> tip = TlB.to_TIP()
>>> B3 = [[[[None, [None, []]], None], [[], None]], None]
>>> B4 = [[None, [[None, []], None]], [None, [[], None]]]
>>> tip.lower_binary_tree() == BinaryTree(B3)
True
>>> tip.upper_binary_tree() == BinaryTree(B4)
True

to_plane_tree()

Return the blossoming tree as an OrderedTree.

The buds simply become leaves.

EXAMPLES:

Sage

sage: T = OrderedTree([[], [[], [], [[], []]]])
sage: T == TamariBlossomingTree(T).to_plane_tree()
True

Python

>>> from sage.all import *
>>> T = OrderedTree([[], [[], [], [[], []]]])
>>> T == TamariBlossomingTree(T).to_plane_tree()
True

to_tamari()

Return the Tamari interval in bijection with self, under the form of a pair of binary trees.

OUTPUT:

A pair of binary trees comparable in the Tamari lattice (thus a Tamari interval)

EXAMPLES:

Sage

sage: B0 = BinaryTree()
sage: T0 = OrderedTree([[]])
sage: TamariBlossomingTree(T0).to_tamari() == (B0, B0)
True
sage: T = OrderedTree([[], [[], [], [[], []]]])
sage: TamariBlossomingTree(T).to_tamari()
([., [., .]], [., [., .]])
sage: Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
....:                   [[], [], [[[], []], [], [[], []], []]]])
sage: B3, B4 = TamariBlossomingTree(Tl).to_tamari()
sage: B3
[[[[., [., [., .]]], .], [[., .], .]], .]
sage: B4
[[., [[., [., .]], .]], [., [[., .], .]]]

Python

>>> from sage.all import *
>>> B0 = BinaryTree()
>>> T0 = OrderedTree([[]])
>>> TamariBlossomingTree(T0).to_tamari() == (B0, B0)
True
>>> T = OrderedTree([[], [[], [], [[], []]]])
>>> TamariBlossomingTree(T).to_tamari()
([., [., .]], [., [., .]])
>>> Tl = OrderedTree([[], [[], [], [[], []], [[[], []], [], []]],
...                   [[], [], [[[], []], [], [[], []], []]]])
>>> B3, B4 = TamariBlossomingTree(Tl).to_tamari()
>>> B3
[[[[., [., [., .]]], .], [[., .], .]], .]
>>> B4
[[., [[., [., .]], .]], [., [[., .], .]]]

class sage.combinat.tamari_blossoming_tree.TamariBlossomingTrees

Bases: UniqueRepresentation, Parent

Factory class for Tamari blossoming trees. See TamariBlossomingTree for details of the elements.

INPUT:

• size – size of Tamari blossoming trees in the set (optional, default: None, standing for Tamari blossoming trees of all sizes)

OUTPUT:

An object representing the set of Tamari blossoming trees of the given size.

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     TamariBlossomingTrees)
sage: TamariBlossomingTrees()
Tamari blossoming trees
sage: TamariBlossomingTrees(10)
Tamari blossoming trees of size 10

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     TamariBlossomingTrees)
>>> TamariBlossomingTrees()
Tamari blossoming trees
>>> TamariBlossomingTrees(Integer(10))
Tamari blossoming trees of size 10

Note

This is a factory class whose constructor returns instances of subclasses corresponding to call parameters.

class sage.combinat.tamari_blossoming_tree.TamariBlossomingTrees_all

Bases: DisjointUnionEnumeratedSets, TamariBlossomingTrees

The enumerated set of all Tamari blossoming trees.

Element

alias of TamariBlossomingTree

class sage.combinat.tamari_blossoming_tree.TamariBlossomingTrees_size(size)

Bases: TamariBlossomingTrees

The enumerated set of Tamari blossoming trees of a given size.

cardinality()

Return the cardinality of self, i.e., the number of Tamari blossoming trees of size \(n\) used to initialize the instance.

The formula, which is the same as that for Tamari intervals, is given in [Cha2008]:

\[\frac{2}{n (n + 1)} \binom{4n + 1}{n - 1}\]

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     TamariBlossomingTrees)
sage: [len(TamariBlossomingTrees(n)) for n in range(1, 6)]
[1, 3, 13, 68, 399]

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     TamariBlossomingTrees)
>>> [len(TamariBlossomingTrees(n)) for n in range(Integer(1), Integer(6))]
[1, 3, 13, 68, 399]

element_class()

Overriding the original method of the base class to make the element class uniform across all implementation of sets of Tamari blossoming trees.

random_element()

Generate a uniformly random Tamari blossoming tree of a given size.

OUTPUT:

A uniformly random Tamari blossoming tree, obtained through random generation of lattice path.

ALGORITHM:

Let \(A\) be the set of rooted plane trees such that each internal node has two buds. Then a tree in \(A\) can be decomposed at the root into three sequences of sub-trees in \(A\), separated by the two buds of the root. A Tamari blossoming tree represented as a rooted plane tree can thus be decomposed at the root as two sequences of sub-trees separated by the only bud (the other bud hangs above the root).

It is clear that lattice paths with steps \((1, 3)\) and \((1, -1)\) returning to the x-axis while staying always weakly above it are in bijection with sequences of trees in \(A\) by separation at contacts. The parts between contacts are the same family of lattices walks with the extra condition of never touching the x-axis except at both ends. They are in bijection with trees in \(A\) by decomposition at the last returning to the height 3, 2 and 1.

We perform random generation by considering a blossoming tree as a pair of lattice paths of a given total size, and the precomputation consists of storing the relative probability of how the total size is split.

EXAMPLES:

Sage

sage: from sage.combinat.tamari_blossoming_tree import (
....:     TamariBlossomingTrees)
sage: TB = TamariBlossomingTrees(100).random_element()
sage: TB
Tamari blossoming tree ... of size 100
sage: TB in TamariBlossomingTrees()
True
sage: TB in TamariBlossomingTrees(100)
True

Python

>>> from sage.all import *
>>> from sage.combinat.tamari_blossoming_tree import (
...     TamariBlossomingTrees)
>>> TB = TamariBlossomingTrees(Integer(100)).random_element()
>>> TB
Tamari blossoming tree ... of size 100
>>> TB in TamariBlossomingTrees()
True
>>> TB in TamariBlossomingTrees(Integer(100))
True

random_modern_element()

Return a uniformly random modern blossoming tree in the current set of Tamari blossoming trees of a given size.

OUTPUT:

A uniformly random modern blossoming tree in the current instance.

Note

This is a thin wrapper of the random generation facility in ModernBlossomingTreeFactory, which automatically cache the instance, thus also the precomputation within.

EXAMPLES:

Sage

sage: B = TamariBlossomingTrees(100).random_modern_element()
sage: B
Tamari blossoming tree ... of size 100
sage: B.is_modern()
True

Python

>>> from sage.all import *
>>> B = TamariBlossomingTrees(Integer(100)).random_modern_element()
>>> B
Tamari blossoming tree ... of size 100
>>> B.is_modern()
True

random_synchronized_element()

Return a uniformly random synchronized blossoming tree in the current set of Tamari blossoming trees of a given size.

OUTPUT:

A uniformly random synchronized blossoming tree in the current instance.

Note

This is a thin wrapper of the random generation in SynchronizedBlossomingTreeFactory, which automatically cache the instance.

EXAMPLES:

Sage

sage: B = TamariBlossomingTrees(100).random_synchronized_element()
sage: B
Tamari blossoming tree ... of size 100
sage: B.is_synchronized()
True

Python

>>> from sage.all import *
>>> B = TamariBlossomingTrees(Integer(100)).random_synchronized_element()
>>> B
Tamari blossoming tree ... of size 100
>>> B.is_synchronized()
True