A class of an object enumerated by the Catalan numbers, see [Sta1999], [Sta] for details.
AUTHORS:
REFERENCES:
[Sta1999] | (1, 2, 3) R. Stanley, Enumerative Combinatorics, Volume 2. Cambridge University Press, 2001. |
[Sta] | (1, 2, 3) R. Stanley, electronic document containing the list of Catalan objects at http://www-math.mit.edu/~rstan/ec/catalan.pdf |
[Hag2008] | (1, 2, 3, 4, 5) The ![]() |
Bases: sage.combinat.dyck_word.DyckWords
Abstract base class for all complete Dyck words.
alias of DyckWord_complete
Return the Dyck word associated to the given Catalan code code.
A Catalan code is a sequence of non–negative integers such
that if
and
and
and
then
.
The Catalan code of a Dyck word is example (x) in Richard Stanley’s exercises on combinatorial interpretations for Catalan objects. The code in this example is the reverse of the description provided there. See [Sta1999] and [Sta].
EXAMPLES:
sage: DyckWords().from_Catalan_code([])
[]
sage: DyckWords().from_Catalan_code([0])
[1, 0]
sage: DyckWords().from_Catalan_code([0, 1])
[1, 1, 0, 0]
sage: DyckWords().from_Catalan_code([0, 0])
[1, 0, 1, 0]
Return the Dyck word associated to the given area sequence code.
See to_area_sequence() for a definition of the area sequence of a Dyck word.
See also
area(), to_area_sequence().
INPUT:
EXAMPLES:
sage: DyckWords().from_area_sequence([])
[]
sage: DyckWords().from_area_sequence([0])
[1, 0]
sage: DyckWords().from_area_sequence([0, 1])
[1, 1, 0, 0]
sage: DyckWords().from_area_sequence([0, 0])
[1, 0, 1, 0]
Bijection from non-decreasing parking functions. See there the method to_dyck_word() for more information.
EXAMPLES:
sage: D = DyckWords()
sage: D.from_non_decreasing_parking_function([])
[]
sage: D.from_non_decreasing_parking_function([1])
[1, 0]
sage: D.from_non_decreasing_parking_function([1,1])
[1, 1, 0, 0]
sage: D.from_non_decreasing_parking_function([1,2])
[1, 0, 1, 0]
sage: D.from_non_decreasing_parking_function([1,1,1])
[1, 1, 1, 0, 0, 0]
sage: D.from_non_decreasing_parking_function([1,2,3])
[1, 0, 1, 0, 1, 0]
sage: D.from_non_decreasing_parking_function([1,1,3,3,4,6,6])
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]
TESTS:
sage: D.from_non_decreasing_parking_function(NonDecreasingParkingFunction([]))
[]
sage: D.from_non_decreasing_parking_function(NonDecreasingParkingFunction([1,1,3,3,4,6,6]))
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]
Convert a noncrossing partition ncp to a Dyck word.
TESTS:
sage: DyckWord(noncrossing_partition=[[1,2]]) # indirect doctest
[1, 1, 0, 0]
sage: DyckWord(noncrossing_partition=[[1],[2]])
[1, 0, 1, 0]
sage: dws = DyckWords(5).list()
sage: ncps = map( lambda x: x.to_noncrossing_partition(), dws)
sage: dws2 = map( lambda x: DyckWord(noncrossing_partition=x), ncps)
sage: dws == dws2
True
Bases: sage.combinat.dyck_word.CompleteDyckWords, sage.combinat.dyck_word.DyckWords_all
All complete Dyck words.
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
The poset of complete Dyck words compared componentwise by heights. This is, D is smaller than or equal to D' if it is weakly below D'.
Compare two Dyck words of equal size, and return True if all of the heights of dw1 are less than or equal to the respective heights of dw2 .
See also
EXAMPLES:
sage: poset = DyckWords().height_poset()
sage: poset.le(DyckWord([]), DyckWord([]))
True
sage: poset.le(DyckWord([1,0]), DyckWord([1,0]))
True
sage: poset.le(DyckWord([1,0,1,0]), DyckWord([1,1,0,0]))
True
sage: poset.le(DyckWord([1,1,0,0]), DyckWord([1,0,1,0]))
False
sage: [poset.le(dw1, dw2)
....: for dw1 in DyckWords(3) for dw2 in DyckWords(3)]
[True, True, True, True, True, False, True, False, True, True, False, False, True, True, True, False, False, False, True, True, False, False, False, False, True]
Bases: sage.combinat.dyck_word.CompleteDyckWords, sage.combinat.dyck_word.DyckWords_size
All complete Dyck words of a given size.
Return the number of complete Dyck words of semilength , i.e. the
-th Catalan number.
EXAMPLES:
sage: DyckWords(4).cardinality()
14
sage: ns = range(9)
sage: dws = [DyckWords(n) for n in ns]
sage: all([ dw.cardinality() == len(dw.list()) for dw in dws])
True
Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element
A Dyck word.
A Dyck word is a sequence of open and close symbols such that every close
symbol has a corresponding open symbol preceding it. That is to say, a
Dyck word of length is a list with
entries 1 and
entries 0 such that the first
entries always have at least as many 1s
among them as 0s. (Here, the 1 serves as the open symbol and the 0 as the
close symbol.) Alternatively, the alphabet 1 and 0 can be replaced by
other characters such as ‘(‘ and ‘)’.
A Dyck word is complete if every open symbol moreover has a corresponding close symbol.
A Dyck word may also be specified by either a noncrossing partition or by an area sequence or the sequence of heights.
A Dyck word may also be thought of as a lattice path in the
grid, starting at the origin
, and with steps in the North
and east
directions such that it does not pass
below the
diagonal. The diagonal is referred to as the “main
diagonal” in the documentation. A North step is represented by a 1 in
the list and an East step is represented by a 0.
Equivalently, the path may be represented with steps in
the and the
direction such that it does not
pass below the horizontal axis.
A path representing a Dyck word (either using and
steps, or
using
and
steps) is called a Dyck path.
EXAMPLES:
sage: dw = DyckWord([1, 0, 1, 0]); dw
[1, 0, 1, 0]
sage: print dw
()()
sage: print dw.height()
1
sage: dw.to_noncrossing_partition()
[[1], [2]]
sage: DyckWord('()()')
[1, 0, 1, 0]
sage: DyckWord('(())')
[1, 1, 0, 0]
sage: DyckWord('((')
[1, 1]
sage: DyckWord('')
[]
sage: DyckWord(noncrossing_partition=[[1],[2]])
[1, 0, 1, 0]
sage: DyckWord(noncrossing_partition=[[1,2]])
[1, 1, 0, 0]
sage: DyckWord(noncrossing_partition=[])
[]
sage: DyckWord(area_sequence=[0,0])
[1, 0, 1, 0]
sage: DyckWord(area_sequence=[0,1])
[1, 1, 0, 0]
sage: DyckWord(area_sequence=[0,1,2,2,0,1,1,2])
[1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
sage: DyckWord(area_sequence=[])
[]
sage: DyckWord(heights_sequence=(0,1,0,1,0))
[1, 0, 1, 0]
sage: DyckWord(heights_sequence=(0,1,2,1,0))
[1, 1, 0, 0]
sage: DyckWord(heights_sequence=(0,))
[]
sage: print DyckWord([1,0,1,1,0,0]).to_path_string()
/\
/\/ \
sage: DyckWord([1,0,1,1,0,0]).pretty_print()
___
| x
_| .
| . .
Report the position for the parenthesis in self that matches the one at position pos .
INPUT:
OUTPUT:
EXAMPLES:
sage: DyckWord([1, 0]).associated_parenthesis(0)
1
sage: DyckWord([1, 0, 1, 0]).associated_parenthesis(0)
1
sage: DyckWord([1, 0, 1, 0]).associated_parenthesis(1)
0
sage: DyckWord([1, 0, 1, 0]).associated_parenthesis(2)
3
sage: DyckWord([1, 0, 1, 0]).associated_parenthesis(3)
2
sage: DyckWord([1, 1, 0, 0]).associated_parenthesis(0)
3
sage: DyckWord([1, 1, 0, 0]).associated_parenthesis(2)
1
sage: DyckWord([1, 1, 0]).associated_parenthesis(1)
2
sage: DyckWord([1, 1]).associated_parenthesis(0)
This is deprecated in trac ticket #14875. Use instead DyckWords_all().from_heights().
EXAMPLES:
sage: from sage.combinat.dyck_word import DyckWord
sage: DyckWord.from_heights((0,))
doctest:...: DeprecationWarning: this method is deprecated. Use DyckWords(complete=False).from_heights instead.
See http://trac.sagemath.org/14875 for details.
[]
Return the height of self.
We view the Dyck word as a Dyck path from to
in the first quadrant by letting 1‘s represent
steps in the direction
and 0‘s represent steps in
the direction
.
The height is the maximum -coordinate reached.
See also
EXAMPLES:
sage: DyckWord([]).height()
0
sage: DyckWord([1,0]).height()
1
sage: DyckWord([1, 1, 0, 0]).height()
2
sage: DyckWord([1, 1, 0, 1, 0]).height()
2
sage: DyckWord([1, 1, 0, 0, 1, 0]).height()
2
sage: DyckWord([1, 0, 1, 0]).height()
1
sage: DyckWord([1, 1, 0, 0, 1, 1, 1, 0, 0, 0]).height()
3
Return the heights of self.
We view the Dyck word as a Dyck path from to
in the first quadrant by letting 1‘s represent
steps in the direction
and 0‘s represent steps in
the direction
.
The heights is the sequence of the -coordinates of all
lattice points along the path.
See also
EXAMPLES:
sage: DyckWord([]).heights()
(0,)
sage: DyckWord([1,0]).heights()
(0, 1, 0)
sage: DyckWord([1, 1, 0, 0]).heights()
(0, 1, 2, 1, 0)
sage: DyckWord([1, 1, 0, 1, 0]).heights()
(0, 1, 2, 1, 2, 1)
sage: DyckWord([1, 1, 0, 0, 1, 0]).heights()
(0, 1, 2, 1, 0, 1, 0)
sage: DyckWord([1, 0, 1, 0]).heights()
(0, 1, 0, 1, 0)
sage: DyckWord([1, 1, 0, 0, 1, 1, 1, 0, 0, 0]).heights()
(0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0)
Return True if self is complete.
A Dyck word is complete if
contains as many closers as openers.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).is_complete()
True
sage: DyckWord([1, 0, 1, 1, 0]).is_complete()
False
TESTS:
sage: DyckWord([]).is_complete()
True
Return the latex options for use in the _latex_ function as a dictionary. The default values are set using the global options.
EXAMPLES:
sage: D = DyckWord([1,0,1,0,1,0])
sage: D.latex_options()
{'valleys': False, 'peaks': False, 'tikz_scale': 1, 'color': 'black', 'diagonal': False, 'bounce path': False, 'line width': 2}
Return the length of self.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).length()
4
sage: DyckWord([1, 0, 1, 1, 0]).length()
5
TESTS:
sage: DyckWord([]).length()
0
This is deprecated in trac ticket #14875. Use instead DyckWords_all.min_from_heights().
EXAMPLES:
sage: from sage.combinat.dyck_word import DyckWord
sage: DyckWord.min_from_heights((0,))
doctest:...: DeprecationWarning: this method is deprecated. Use DyckWords(complete=False).from_min_heights instead.
See http://trac.sagemath.org/14875 for details.
[]
Return the number of close symbols in self.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).number_of_close_symbols()
2
sage: DyckWord([1, 0, 1, 1, 0]).number_of_close_symbols()
2
TESTS:
sage: DyckWord([]).number_of_close_symbols()
0
Return a the number of positions in self where there are two
consecutive ‘s.
EXAMPLES:
sage: DyckWord([1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0]).number_of_double_rises()
2
sage: DyckWord([1, 1, 0, 0]).number_of_double_rises()
1
sage: DyckWord([1, 0, 1, 0]).number_of_double_rises()
0
Return the length of the initial run of self
OUPUT:
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).number_of_initial_rises()
1
sage: DyckWord([1, 1, 0, 0]).number_of_initial_rises()
2
sage: DyckWord([1, 1, 0, 0, 1, 0]).number_of_initial_rises()
2
sage: DyckWord([1, 0, 1, 1, 0, 0]).number_of_initial_rises()
1
TESTS:
sage: DyckWord([]).number_of_initial_rises()
0
sage: DyckWord([1, 0]).number_of_initial_rises()
1
Return the number of open symbols in self.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).number_of_open_symbols()
2
sage: DyckWord([1, 0, 1, 1, 0]).number_of_open_symbols()
3
TESTS:
sage: DyckWord([]).number_of_open_symbols()
0
The number of peaks of the Dyck path associated to self .
See also
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).number_of_peaks()
2
sage: DyckWord([1, 1, 0, 0]).number_of_peaks()
1
sage: DyckWord([1,1,0,1,0,1,0,0]).number_of_peaks()
3
sage: DyckWord([]).number_of_peaks()
0
Return the number of touches of self at the main diagonal.
OUTPUT:
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).number_of_touch_points()
2
sage: DyckWord([1, 1, 0, 0]).number_of_touch_points()
1
sage: DyckWord([1, 1, 0, 0, 1, 0]).number_of_touch_points()
2
sage: DyckWord([1, 0, 1, 1, 0, 0]).number_of_touch_points()
2
TESTS:
sage: DyckWord([]).number_of_touch_points()
0
Return the number of valleys of self.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).number_of_valleys()
1
sage: DyckWord([1, 1, 0, 0]).number_of_valleys()
0
sage: DyckWord([1, 1, 0, 0, 1, 0]).number_of_valleys()
1
sage: DyckWord([1, 0, 1, 1, 0, 0]).number_of_valleys()
1
TESTS:
sage: DyckWord([]).number_of_valleys()
0
sage: DyckWord([1, 0]).number_of_valleys()
0
Return a list of the positions of the peaks of a Dyck word.
A peak is followed by a
. Note that this does not agree with
the definition given in [Hag2008].
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).peaks()
[0, 2]
sage: DyckWord([1, 1, 0, 0]).peaks()
[1]
sage: DyckWord([1,1,0,1,0,1,0,0]).peaks() # Haglund's def gives 2
[1, 3, 5]
Return the number of vertical steps before the Dyck path returns to the main diagonal.
EXAMPLES:
sage: DyckWord([1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0]).position_of_first_return()
1
sage: DyckWord([1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0]).position_of_first_return()
7
sage: DyckWord([1, 1, 0, 0]).position_of_first_return()
2
sage: DyckWord([1, 0, 1, 0]).position_of_first_return()
1
sage: DyckWord([]).position_of_first_return()
0
Return a list of positions in self where there are two
consecutive ‘s.
EXAMPLES:
sage: DyckWord([1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0]).positions_of_double_rises()
[2, 5]
sage: DyckWord([1, 1, 0, 0]).positions_of_double_rises()
[0]
sage: DyckWord([1, 0, 1, 0]).positions_of_double_rises()
[]
Display a DyckWord as a lattice path in the grid.
If the type is “N-E”, then the a cell below the diagonal is indicated by a period, a cell below the path, but above the diagonal are indicated by an x. If a list of labels is included, they are displayed along the vertical edges of the Dyck path.
If the type is “NE-SE”, then the path is simply printed as up steps and down steps.
INPUT:
EXAMPLES:
sage: for D in DyckWords(3): D.pretty_print()
_
_|
_| .
| . .
___
| x
_| .
| . .
_
___|
| x .
| . .
___
_| x
| x .
| . .
_____
| x x
| x .
| . .
sage: for D in DyckWords(3): D.pretty_print(type="NE-SE")
/\/\/\
/\
/\/ \
/\
/ \/\
/\/\
/ \
/\
/ \
/ \
sage: D = DyckWord([1,1,1,0,1,0,0,1,1])
sage: D.pretty_print()
| x x
___| x .
_| x x . .
| x x . . .
| x . . . .
| . . . . .
sage: D = DyckWord([1,1,1,0,1,0,0,1,1,0])
sage: D.pretty_print()
_
| x x
___| x .
_| x x . .
| x x . . .
| x . . . .
| . . . . .
sage: D = DyckWord([1,1,1,0,1,0,0,1,1,0,0])
sage: D.pretty_print()
___
| x x
___| x .
_| x x . .
| x x . . .
| x . . . .
| . . . . .
sage: DyckWord(area_sequence=[0,1,0]).pretty_print(labelling=[1,3,2])
_
___|2
|3x .
|1 . .
sage: DyckWord(area_sequence=[0,1,0]).pretty_print(labelling=[1,3,2],underpath=False)
_
___| 2
| x . 3
| . . 1
sage: DyckWord(area_sequence=[0,1,1,2,3,2,3,3,2,0,1,1,2,3,4,2,3]).pretty_print()
_______
| x x x
_____| x x .
| x x x x . .
| x x x . . .
| x x . . . .
_| x . . . . .
| x . . . . . .
_____| . . . . . . .
___| x x . . . . . . . .
_| x x x . . . . . . . . .
| x x x . . . . . . . . . .
___| x x . . . . . . . . . . .
| x x x . . . . . . . . . . . .
| x x . . . . . . . . . . . . .
_| x . . . . . . . . . . . . . .
| x . . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . .
sage: DyckWord(area_sequence=[0,1,1,2,3,2,3,3,2,0,1,1,2,3,4,2,3]).pretty_print(labelling=range(17),underpath=False)
_______
| x x x 16
_____| x x . 15
| x x x x . . 14
| x x x . . . 13
| x x . . . . 12
_| x . . . . . 11
| x . . . . . . 10
_____| . . . . . . . 9
___| x x . . . . . . . . 8
_| x x x . . . . . . . . . 7
| x x x . . . . . . . . . . 6
___| x x . . . . . . . . . . . 5
| x x x . . . . . . . . . . . . 4
| x x . . . . . . . . . . . . . 3
_| x . . . . . . . . . . . . . . 2
| x . . . . . . . . . . . . . . . 1
| . . . . . . . . . . . . . . . . 0
sage: DyckWord([]).pretty_print()
.
Display a DyckWord as a lattice path in the grid.
If the type is “N-E”, then the a cell below the diagonal is indicated by a period, a cell below the path, but above the diagonal are indicated by an x. If a list of labels is included, they are displayed along the vertical edges of the Dyck path.
If the type is “NE-SE”, then the path is simply printed as up steps and down steps.
INPUT:
EXAMPLES:
sage: for D in DyckWords(3): D.pretty_print()
_
_|
_| .
| . .
___
| x
_| .
| . .
_
___|
| x .
| . .
___
_| x
| x .
| . .
_____
| x x
| x .
| . .
sage: for D in DyckWords(3): D.pretty_print(type="NE-SE")
/\/\/\
/\
/\/ \
/\
/ \/\
/\/\
/ \
/\
/ \
/ \
sage: D = DyckWord([1,1,1,0,1,0,0,1,1])
sage: D.pretty_print()
| x x
___| x .
_| x x . .
| x x . . .
| x . . . .
| . . . . .
sage: D = DyckWord([1,1,1,0,1,0,0,1,1,0])
sage: D.pretty_print()
_
| x x
___| x .
_| x x . .
| x x . . .
| x . . . .
| . . . . .
sage: D = DyckWord([1,1,1,0,1,0,0,1,1,0,0])
sage: D.pretty_print()
___
| x x
___| x .
_| x x . .
| x x . . .
| x . . . .
| . . . . .
sage: DyckWord(area_sequence=[0,1,0]).pretty_print(labelling=[1,3,2])
_
___|2
|3x .
|1 . .
sage: DyckWord(area_sequence=[0,1,0]).pretty_print(labelling=[1,3,2],underpath=False)
_
___| 2
| x . 3
| . . 1
sage: DyckWord(area_sequence=[0,1,1,2,3,2,3,3,2,0,1,1,2,3,4,2,3]).pretty_print()
_______
| x x x
_____| x x .
| x x x x . .
| x x x . . .
| x x . . . .
_| x . . . . .
| x . . . . . .
_____| . . . . . . .
___| x x . . . . . . . .
_| x x x . . . . . . . . .
| x x x . . . . . . . . . .
___| x x . . . . . . . . . . .
| x x x . . . . . . . . . . . .
| x x . . . . . . . . . . . . .
_| x . . . . . . . . . . . . . .
| x . . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . .
sage: DyckWord(area_sequence=[0,1,1,2,3,2,3,3,2,0,1,1,2,3,4,2,3]).pretty_print(labelling=range(17),underpath=False)
_______
| x x x 16
_____| x x . 15
| x x x x . . 14
| x x x . . . 13
| x x . . . . 12
_| x . . . . . 11
| x . . . . . . 10
_____| . . . . . . . 9
___| x x . . . . . . . . 8
_| x x x . . . . . . . . . 7
| x x x . . . . . . . . . . 6
___| x x . . . . . . . . . . . 5
| x x x . . . . . . . . . . . . 4
| x x . . . . . . . . . . . . . 3
_| x . . . . . . . . . . . . . . 2
| x . . . . . . . . . . . . . . . 1
| . . . . . . . . . . . . . . . . 0
sage: DyckWord([]).pretty_print()
.
Deprecated: Use returns_to_zero() instead. See trac ticket #13550 for details.
Return a list of positions where self has height ,
excluding the position
.
EXAMPLES:
sage: DyckWord([]).returns_to_zero()
[]
sage: DyckWord([1, 0]).returns_to_zero()
[2]
sage: DyckWord([1, 0, 1, 0]).returns_to_zero()
[2, 4]
sage: DyckWord([1, 1, 0, 0]).returns_to_zero()
[4]
The sequences of lengths of runs of ‘s in self. Also equal to
the sequence of lengths of vertical segments in the Dyck path.
EXAMPLES:
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).pretty_print()
___
| x
_______| .
| x x x . .
| x x . . .
_| x . . . .
| x . . . . .
| . . . . . .
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).rise_composition()
[2, 3, 2]
sage: DyckWord([1,1,0,0]).rise_composition()
[2]
sage: DyckWord([1,0,1,0]).rise_composition()
[1, 1]
TESTS:
sage: DyckWord.set_ascii_art("path")
doctest:...: DeprecationWarning: set_ascii_art is deprecated. Use DyckWords.global_options instead.
See http://trac.sagemath.org/14875 for details.
Set the latex options for use in the _latex_ function. The default values are set in the __init__ function.
INPUT:
EXAMPLES:
sage: D = DyckWord([1,0,1,0,1,0])
sage: D.set_latex_options({"tikz_scale":2})
sage: D.set_latex_options({"valleys":True, "color":"blue"})
Deprecated: Use number_of_open_symbols() instead. See trac ticket #13550 for details.
Return the area sequence of the Dyck word self.
The area sequence of a Dyck word is defined as follows:
Representing the Dyck word
as a Dyck path from
to
using
and
steps (this involves padding
by
steps until
reaches the main diagonal if
is not
already a complete Dyck path), the area sequence of
is the
sequence
, where
is the number
of full cells in the
-th row of the rectangle
which lie completely above the diagonal.
(The cells are the regions into which the rectangle is
subdivided by the lines
with
integer and the lines
with
integer. The
-th row consists of all the
cells between the lines
and
.)
An alternative definition:
Representing the Dyck word as a Dyck path consisting of
and
steps, the area sequence is the sequence of
ordinates of all lattice points on the path which are
starting points of
steps.
A list of integers is the area sequence of some Dyck path
if and only if it satisfies
and
for
.
EXAMPLES:
sage: DyckWord([]).to_area_sequence()
[]
sage: DyckWord([1, 0]).to_area_sequence()
[0]
sage: DyckWord([1, 1, 0, 0]).to_area_sequence()
[0, 1]
sage: DyckWord([1, 0, 1, 0]).to_area_sequence()
[0, 0]
sage: all(dw ==
....: DyckWords().from_area_sequence(dw.to_area_sequence())
....: for i in range(6) for dw in DyckWords(i))
True
sage: DyckWord([1,0,1,0,1,0,1,0,1,0]).to_area_sequence()
[0, 0, 0, 0, 0]
sage: DyckWord([1,1,1,1,1,0,0,0,0,0]).to_area_sequence()
[0, 1, 2, 3, 4]
sage: DyckWord([1,1,1,1,0,1,0,0,0,0]).to_area_sequence()
[0, 1, 2, 3, 3]
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).to_area_sequence()
[0, 1, 1, 0, 1, 1, 1]
Return a binary tree recursively constructed from the Dyck path by the sent usemap. The default usemap is 1L0R which means:
INPUT:
Other valid usemap are 1R0L, L1R0, and R1L0 and all corresponding to different recursive definitions of Dyck paths.
EXAMPLES:
sage: dw = DyckWord([1,0])
sage: dw.to_binary_tree()
[., .]
sage: dw = DyckWord([])
sage: dw.to_binary_tree()
.
sage: dw = DyckWord([1,0,1,1,0,0])
sage: dw.to_binary_tree()
[., [[., .], .]]
sage: dw.to_binary_tree("L1R0")
[[., .], [., .]]
sage: dw = DyckWord([1,0,1,1,0,0,1,1,1,0,1,0,0,0])
sage: dw.to_binary_tree() == dw.to_binary_tree("1R0L").left_right_symmetry()
True
sage: dw.to_binary_tree() == dw.to_binary_tree("L1R0").left_border_symmetry()
False
sage: dw.to_binary_tree("1R0L") == dw.to_binary_tree("L1R0").left_border_symmetry()
True
sage: dw.to_binary_tree("R1L0") == dw.to_binary_tree("L1R0").left_right_symmetry()
True
sage: dw.to_binary_tree("R10L")
Traceback (most recent call last):
...
ValueError: R10L is not a correct map
Return the binary tree with consistency with the Tamari order of self.
EXAMPLES:
sage: DyckWord([1,0]).to_binary_tree_tamari()
[., .]
sage: DyckWord([1,0,1,1,0,0]).to_binary_tree_tamari()
[[., .], [., .]]
sage: DyckWord([1,0,1,0,1,0]).to_binary_tree_tamari()
[[[., .], .], .]
A path representation of the Dyck word consisting of steps / and \ .
EXAMPLES:
sage: print DyckWord([1, 0, 1, 0]).to_path_string()
/\/\
sage: print DyckWord([1, 1, 0, 0]).to_path_string()
/\
/ \
sage: print DyckWord([1,1,0,1,1,0,0,1,0,1,0,0]).to_path_string()
/\
/\/ \/\/\
/ \
Return a standard tableau of shape where
is the number of open symbols and
is the number of
close symbols in self.
EXAMPLES:
sage: DyckWord([]).to_standard_tableau()
[]
sage: DyckWord([1, 0]).to_standard_tableau()
[[1], [2]]
sage: DyckWord([1, 1, 0, 0]).to_standard_tableau()
[[1, 2], [3, 4]]
sage: DyckWord([1, 0, 1, 0]).to_standard_tableau()
[[1, 3], [2, 4]]
sage: DyckWord([1]).to_standard_tableau()
[[1]]
sage: DyckWord([1, 0, 1]).to_standard_tableau()
[[1, 3], [2]]
Return a composition which indicates the positions where self returns to the diagonal.
This assumes self to be a complete Dyck word.
OUTPUT:
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).touch_composition()
[1, 1]
sage: DyckWord([1, 1, 0, 0]).touch_composition()
[2]
sage: DyckWord([1, 1, 0, 0, 1, 0]).touch_composition()
[2, 1]
sage: DyckWord([1, 0, 1, 1, 0, 0]).touch_composition()
[1, 2]
sage: DyckWord([]).touch_composition()
[]
Return the abscissae (or, equivalently, ordinates) of the
points where the Dyck path corresponding to self (comprising
and
steps) touches the main diagonal. This includes
the last point (if it is on the main diagonal) but excludes the
beginning point.
Note that these abscissae are precisely the entries of
returns_to_zero() divided by .
OUTPUT:
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).touch_points()
[1, 2]
sage: DyckWord([1, 1, 0, 0]).touch_points()
[2]
sage: DyckWord([1, 1, 0, 0, 1, 0]).touch_points()
[2, 3]
sage: DyckWord([1, 0, 1, 1, 0, 0]).touch_points()
[1, 3]
Return a list of the positions of the valleys of a Dyck word.
A valley is followed by a
.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).valleys()
[1]
sage: DyckWord([1, 1, 0, 0]).valleys()
[]
sage: DyckWord([1,1,0,1,0,1,0,0]).valleys()
[2, 4]
Bases: sage.combinat.backtrack.GenericBacktracker
This class is an iterator for all Dyck words
with opening parentheses and
closing parentheses using
the backtracker class. It is used by the DyckWords_size class.
This is not really meant to be called directly, partially because it fails in a couple corner cases: DWB(0) yields [0], not the empty word, and DWB(k, k+1) yields something (it shouldn’t yield anything). This could be fixed with a sanity check in _rec(), but then we’d be doing the sanity check every time we generate new objects; instead, we do one sanity check in DyckWords and assume here that the sanity check has already been made.
AUTHOR:
Bases: sage.combinat.dyck_word.DyckWord
The class of complete Dyck words. A Dyck word is complete, if it contains as many closers as openers.
For further information on Dyck words, see DyckWords_class.
Deprecated: Use area() instead. See trac ticket #13550 for details.
Return the area for self corresponding to the area of the Dyck path.
One can view a balanced Dyck word as a lattice path from
to
in the first quadrant by letting
‘1’s represent steps in the direction
and ‘0’s
represent steps in the direction
. The resulting
path will remain weakly above the diagonal
.
The area statistic is the number of complete
squares in the integer lattice which are below the path and above
the line . The ‘half-squares’ directly above the
line
do not contribute to this statistic.
EXAMPLES:
sage: dw = DyckWord([1,0,1,0])
sage: dw.area() # 2 half-squares, 0 complete squares
0
sage: dw = DyckWord([1,1,1,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0])
sage: dw.area()
19
sage: DyckWord([1,1,1,1,0,0,0,0]).area()
6
sage: DyckWord([1,1,1,0,1,0,0,0]).area()
5
sage: DyckWord([1,1,1,0,0,1,0,0]).area()
4
sage: DyckWord([1,1,1,0,0,0,1,0]).area()
3
sage: DyckWord([1,0,1,1,0,1,0,0]).area()
2
sage: DyckWord([1,1,0,1,1,0,0,0]).area()
4
sage: DyckWord([1,1,0,0,1,1,0,0]).area()
2
sage: DyckWord([1,0,1,1,1,0,0,0]).area()
3
sage: DyckWord([1,0,1,1,0,0,1,0]).area()
1
sage: DyckWord([1,0,1,0,1,1,0,0]).area()
1
sage: DyckWord([1,1,0,0,1,0,1,0]).area()
1
sage: DyckWord([1,1,0,1,0,0,1,0]).area()
2
sage: DyckWord([1,1,0,1,0,1,0,0]).area()
3
sage: DyckWord([1,0,1,0,1,0,1,0]).area()
0
Return the image of self under the map which sends a
Dyck word with area equal to and dinv equal to
to a
Dyck word with bounce equal to
and area equal to
.
The inverse of this map is bounce_area_to_area_dinv_map().
For a definition of this map, see [Hag2008] p. 50 where it is called
. However, this map differs from Haglund’s map by an application
of reverse() (as does the definition of the bounce()
statistic).
EXAMPLES:
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).area_dinv_to_bounce_area_map()
[1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0]
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).area()
5
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).dinv()
13
sage: DyckWord([1,1,1,1,1,0,0,0,1,0,0,1,0,0]).area()
13
sage: DyckWord([1,1,1,1,1,0,0,0,1,0,0,1,0,0]).bounce()
5
sage: DyckWord([1,1,1,1,1,0,0,0,1,0,0,1,0,0]).area_dinv_to_bounce_area_map()
[1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0]
sage: DyckWord([1,1,0,0]).area_dinv_to_bounce_area_map()
[1, 0, 1, 0]
sage: DyckWord([1,0,1,0]).area_dinv_to_bounce_area_map()
[1, 1, 0, 0]
Deprecated: Use bounce() instead. See trac ticket #13550 for details.
Return the bounce statistic of self due to J. Haglund, see [Hag2008].
One can view a balanced Dyck word as a lattice path from to
in the first quadrant by letting ‘1’s represent steps in
the direction
and ‘0’s represent steps in the direction
. The resulting path will remain weakly above the diagonal
.
We describe the bounce statistic of such a path in terms of what is known as the “bounce path”.
We can think of our bounce path as describing the trail of a billiard
ball shot West from , which “bounces” down whenever it
encounters a vertical step and “bounces” left when it encounters the
line
.
The bouncing ball will strike the diagonal at the places
We define the bounce to be the sum .
EXAMPLES:
sage: DyckWord([1,1,1,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0]).bounce()
7
sage: DyckWord([1,1,1,1,0,0,0,0]).bounce()
0
sage: DyckWord([1,1,1,0,1,0,0,0]).bounce()
1
sage: DyckWord([1,1,1,0,0,1,0,0]).bounce()
2
sage: DyckWord([1,1,1,0,0,0,1,0]).bounce()
3
sage: DyckWord([1,0,1,1,0,1,0,0]).bounce()
3
sage: DyckWord([1,1,0,1,1,0,0,0]).bounce()
1
sage: DyckWord([1,1,0,0,1,1,0,0]).bounce()
2
sage: DyckWord([1,0,1,1,1,0,0,0]).bounce()
1
sage: DyckWord([1,0,1,1,0,0,1,0]).bounce()
4
sage: DyckWord([1,0,1,0,1,1,0,0]).bounce()
3
sage: DyckWord([1,1,0,0,1,0,1,0]).bounce()
5
sage: DyckWord([1,1,0,1,0,0,1,0]).bounce()
4
sage: DyckWord([1,1,0,1,0,1,0,0]).bounce()
2
sage: DyckWord([1,0,1,0,1,0,1,0]).bounce()
6
Return the image of the Dyck word under the map which sends a
Dyck word with bounce equal to and area equal to
to a
Dyck word with area equal to
and dinv equal to
.
This implementation uses a recursive method by saying that
the last entry in the area sequence of is equal to the number of
touch points of the Dyck path minus 1 of the image of this map.
The inverse of this map is area_dinv_to_bounce_area_map().
For a definition of this map, see [Hag2008] p. 50 where it is called
. However, this map differs from Haglund’s map by an
application of reverse() (as does the definition of the
bounce() statistic).
EXAMPLES:
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).bounce_area_to_area_dinv_map()
[1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0]
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).area()
5
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).bounce()
9
sage: DyckWord([1,1,0,0,1,1,1,1,0,0,1,0,0,0]).area()
9
sage: DyckWord([1,1,0,0,1,1,1,1,0,0,1,0,0,0]).dinv()
5
sage: all(D==D.bounce_area_to_area_dinv_map().area_dinv_to_bounce_area_map() for D in DyckWords(6))
True
sage: DyckWord([1,1,0,0]).bounce_area_to_area_dinv_map()
[1, 0, 1, 0]
sage: DyckWord([1,0,1,0]).bounce_area_to_area_dinv_map()
[1, 1, 0, 0]
Return the bounce path of self formed by starting at and
traveling West until encountering the first vertical step of self,
then South until encountering the diagonal, then West again to hit
the path, etc. until the
point is reached. The path followed
by this walk is the bounce path.
See also
EXAMPLES:
sage: DyckWord([1,1,0,1,0,0]).bounce_path()
[1, 0, 1, 1, 0, 0]
sage: DyckWord([1,1,1,0,0,0]).bounce_path()
[1, 1, 1, 0, 0, 0]
sage: DyckWord([1,0,1,0,1,0]).bounce_path()
[1, 0, 1, 0, 1, 0]
sage: DyckWord([1,1,1,1,0,0,1,0,0,0]).bounce_path()
[1, 1, 0, 0, 1, 1, 1, 0, 0, 0]
TESTS:
sage: DyckWord([]).bounce_path()
[]
sage: DyckWord([1,0]).bounce_path()
[1, 0]
The characteristic function of self is the sum of
over all permutation
fillings of the Dyck path representing self, where
is the descent composition of the inverse of the
reading word of the filling.
INPUT:
OUTPUT:
EXAMPLES:
sage: R = QQ['q','t'].fraction_field()
sage: (q,t) = R.gens()
sage: f = sum(t**D.area()*D.characteristic_symmetric_function() for D in DyckWords(3)); f
(q^3+q^2*t+q*t^2+t^3+q*t)*s[1, 1, 1] + (q^2+q*t+t^2+q+t)*s[2, 1] + s[3]
sage: f.nabla(power=-1)
s[1, 1, 1]
Return the involution of self with a recursive definition.
If a Dyck word decomposes as
where
and
are complete Dyck words then the decomposition reverse is
.
EXAMPLES:
sage: DyckWord([1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0]).decomposition_reverse()
[1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).decomposition_reverse()
[1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0]
sage: DyckWord([1,1,0,0]).decomposition_reverse()
[1, 0, 1, 0]
sage: DyckWord([1,0,1,0]).decomposition_reverse()
[1, 1, 0, 0]
Return the dinv statistic of self due to M. Haiman, see [Hag2008].
If a labeling is provided then this function returns the dinv of the labeled Dyck word.
INPUT:
OUTPUT:
EXAMPLES:
sage: DyckWord([1,0,1,0,1,0,1,0,1,0]).dinv()
10
sage: DyckWord([1,1,1,1,1,0,0,0,0,0]).dinv()
0
sage: DyckWord([1,1,1,1,0,1,0,0,0,0]).dinv()
1
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).dinv()
13
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).dinv([1,2,3,4,5,6,7])
11
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).dinv([6,7,5,3,4,2,1])
2
Decompose a Dyck word into a pair of Dyck words (potentially empty) where the first word consists of the word after the first up step and the corresponding matching closing parenthesis.
EXAMPLES:
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).first_return_decomposition()
([1, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0])
sage: DyckWord([1,1,0,0]).first_return_decomposition()
([1, 0], [])
sage: DyckWord([1,0,1,0]).first_return_decomposition()
([], [1, 0])
This is deprecated in trac ticket #14875. Use instead CompleteDyckWords.from_Catalan_code().
EXAMPLES:
sage: from sage.combinat.dyck_word import DyckWord_complete
sage: DyckWord_complete.from_Catalan_code([])
doctest:...: DeprecationWarning: this method is deprecated. Use DyckWords().from_Catalan_code instead.
See http://trac.sagemath.org/14875 for details.
[]
This is deprecated in trac ticket #14875. Use instead CompleteDyckWords.from_area_sequence().
EXAMPLES:
sage: from sage.combinat.dyck_word import DyckWord_complete
sage: DyckWord_complete.from_area_sequence([])
doctest:...: DeprecationWarning: this method is deprecated. Use DyckWords().from_area_sequence instead.
See http://trac.sagemath.org/14875 for details.
[]
This is deprecated in trac ticket #14875. Use instead CompleteDyckWords.from_non_decreasing_parking_function().
EXAMPLES:
sage: from sage.combinat.dyck_word import DyckWord_complete
sage: DyckWord_complete.from_non_decreasing_parking_function([])
doctest:...: DeprecationWarning: this method is deprecated. Use DyckWords().from_non_decreasing_parking_function instead.
See http://trac.sagemath.org/14875 for details.
[]
Return all parking functions whose supporting Dyck path is self.
EXAMPLES:
sage: DyckWord([1,1,0,0,1,0]).list_parking_functions()
Permutations of the multi-set [1, 1, 3]
sage: DyckWord([1,1,1,0,0,0]).list_parking_functions()
Permutations of the multi-set [1, 1, 1]
sage: DyckWord([1,0,1,0,1,0]).list_parking_functions()
Permutations of the set [1, 2, 3]
Return the major index of self .
The major index of a Dyck word is the sum of the positions of
the valleys of
(when started counting at position 1).
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).major_index()
2
sage: DyckWord([1, 1, 0, 0]).major_index()
0
sage: DyckWord([1, 1, 0, 0, 1, 0]).major_index()
4
sage: DyckWord([1, 0, 1, 1, 0, 0]).major_index()
2
TESTS:
sage: DyckWord([]).major_index()
0
sage: DyckWord([1, 0]).major_index()
0
Return the number of parking functions with self as the supporting Dyck path.
One representation of a parking function is as a pair consisting of a
Dyck path and a permutation such that if
is the area_sequence of the Dyck path
(see to_area_sequence) then the
permutation
satisfies
whenever
. This function counts the number of permutations
which satisfy this condition.
EXAMPLES:
sage: DyckWord(area_sequence=[0,1,2]).number_of_parking_functions()
1
sage: DyckWord(area_sequence=[0,1,1]).number_of_parking_functions()
3
sage: DyckWord(area_sequence=[0,1,0]).number_of_parking_functions()
3
sage: DyckWord(area_sequence=[0,0,0]).number_of_parking_functions()
6
Return the number of tunnels of self of type tunnel_type.
A tunnel is a pair where a is the position of an open
parenthesis and b is the position of the matching close
parenthesis. If
then the tunnel is called centered . If
then the tunnel is called left and if
, then
the tunnel is called right.
INPUT:
EXAMPLES:
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).number_of_tunnels()
0
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).number_of_tunnels('left')
5
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).number_of_tunnels('right')
2
sage: DyckWord([1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0]).number_of_tunnels('all')
7
sage: DyckWord([1, 1, 0, 0]).number_of_tunnels('centered')
2
A pyramid of self is a subsequence of the form
. A pyramid is maximal if it is neither preceded by a
nor followed by a
.
The pyramid weight of a Dyck path is the sum of the lengths of the maximal pyramids and was defined in [DS1992].
EXAMPLES:
sage: DyckWord([1,1,0,1,1,1,0,0,1,0,0,0,1,1,0,0]).pyramid_weight()
6
sage: DyckWord([1,1,1,0,0,0]).pyramid_weight()
3
sage: DyckWord([1,0,1,0,1,0]).pyramid_weight()
3
sage: DyckWord([1,1,0,1,0,0]).pyramid_weight()
2
REFERENCES:
[DS1992] | A. Denise, R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math 137 (1992), 155–176. |
The permutation formed by taking the reading word of the Dyck path
representing self (with and
steps) if the vertical
edges of the Dyck path are labeled from bottom to top with
through
and the diagonals are read from top to bottom starting
with the diagonal furthest from the main diagonal.
EXAMPLES:
sage: DyckWord([1,0,1,0]).reading_permutation()
[2, 1]
sage: DyckWord([1,1,0,0]).reading_permutation()
[2, 1]
sage: DyckWord([1,1,0,1,0,0]).reading_permutation()
[3, 2, 1]
sage: DyckWord([1,1,0,0,1,0]).reading_permutation()
[2, 3, 1]
sage: DyckWord([1,0,1,1,0,0,1,0]).reading_permutation()
[3, 4, 2, 1]
Return the reverse and complement of self.
This operation corresponds to flipping the Dyck path across the
line.
EXAMPLES:
sage: DyckWord([1,1,0,0,1,0]).reverse()
[1, 0, 1, 1, 0, 0]
sage: DyckWord([1,1,1,0,0,0]).reverse()
[1, 1, 1, 0, 0, 0]
sage: len(filter(lambda D: D.reverse() == D, DyckWords(5)))
10
TESTS:
sage: DyckWord([]).reverse()
[]
Return the semilength of self.
The semilength of a complete Dyck word is the number of openers
and the number of closers.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).semilength()
2
TESTS:
sage: DyckWord([]).semilength()
0
Use the bijection by C. Krattenthaler in [Kra2001] to send self
to a -avoiding permutation.
REFERENCES:
[Kra2001] | C. Krattenthaler – Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001), 510–530. |
EXAMPLES:
sage: DyckWord([1,1,0,0]).to_132_avoiding_permutation()
[1, 2]
sage: DyckWord([1,0,1,0]).to_132_avoiding_permutation()
[2, 1]
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).to_132_avoiding_permutation()
[6, 5, 4, 7, 2, 1, 3]
TESTS:
sage: PD = [D.to_132_avoiding_permutation() for D in DyckWords(5)]
sage: all(pi.avoids([1,3,2]) for pi in PD)
True
Convert self to a -avoiding permutation using the bijection by
Bandlow and Killpatrick in [BK2001]. Sends the area to the
inversion number.
REFERENCES:
[BK2001] | J. Bandlow, K. Killpatrick – An area-to_inv bijection between Dyck paths and 312-avoiding permutations, Electronic Journal of Combinatorics, Volume 8, Issue 1 (2001). |
EXAMPLES:
sage: DyckWord([1,1,0,0]).to_312_avoiding_permutation()
[2, 1]
sage: DyckWord([1,0,1,0]).to_312_avoiding_permutation()
[1, 2]
sage: p = DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).to_312_avoiding_permutation(); p
[2, 3, 1, 5, 6, 7, 4]
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).area()
5
sage: p.length()
5
TESTS:
sage: PD = [D.to_312_avoiding_permutation() for D in DyckWords(5)]
sage: all(pi.avoids([3,1,2]) for pi in PD)
True
sage: all(D.area()==D.to_312_avoiding_permutation().length() for D in DyckWords(5))
True
Use the bijection (pp. 60-61 of [Knu1973] or section 3.1 of [CK2008])
to send self to a -avoiding permutation.
It is shown in [EP2004] that it sends the number of centered tunnels to the number of fixed points, the number of right tunnels to the number of exceedences, and the semilength plus the height of the middle point to 2 times the length of the longest increasing subsequence.
REFERENCES:
[EP2004] | S. Elizalde, I. Pak. Bijections for refined restricted permutations*. JCTA 105(2) 2004. |
[CK2008] | A. Claesson, S. Kitaev. Classification of bijections between `321`- and `132`- avoiding permutations. Seminaire Lotharingien de Combinatoire 60 2008. Arxiv 0805.1325. |
[Knu1973] | D. Knuth. The Art of Computer Programming, Vol. III. Addison-Wesley. Reading, MA. 1973. |
EXAMPLES:
sage: DyckWord([1,0,1,0]).to_321_avoiding_permutation()
[2, 1]
sage: DyckWord([1,1,0,0]).to_321_avoiding_permutation()
[1, 2]
sage: D = DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0])
sage: p = D.to_321_avoiding_permutation()
sage: p
[3, 5, 1, 6, 2, 7, 4]
sage: D.number_of_tunnels()
0
sage: p.number_of_fixed_points()
0
sage: D.number_of_tunnels('right')
4
sage: len(p.weak_excedences())-p.number_of_fixed_points()
4
sage: n = D.semilength()
sage: D.heights()[n] + n
8
sage: 2*p.longest_increasing_subsequence_length()
8
TESTS:
sage: PD = [D.to_321_avoiding_permutation() for D in DyckWords(5)]
sage: all(pi.avoids([3,2,1]) for pi in PD)
True
sage: to_perm = lambda x: x.to_321_avoiding_permutation()
sage: all(D.number_of_tunnels() == to_perm(D).number_of_fixed_points()
....: for D in DyckWords(5))
True
sage: all(D.number_of_tunnels('right') == len(to_perm(D).weak_excedences())
....: -to_perm(D).number_of_fixed_points() for D in DyckWords(5))
True
sage: all(D.heights()[5]+5 == 2*to_perm(D).longest_increasing_subsequence_length()
....: for D in DyckWords(5))
True
Return the Catalan code associated to self . The Catalan code is a
sequence of non–negative integers such that if
and
and
and
then
.
The Catalan code of a Dyck word is example (x) in Richard Stanley’s exercises on combinatorial interpretations for Catalan objects. The code in this example is the reverse of the description provided there. See [Sta1999] and [Sta].
EXAMPLES:
sage: DyckWord([]).to_Catalan_code()
[]
sage: DyckWord([1, 0]).to_Catalan_code()
[0]
sage: DyckWord([1, 1, 0, 0]).to_Catalan_code()
[0, 1]
sage: DyckWord([1, 0, 1, 0]).to_Catalan_code()
[0, 0]
sage: all(dw ==
....: DyckWords().from_Catalan_code(dw.to_Catalan_code())
....: for i in range(6) for dw in DyckWords(i))
True
Return self as an alternating sign matrix.
This is an inclusion map from Dyck words of length to certain
alternating sign matrices.
EXAMPLES:
sage: DyckWord([1,1,1,0,1,0,0,0]).to_alternating_sign_matrix()
[ 0 0 1 0]
[ 1 0 -1 1]
[ 0 1 0 0]
[ 0 0 1 0]
sage: DyckWord([1,0,1,0,1,1,0,0]).to_alternating_sign_matrix()
[1 0 0 0]
[0 1 0 0]
[0 0 0 1]
[0 0 1 0]
Bijection to non-decreasing parking functions. See there the method to_dyck_word() for more information.
EXAMPLES:
sage: DyckWord([]).to_non_decreasing_parking_function()
[]
sage: DyckWord([1,0]).to_non_decreasing_parking_function()
[1]
sage: DyckWord([1,1,0,0]).to_non_decreasing_parking_function()
[1, 1]
sage: DyckWord([1,0,1,0]).to_non_decreasing_parking_function()
[1, 2]
sage: DyckWord([1,0,1,1,0,1,0,0,1,0]).to_non_decreasing_parking_function()
[1, 2, 2, 3, 5]
TESTS:
sage: ld=DyckWords(5);
sage: list(ld) == [dw.to_non_decreasing_parking_function().to_dyck_word() for dw in ld]
True
Bijection of Biane from self to a noncrossing partition.
There is an optional parameter bijection that indicates if a different bijection from Dyck words to non-crossing partitions should be used (since there are potentially many).
If the parameter bijection is “Stump” then the bijection used is from [Stu2008], see also the method to_noncrossing_permutation().
Thanks to Mathieu Dutour for describing the bijection. See also from_noncrossing_partition().
EXAMPLES:
sage: DyckWord([]).to_noncrossing_partition()
[]
sage: DyckWord([1, 0]).to_noncrossing_partition()
[[1]]
sage: DyckWord([1, 1, 0, 0]).to_noncrossing_partition()
[[1, 2]]
sage: DyckWord([1, 1, 1, 0, 0, 0]).to_noncrossing_partition()
[[1, 2, 3]]
sage: DyckWord([1, 0, 1, 0, 1, 0]).to_noncrossing_partition()
[[1], [2], [3]]
sage: DyckWord([1, 1, 0, 1, 0, 0]).to_noncrossing_partition()
[[2], [1, 3]]
sage: DyckWord([]).to_noncrossing_partition("Stump")
[]
sage: DyckWord([1, 0]).to_noncrossing_partition("Stump")
[[1]]
sage: DyckWord([1, 1, 0, 0]).to_noncrossing_partition("Stump")
[[1, 2]]
sage: DyckWord([1, 1, 1, 0, 0, 0]).to_noncrossing_partition("Stump")
[[1, 3], [2]]
sage: DyckWord([1, 0, 1, 0, 1, 0]).to_noncrossing_partition("Stump")
[[1], [2], [3]]
sage: DyckWord([1, 1, 0, 1, 0, 0]).to_noncrossing_partition("Stump")
[[1, 2, 3]]
Use the bijection by C. Stump in [Stu2008] to send self to a non-crossing permutation.
A non-crossing permutation when written in cyclic notation has cycles
which are strictly increasing. Sends the area to the inversion number
and self.major_index() to .
Uses the function pealing()
REFERENCES:
[Stu2008] | (1, 2, 3) C. Stump – More bijective Catalan combinatorics on permutations and on colored permutations, Preprint. Arxiv 0808.2822. |
EXAMPLES:
sage: DyckWord([1,1,0,0]).to_noncrossing_permutation()
[2, 1]
sage: DyckWord([1,0,1,0]).to_noncrossing_permutation()
[1, 2]
sage: p = DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).to_noncrossing_permutation(); p
[2, 3, 1, 5, 6, 7, 4]
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).area()
5
sage: p.length()
5
TESTS:
sage: all(D.area()==D.to_noncrossing_permutation().length() for D in DyckWords(5))
True
sage: all(20-D.major_index()==D.to_noncrossing_permutation().major_index()
....: +D.to_noncrossing_permutation().imajor_index() for D in DyckWords(5))
True
Return the ordered tree corresponding to self where the depth of the tree is the maximal height of self.
EXAMPLES:
sage: D = DyckWord([1,1,0,0])
sage: D.to_ordered_tree()
[[[]]]
sage: D = DyckWord([1,0,1,0])
sage: D.to_ordered_tree()
[[], []]
sage: D = DyckWord([1, 0, 1, 1, 0, 0])
sage: D.to_ordered_tree()
[[], [[]]]
sage: D = DyckWord([1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0])
sage: D.to_ordered_tree()
[[], [[], []], [[], [[]]]]
TESTS:
sage: D = DyckWord([1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0])
sage: D == D.to_ordered_tree().to_dyck_word()
True
Convert self to a pair of standard tableaux of the same shape and of length less than or equal to two.
EXAMPLES:
sage: DyckWord([1,0,1,0]).to_pair_of_standard_tableaux()
([[1], [2]], [[1], [2]])
sage: DyckWord([1,1,0,0]).to_pair_of_standard_tableaux()
([[1, 2]], [[1, 2]])
sage: DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).to_pair_of_standard_tableaux()
([[1, 2, 4, 7], [3, 5, 6]], [[1, 2, 4, 6], [3, 5, 7]])
Return the partition associated to self .
This partition is determined by thinking of self as a lattice path
and considering the cells which are above the path but within the
grid and the partition is formed by reading the sequence
of the number of cells in this collection in each row.
OUTPUT:
EXAMPLES:
sage: DyckWord([]).to_partition()
[]
sage: DyckWord([1,0]).to_partition()
[]
sage: DyckWord([1,1,0,0]).to_partition()
[]
sage: DyckWord([1,0,1,0]).to_partition()
[1]
sage: DyckWord([1,0,1,0,1,0]).to_partition()
[2, 1]
sage: DyckWord([1,1,0,0,1,0]).to_partition()
[2]
sage: DyckWord([1,0,1,1,0,0]).to_partition()
[1, 1]
This is simply a method collecting all implemented maps from Dyck words to permutations.
INPUT:
EXAMPLES:
sage: D = DyckWord([1,1,1,0,1,0,0,0])
sage: D.pretty_print()
_____
_| x x
| x x .
| x . .
| . . .
sage: D.to_permutation(map="Bandlow-Killpatrick")
[3, 4, 2, 1]
sage: D.to_permutation(map="Stump")
[4, 2, 3, 1]
sage: D.to_permutation(map="Knuth")
[1, 2, 4, 3]
sage: D.to_permutation(map="Krattenthaler")
[2, 1, 3, 4]
Map self to a triangulation.
Todo
Implement DyckWord_complete.to_triangulation().
TESTS:
sage: DyckWord([1, 1, 0, 0]).to_triangulation()
Traceback (most recent call last):
...
NotImplementedError: TODO
Return the list of ranges of the matching parentheses in the Dyck word self. That is, if (a,b) is in self.tunnels(), then the matching parenthesis to self[a] is self[b-1].
EXAMPLES:
sage: DyckWord([1, 1, 0, 1, 1, 0, 0, 1, 0, 0]).tunnels()
[(0, 10), (1, 3), (3, 7), (4, 6), (7, 9)]
Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation
Dyck words.
A Dyck word is a sequence consisting of 1 s and 0 s,
with the property that for any
with
, the sequence
contains at least as many 1 s as 0 s.
A Dyck word is balanced if the total number of 1 s is equal to the total
number of 0 s. The number of balanced Dyck words of length is given
by the Catalan number
.
EXAMPLES:
This class can be called with three keyword parameters k1, k2 and complete.
If neither k1 nor k2 are specified, then DyckWords returns the combinatorial class of all balanced (=complete) Dyck words, unless the keyword complete is set to False (in which case it returns the class of all Dyck words).
sage: DW = DyckWords(); DW
Complete Dyck words
sage: [] in DW
True
sage: [1, 0, 1, 0] in DW
True
sage: [1, 1, 0] in DW
False
sage: ADW = DyckWords(complete=False); ADW
Dyck words
sage: [] in ADW
True
sage: [1, 0, 1, 0] in ADW
True
sage: [1, 1, 0] in ADW
True
sage: [1, 0, 0] in ADW
False
If just k1 is specified, then it returns the balanced Dyck words with k1 opening parentheses and k1 closing parentheses.
sage: DW2 = DyckWords(2); DW2
Dyck words with 2 opening parentheses and 2 closing parentheses
sage: DW2.first()
[1, 0, 1, 0]
sage: DW2.last()
[1, 1, 0, 0]
sage: DW2.cardinality()
2
sage: DyckWords(100).cardinality() == catalan_number(100)
True
If k2 is specified in addition to k1, then it returns the Dyck words with k1 opening parentheses and k2 closing parentheses.
sage: DW32 = DyckWords(3,2); DW32
Dyck words with 3 opening parentheses and 2 closing parentheses
sage: DW32.list()
[[1, 0, 1, 0, 1],
[1, 0, 1, 1, 0],
[1, 1, 0, 0, 1],
[1, 1, 0, 1, 0],
[1, 1, 1, 0, 0]]
Compute a Dyck word knowing its heights.
We view the Dyck word as a Dyck path from to
in the first quadrant by letting 1‘s represent
steps in the direction
and 0‘s represent steps in
the direction
.
The heights() is the sequence of the -coordinates of
the
lattice points along this path.
EXAMPLES:
sage: from sage.combinat.dyck_word import DyckWord
sage: D = DyckWords(complete=False)
sage: D.from_heights((0,))
[]
sage: D.from_heights((0, 1, 0))
[1, 0]
sage: D.from_heights((0, 1, 2, 1, 0))
[1, 1, 0, 0]
This also works for incomplete Dyck words:
sage: D.from_heights((0, 1, 2, 1, 2, 1))
[1, 1, 0, 1, 0]
sage: D.from_heights((0, 1, 2, 1))
[1, 1, 0]
See also
heights(), min_from_heights()
TESTS:
sage: all(dw == D.from_heights(dw.heights())
....: for i in range(7) for dw in DyckWords(i))
True
sage: D.from_heights((1, 2, 1))
Traceback (most recent call last):
...
ValueError: heights must start with 0: (1, 2, 1)
sage: D.from_heights((0, 1, 4, 1))
Traceback (most recent call last):
...
ValueError: consecutive heights must differ by exactly 1: (0, 1, 4, 1)
sage: D.from_heights(())
Traceback (most recent call last):
...
ValueError: heights must start with 0: ()
Set and display the global options for Dyck words. If no parameters are set, then the function returns a copy of the options dictionary.
The options to Dyck words can be accessed as the method DyckWords.global_options of DyckWords and related parent classes.
OPTIONS:
EXAMPLES:
sage: D = DyckWord([1, 1, 0, 1, 0, 0])
sage: D
[1, 1, 0, 1, 0, 0]
sage: DyckWords.global_options(display="lattice")
sage: D
___
_| x
| x .
| . .
sage: DyckWords.global_options(diagram_style="line")
sage: D
/\/\
/ \
sage: DyckWords.global_options.reset()
See GlobalOptions for more features of these options.
Compute the smallest Dyck word which achieves or surpasses a given sequence of heights.
INPUT:
OUTPUT:
See also
EXAMPLES:
sage: D = DyckWords(complete=False)
sage: D.min_from_heights((0,))
[]
sage: D.min_from_heights((0, 1, 0))
[1, 0]
sage: D.min_from_heights((0, 0, 2, 0, 0))
[1, 1, 0, 0]
sage: D.min_from_heights((0, 0, 2, 0, 2, 0))
[1, 1, 0, 1, 0]
sage: D.min_from_heights((0, 0, 1, 0, 1, 0))
[1, 1, 0, 1, 0]
TESTS:
sage: D.min_from_heights(())
Traceback (most recent call last):
...
ValueError: heights must start with 0: ()
Bases: sage.combinat.dyck_word.DyckWords
All Dyck words.
Bases: sage.combinat.dyck_word.DyckWords
Dyck words with openers and
closers.
Return the number of Dyck words with openers and
closers.
This number is
if , and
if
(these numbers are the
same if
).
EXAMPLES:
sage: DyckWords(3, 2).cardinality()
5
sage: all( all( DyckWords(p, q).cardinality()
....: == len(DyckWords(p, q).list()) for q in range(p + 1) )
....: for p in range(7) )
True
This is deprecated in trac ticket #14875. Instead use CompleteDyckWords.from_noncrossing_partition().
TESTS:
sage: sage.combinat.dyck_word.from_noncrossing_partition([[1,2]])
doctest:...: DeprecationWarning: this method is deprecated. Use DyckWords().from_noncrossing_partition instead.
See http://trac.sagemath.org/14875 for details.
[1, 1, 0, 0]
TESTS:
sage: sage.combinat.dyck_word.from_ordered_tree(1)
Traceback (most recent call last):
...
NotImplementedError: TODO
Test if obj is a Dyck word with exactly k1 open symbols and exactly k2 close symbols.
If k1 is not specified, then the number of open symbols can be arbitrary. If k1 is specified but k2 is not, then k2 is set to be k1.
EXAMPLES:
sage: from sage.combinat.dyck_word import is_a
sage: is_a([1,1,0,0])
True
sage: is_a([1,0,1,0])
True
sage: is_a([1,1,0,0], 2)
True
sage: is_a([1,1,0,0], 3)
False
sage: is_a([1,1,0,0], 3, 2)
False
sage: is_a([1,1,0])
True
sage: is_a([0,1,0])
False
sage: is_a([1,0,0])
False
sage: is_a([1,1,0],2,1)
True
sage: is_a([1,1,0],2)
False
sage: is_a([1,1,0],1,1)
False
Test if a sequence of integers satisfies
and
for
.
EXAMPLES:
sage: from sage.combinat.dyck_word import is_area_sequence
sage: is_area_sequence([0,2,0])
False
sage: is_area_sequence([1,2,3])
False
sage: is_area_sequence([0,1,0])
True
sage: is_area_sequence([0,1,2])
True
sage: is_area_sequence([])
True
A helper function for computing the bijection from a Dyck word to a
-avoiding permutation using the bijection “Stump”. For details
see [Stu2008].
See also
EXAMPLES:
sage: from sage.combinat.dyck_word import pealing
sage: pealing(DyckWord([1,1,0,0]))
[1, 0, 1, 0]
sage: pealing(DyckWord([1,0,1,0]))
[1, 0, 1, 0]
sage: pealing(DyckWord([1, 1, 0, 0, 1, 1, 1, 0, 0, 0]))
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
sage: pealing(DyckWord([1,1,0,0]),return_touches=True)
([1, 0, 1, 0], [[1, 2]])
sage: pealing(DyckWord([1,0,1,0]),return_touches=True)
([1, 0, 1, 0], [])
sage: pealing(DyckWord([1, 1, 0, 0, 1, 1, 1, 0, 0, 0]),return_touches=True)
([1, 0, 1, 0, 1, 0, 1, 0, 1, 0], [[1, 2], [3, 5]])
A map sending '(' to open_symbol and ')' to close_symbol, and raising an error on any input other than '(' and ')'. The values of the constants open_symbol and close_symbol are subject to change.
This is the inverse map of replace_symbols().
INPUT:
OUTPUT:
See also
EXAMPLES:
sage: from sage.combinat.dyck_word import replace_parens
sage: replace_parens('(')
1
sage: replace_parens(')')
0
sage: replace_parens(1)
Traceback (most recent call last):
...
ValueError
A map sending open_symbol to '(' and close_symbol to ')', and raising an error on any input other than open_symbol and close_symbol. The values of the constants open_symbol and close_symbol are subject to change.
This is the inverse map of replace_parens().
INPUT:
OUTPUT:
See also
EXAMPLES:
sage: from sage.combinat.dyck_word import replace_symbols
sage: replace_symbols(1)
'('
sage: replace_symbols(0)
')'
sage: replace_symbols(3)
Traceback (most recent call last):
...
ValueError