# Generalized Tamari lattices#

These lattices depend on three parameters $$a$$, $$b$$ and $$m$$, where $$a$$ and $$b$$ are 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

>>> from sage.all import *
>>> 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

>>> from sage.all import *
>>> GeneralizedTamariLattice(Integer(3),Integer(2))
Finite lattice containing 2 elements
>>> GeneralizedTamariLattice(Integer(4),Integer(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

>>> from sage.all import *
>>> posets.TamariLattice(Integer(3))
Finite lattice containing 5 elements


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

sage.combinat.tamari_lattices.DexterSemilattice(n)[source]#

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

>>> from sage.all import *
>>> posets.DexterSemilattice(Integer(3))
Finite meet-semilattice containing 5 elements

>>> P = posets.DexterSemilattice(Integer(4)); P
Finite meet-semilattice containing 14 elements
>>> len(P.maximal_chains())
15
>>> len(P.maximal_elements())
4
>>> 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)[source]#

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

INPUT:

• $$a$$ and $$b$$ – integers with $$a \geq b$$

• $$m$$ – a nonnegative rational number such that $$a \geq b m$$

OUTPUT:

• a finite lattice (special case of the alt $$\nu$$-Tamari lattices in [CC2023])

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 [BMFPR2011], or the rational Tamari lattices when a and b are coprime and m = a/b (see [PRV2017]).

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(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
sage: P = GeneralizedTamariLattice(5, 3, m=5/3); P
Finite lattice containing 7 elements

>>> from sage.all import *
>>> from sage.combinat.tamari_lattices import GeneralizedTamariLattice
>>> GeneralizedTamariLattice(Integer(3),Integer(2))
Finite lattice containing 2 elements
>>> GeneralizedTamariLattice(Integer(4),Integer(3))
Finite lattice containing 5 elements
>>> GeneralizedTamariLattice(Integer(7),Integer(5),Integer(2))
Traceback (most recent call last):
...
ValueError: the condition a>=b*m does not hold
>>> P = GeneralizedTamariLattice(Integer(5),Integer(3)); P
Finite lattice containing 7 elements
>>> P = GeneralizedTamariLattice(Integer(5), Integer(3), m=Integer(5)/Integer(3)); P
Finite lattice containing 7 elements


REFERENCES:

sage.combinat.tamari_lattices.TamariLattice(n, m=1)[source]#

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

>>> from sage.all import *
>>> posets.TamariLattice(Integer(3))
Finite lattice containing 5 elements

>>> posets.TamariLattice(Integer(3), Integer(2))
Finite lattice containing 12 elements


REFERENCES:

sage.combinat.tamari_lattices.paths_in_triangle(i, j, a, b)[source]#

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$$ – integers with $$a \geq b$$

• $$i$$ and $$j$$ – nonnegative integers with $$1 \geq \frac{j}{b} \geq \frac{i}{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)]

>>> from sage.all import *
>>> from sage.combinat.tamari_lattices import paths_in_triangle
>>> paths_in_triangle(Integer(2),Integer(2),Integer(2),Integer(2))
[(1, 0, 1, 0), (1, 1, 0, 0)]
>>> paths_in_triangle(Integer(2),Integer(3),Integer(4),Integer(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)]
>>> paths_in_triangle(Integer(2),Integer(1),Integer(4),Integer(4))
Traceback (most recent call last):
...
ValueError: the endpoint is not valid
>>> paths_in_triangle(Integer(3),Integer(2),Integer(5),Integer(3))
[(1, 0, 1, 0, 0), (1, 1, 0, 0, 0)]

sage.combinat.tamari_lattices.swap(p, i, m=1)[source]#

Perform a covering move in the $$(a,b)$$-Tamari lattice of slope 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: swap((1,0,1,0,1,0,0,0), 1, 1)
(1, 1, 0, 0, 1, 0, 0, 0)
sage: swap((1,0,1,0,1,0,0,0), 1, 5/3)
(1, 1, 0, 1, 0, 0, 0, 0)

>>> from sage.all import *
>>> from sage.combinat.tamari_lattices import swap
>>> swap((Integer(1),Integer(0),Integer(1),Integer(0),Integer(0)),Integer(1))
(1, 1, 0, 0, 0)
>>> swap((Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)),Integer(3))
(1, 1, 0, 1, 1, 0, 0, 0, 0)
>>> swap((Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)), Integer(1), Integer(1))
(1, 1, 0, 0, 1, 0, 0, 0)
>>> swap((Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)), Integer(1), Integer(5)/Integer(3))
(1, 1, 0, 1, 0, 0, 0, 0)

sage.combinat.tamari_lattices.swap_dexter(p, i)[source]#

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)
[]

>>> from sage.all import *
>>> from sage.combinat.tamari_lattices import swap_dexter
>>> swap_dexter((Integer(1),Integer(0),Integer(1),Integer(0),Integer(0)),Integer(1))
[(1, 1, 0, 0, 0)]
>>> swap_dexter((Integer(1),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)),Integer(3))
[(1, 1, 0, 1, 1, 0, 0, 0, 0), (1, 1, 1, 1, 0, 0, 0, 0, 0)]
>>> swap_dexter((Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)),Integer(2))
[]