# Dyck Paths#

This is an implementation of the abstract base class sage.combinat.path_tableaux.path_tableau.PathTableau. This is the simplest implementation of a path tableau and is included to provide a convenient test case and for pedagogical purposes.

In this implementation we have sequences of nonnegative integers. These are required to be the heights Dyck words (except that we do not require the sequence to start or end at height zero). These are in bijection with skew standard tableaux with at most two rows. Sequences which start and end at height zero are in bijection with noncrossing perfect matchings.

AUTHORS:

• Bruce Westbury (2018): initial version

class sage.combinat.path_tableaux.dyck_path.DyckPath(parent, ot, check=True)[source]#

Bases: PathTableau

An instance is the sequence of nonnegative integers given by the heights of a Dyck word.

INPUT:

• a sequence of nonnegative integers

• a two row standard skew tableau

• a Dyck word

• a noncrossing perfect matching

EXAMPLES:

sage: path_tableaux.DyckPath([0,1,2,1,0])
[0, 1, 2, 1, 0]

sage: w = DyckWord([1,1,0,0])
sage: path_tableaux.DyckPath(w)
[0, 1, 2, 1, 0]

sage: p = PerfectMatching([(1,2), (3,4)])
sage: path_tableaux.DyckPath(p)
[0, 1, 0, 1, 0]

sage: t = Tableau([[1,2,4],[3,5,6]])
sage: path_tableaux.DyckPath(t)
[0, 1, 2, 1, 2, 1, 0]

sage: st = SkewTableau([[None, 1,4],[2,3]])
sage: path_tableaux.DyckPath(st)
[1, 2, 1, 0, 1]

>>> from sage.all import *
>>> path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(1),Integer(0)])
[0, 1, 2, 1, 0]

>>> w = DyckWord([Integer(1),Integer(1),Integer(0),Integer(0)])
>>> path_tableaux.DyckPath(w)
[0, 1, 2, 1, 0]

>>> p = PerfectMatching([(Integer(1),Integer(2)), (Integer(3),Integer(4))])
>>> path_tableaux.DyckPath(p)
[0, 1, 0, 1, 0]

>>> t = Tableau([[Integer(1),Integer(2),Integer(4)],[Integer(3),Integer(5),Integer(6)]])
>>> path_tableaux.DyckPath(t)
[0, 1, 2, 1, 2, 1, 0]

>>> st = SkewTableau([[None, Integer(1),Integer(4)],[Integer(2),Integer(3)]])
>>> path_tableaux.DyckPath(st)
[1, 2, 1, 0, 1]


Here we illustrate the slogan that promotion = rotation:

sage: t = path_tableaux.DyckPath([0,1,2,3,2,1,0])
sage: t.to_perfect_matching()
[(0, 5), (1, 4), (2, 3)]

sage: t = t.promotion()
sage: t.to_perfect_matching()
[(0, 3), (1, 2), (4, 5)]

sage: t = t.promotion()
sage: t.to_perfect_matching()
[(0, 1), (2, 5), (3, 4)]

sage: t = t.promotion()
sage: t.to_perfect_matching()
[(0, 5), (1, 4), (2, 3)]

>>> from sage.all import *
>>> t = path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(0)])
>>> t.to_perfect_matching()
[(0, 5), (1, 4), (2, 3)]

>>> t = t.promotion()
>>> t.to_perfect_matching()
[(0, 3), (1, 2), (4, 5)]

>>> t = t.promotion()
>>> t.to_perfect_matching()
[(0, 1), (2, 5), (3, 4)]

>>> t = t.promotion()
>>> t.to_perfect_matching()
[(0, 5), (1, 4), (2, 3)]

check()[source]#

Check that self is a valid path.

EXAMPLES:

sage: path_tableaux.DyckPath([0,1,0,-1,0]) # indirect doctest
Traceback (most recent call last):
...
ValueError: [0, 1, 0, -1, 0] has a negative entry

sage: path_tableaux.DyckPath([0,1,3,1,0]) # indirect doctest
Traceback (most recent call last):
...
ValueError: [0, 1, 3, 1, 0] is not a Dyck path

