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

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]

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)]
check()#

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
descents()#

Return the descent set of self.

EXAMPLES:

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

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
local_rule(i)#

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]
to_DyckWord()#

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]
to_perfect_matching()#

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)]
to_tableau()#

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]]
to_word()#

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]
class sage.combinat.path_tableaux.dyck_path.DyckPaths#

Bases: PathTableaux

The parent class for DyckPath.

Element#

alias of DyckPath