# Generalized Tamari lattices¶

These lattices depend on three parameters $$a$$, $$b$$ and $$m$$, where $$a$$ and $$b$$ are coprime positive integers and $$m$$ is a nonnegative integer.

The elements are Dyck paths in the $$(a \times b)$$-rectangle. The order relation depends on $$m$$.

To use the provided functionality, you should import Tamari lattices by typing:

sage: from sage.combinat.tamari_lattices import TamariLattice


or:

sage: from sage.combinat.tamari_lattices import GeneralizedTamariLattice


EXAMPLES:

sage: from sage.combinat.tamari_lattices import TamariLattice
sage: TamariLattice(3)
Finite lattice containing 5 elements

sage: from sage.combinat.tamari_lattices import GeneralizedTamariLattice
sage: GeneralizedTamariLattice(3,2)
Finite lattice containing 2 elements
sage: GeneralizedTamariLattice(4,3)
Finite lattice containing 5 elements


For more detailed information see TamariLattice(), GeneralizedTamariLattice().

sage.combinat.tamari_lattices.GeneralizedTamariLattice(a, b, m=1)

Returns the $$(a,b)$$-Tamari lattice of parameter $$m$$.

INPUT:

• $$a$$ and $$b$$ coprime integers with $$a \geq b$$
• $$m$$ a nonnegative integer such that $$a \geq b \times m$$

OUTPUT:

• a finite lattice (the lattice property is only conjectural in general)

The elements of the lattice are Dyck paths in the $$(a \times b)$$-rectangle.

The parameter $$m$$ (slope) is used only to define the covering relations. When the slope $$m$$ is $$0$$, two paths are comparable if and only if one is always above the other.

The usual Tamari lattice of index $$b$$ is the special case $$a=b+1$$ and $$m=1$$.

Other special cases give the $$m$$-Tamari lattices studied in [BMFPR].

EXAMPLES:

sage: from sage.combinat.tamari_lattices import GeneralizedTamariLattice
sage: GeneralizedTamariLattice(3,2)
Finite lattice containing 2 elements
sage: GeneralizedTamariLattice(4,3)
Finite lattice containing 5 elements
sage: GeneralizedTamariLattice(4,4)
Traceback (most recent call last):
...
ValueError: The numbers a and b must be coprime with a>=b.
sage: GeneralizedTamariLattice(7,5,2)
Traceback (most recent call last):
...
ValueError: The condition a>=b*m does not hold.
sage: P = GeneralizedTamariLattice(5,3);P
Finite lattice containing 7 elements


TESTS:

sage: P.coxeter_transformation()**18 == 1
True


REFERENCES:

 [BMFPR] Bousquet-Melou, E. Fusy, L.-F. Preville Ratelle. “The number of intervals in the m-Tamari lattices”. arXiv:1106.1498
sage.combinat.tamari_lattices.TamariLattice(n)

Returns the $$n$$-th Tamari lattice.

INPUT:

• $$n$$ a nonnegative integer

OUTPUT:

• a finite lattice

The elements of the lattice are Dyck paths in the $$(n+1 \times n)$$-rectangle.

See Tamari lattice for mathematical background.

EXAMPLES:

sage: from sage.combinat.tamari_lattices import TamariLattice
sage: TamariLattice(3)
Finite lattice containing 5 elements

sage.combinat.tamari_lattices.paths_in_triangle(i, j, a, b)

Returns all Dyck paths from $$(0,0)$$ to $$(i,j)$$ in the $$(a \times b)$$-rectangle.

This means that at each step of the path, one has $$a y \geq b x$$.

A path is represented by a sequence of $$0$$ and $$1$$, where $$0$$ is an horizontal step $$(1,0)$$ and $$1$$ is a vertical step $$(0,1)$$.

INPUT:

• $$a$$ and $$b$$ coprime integers with $$a \geq b$$
• $$i$$ and $$j$$ nonnegative integers with $$1 \geq \frac{j}{b} \geq \frac{bi}{a} \geq 0$$

OUTPUT:

• a list of paths

EXAMPLES:

sage: from sage.combinat.tamari_lattices import paths_in_triangle
sage: paths_in_triangle(2,2,2,2)
[(1, 0, 1, 0), (1, 1, 0, 0)]
sage: paths_in_triangle(2,3,4,4)
[(1, 0, 1, 0, 1), (1, 1, 0, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0)]
sage: paths_in_triangle(2,1,4,4)
Traceback (most recent call last):
...
ValueError: The endpoint is not valid.
sage: paths_in_triangle(3,2,5,3)
[(1, 0, 1, 0, 0), (1, 1, 0, 0, 0)]

sage.combinat.tamari_lattices.swap(p, i, m=1)

Performs a covering move in the $$(a,b)$$-Tamari lattice of parameter $$m$$.

The letter at position $$i$$ in $$p$$ must be a $$0$$, followed by at least one $$1$$.

INPUT:

• $$p$$ a Dyck path in the $$(a \times b)$$-rectangle
• $$i$$ an integer between $$0$$ and $$a+b-1$$

OUTPUT:

• a Dyck path in the $$(a \times b)$$-rectangle

EXAMPLES:

sage: from sage.combinat.tamari_lattices import swap
sage: swap((1,0,1,0),1)
(1, 1, 0, 0)
sage: swap((1,0,1,0),6)
Traceback (most recent call last):
...
ValueError: The index is greater than the length of the path.
sage: swap((1,1,0,0,1,1,0,0),3)
(1, 1, 0, 1, 1, 0, 0, 0)
sage: swap((1,1,0,0,1,1,0,0),2)
Traceback (most recent call last):
...
ValueError: There is no such covering move.


TableauTuples

Tiling Solver