>>> from sage.all import *
>>> path_tableaux.DyckPath([Integer(0),Integer(1),Integer(0),-Integer(1),Integer(0)]) # indirect doctest
Traceback (most recent call last):
...
ValueError: [0, 1, 0, -1, 0] has a negative entry

>>> path_tableaux.DyckPath([Integer(0),Integer(1),Integer(3),Integer(1),Integer(0)]) # indirect doctest
Traceback (most recent call last):
...
ValueError: [0, 1, 3, 1, 0] is not a Dyck path

descents()[source]#

Return the descent set of self.

EXAMPLES:

sage: path_tableaux.DyckPath([0,1,2,1,2,1,0,1,0]).descents()
{3, 6}

>>> from sage.all import *
>>> path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(1),Integer(2),Integer(1),Integer(0),Integer(1),Integer(0)]).descents()
{3, 6}

is_skew()[source]#

Return True if self is skew and False if not.

EXAMPLES:

sage: path_tableaux.DyckPath([0,1,2,1]).is_skew()
False

sage: path_tableaux.DyckPath([1,0,1,2,1]).is_skew()
True

>>> from sage.all import *
>>> path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(1)]).is_skew()
False

>>> path_tableaux.DyckPath([Integer(1),Integer(0),Integer(1),Integer(2),Integer(1)]).is_skew()
True

local_rule(i)[source]#

This has input a list of objects. This method first takes the list of objects of length three consisting of the $$(i-1)$$-st, $$i$$-th and $$(i+1)$$-term and applies the rule. It then replaces the $$i$$-th object by the object returned by the rule.

EXAMPLES:

sage: t = path_tableaux.DyckPath([0,1,2,3,2,1,0])
sage: t.local_rule(3)
[0, 1, 2, 1, 2, 1, 0]

>>> from sage.all import *
>>> t = path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(0)])
>>> t.local_rule(Integer(3))
[0, 1, 2, 1, 2, 1, 0]

to_DyckWord()[source]#

Converts self to a Dyck word.

EXAMPLES:

sage: c = path_tableaux.DyckPath([0,1,2,1,0])
sage: c.to_DyckWord()
[1, 1, 0, 0]

>>> from sage.all import *
>>> c = path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(1),Integer(0)])
>>> c.to_DyckWord()
[1, 1, 0, 0]

to_perfect_matching()[source]#

Return the perfect matching associated to self.

EXAMPLES:

sage: path_tableaux.DyckPath([0,1,2,1,2,1,0,1,0]).to_perfect_matching()
[(0, 5), (1, 2), (3, 4), (6, 7)]

>>> from sage.all import *
>>> path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(1),Integer(2),Integer(1),Integer(0),Integer(1),Integer(0)]).to_perfect_matching()
[(0, 5), (1, 2), (3, 4), (6, 7)]

to_tableau()[source]#

Return the skew tableau associated to self.

EXAMPLES:

sage: T = path_tableaux.DyckPath([0,1,2,3,2,3])
sage: T.to_tableau()
[[1, 2, 3, 5], [4]]

sage: U = path_tableaux.DyckPath([2,3,2,3])
sage: U.to_tableau()
[[None, None, 1, 3], [2]]

>>> from sage.all import *
>>> T = path_tableaux.DyckPath([Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(3)])
>>> T.to_tableau()
[[1, 2, 3, 5], [4]]

>>> U = path_tableaux.DyckPath([Integer(2),Integer(3),Integer(2),Integer(3)])
>>> U.to_tableau()
[[None, None, 1, 3], [2]]

to_word()[source]#

Return the word in the alphabet $$\{0,1\}$$ associated to self.

EXAMPLES:

sage: path_tableaux.DyckPath([1,0,1,2,1]).to_word()
[0, 1, 1, 0]

>>> from sage.all import *
>>> path_tableaux.DyckPath([Integer(1),Integer(0),Integer(1),Integer(2),Integer(1)]).to_word()
[0, 1, 1, 0]

class sage.combinat.path_tableaux.dyck_path.DyckPaths[source]#

Bases: PathTableaux

The parent class for DyckPath.

Element[source]#

alias of DyckPath