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:
PathTableauAn 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
selfis 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
Trueifselfis skew andFalseif 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]¶
Convert
selfto 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]]