# 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 Generalized Tamari lattices by typing:

sage: from sage.combinat.tamari_lattices import GeneralizedTamariLattice


Then,

sage: GeneralizedTamariLattice(3,2)
Finite lattice containing 2 elements
sage: GeneralizedTamariLattice(4,3)
Finite lattice containing 5 elements


The classical Tamari lattices are special cases of this construction and are also available directly using the catalogue of posets, as follows:

sage: posets.TamariLattice(3)
Finite lattice containing 5 elements


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

sage.combinat.tamari_lattices.DexterSemilattice(n)

Return the $$n$$-th Dexter meet-semilattice.

INPUT:

• n – a nonnegative integer (the index)

OUTPUT:

a finite meet-semilattice

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

EXAMPLES:

sage: posets.DexterSemilattice(3)
Finite meet-semilattice containing 5 elements

sage: P = posets.DexterSemilattice(4); P
Finite meet-semilattice containing 14 elements
sage: len(P.maximal_chains())
15
sage: len(P.maximal_elements())
4
sage: P.chain_polynomial()
q^5 + 19*q^4 + 47*q^3 + 42*q^2 + 14*q + 1


REFERENCES:

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

Return 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 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


REFERENCES:

 [BMFPR] (1, 2) M. 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, m=1)

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

Using the slope parameter $$m$$, one can also get the $$m$$-Tamari lattices.

INPUT:

• $$n$$ – a nonnegative integer (the index)
• $$m$$ – an optional nonnegative integer (the slope, default to 1)

OUTPUT:

a finite lattice

In the usual case, the elements of the lattice are Dyck paths in the $$(n+1 \times n)$$-rectangle. For a general slope $$m$$, the elements are Dyck paths in the $$(m n+1 \times n)$$-rectangle.

See Tamari lattice for mathematical background.

EXAMPLES:

sage: posets.TamariLattice(3)
Finite lattice containing 5 elements

sage: posets.TamariLattice(3, 2)
Finite lattice containing 12 elements


REFERENCES:

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

Return 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)

Perform 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,0),1)
(1, 1, 0, 0, 0)
sage: swap((1,1,0,0,1,1,0,0,0),3)
(1, 1, 0, 1, 1, 0, 0, 0, 0)

sage.combinat.tamari_lattices.swap_dexter(p, i)

Perform covering moves in the $$(a,b)$$-Dexter posets.

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 list of Dyck paths in the $$(a \times b)$$-rectangle

EXAMPLES:

sage: from sage.combinat.tamari_lattices import swap_dexter
sage: swap_dexter((1,0,1,0,0),1)
[(1, 1, 0, 0, 0)]
sage: swap_dexter((1,1,0,0,1,1,0,0,0),3)
[(1, 1, 0, 1, 1, 0, 0, 0, 0), (1, 1, 1, 1, 0, 0, 0, 0, 0)]
sage: swap_dexter((1,1,0,1,0,0,0),2)
[]