Dyck Words

A class of an object enumerated by the Catalan numbers, see [Sta1999], [Sta] for details.

AUTHORS:

  • Mike Hansen

  • Dan Drake (2008–05-30): DyckWordBacktracker support

  • Florent Hivert (2009–02-01): Bijections with NonDecreasingParkingFunctions

  • Christian Stump (2011–12): added combinatorial maps and statistics

  • Mike Zabrocki (2012–10): added pretty print, characteristic function, more functions

    (2013–01): added inverse of area/dinv, bounce/area map

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 q,t – Catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials, James Haglund, University of Pennsylvania, Philadelphia – AMS, 2008, 167 pp.
sage.combinat.dyck_word.DyckWord(dw=None, noncrossing_partition=None, area_sequence=None, heights_sequence=None, catalan_code=None)

Returns a complete or incomplete Dyck word.

A Dyck word is a sequence of open and close symbols, such that every close symbol has a corresponding open symbol preceeding it.

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 \mathbb{Z}^2 grid, starting at the origin (0,0), and with steps in the N = (0,1) and E = (1,0), directions such that it does not pass below the x=y diagonal. The diagonal is referred to as the “main diagonal” in the documentation. Equivalently, the path may be represented with steps in the NE = (1,1) and the SE = (1,-1) direction such that it does not pass below the horizontal axis.

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(noncrossing_partition=[[1],[2]])
[1, 0, 1, 0]
sage: DyckWord(noncrossing_partition=[[1,2]])
[1, 1, 0, 0]
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(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: print DyckWord([1,0,1,1,0,0]).to_path_string()
   /\
/\/  \
sage: DyckWord([1,0,1,1,0,0]).pretty_print()
   ___
  | x
 _|  .
|  . .
class sage.combinat.dyck_word.DyckWordBacktracker(k1, k2)

Bases: sage.combinat.backtrack.GenericBacktracker

DyckWordBacktracker: this class is an iterator for all Dyck words with n opening parentheses and n - endht 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:

  • Dan Drake (2008-05-30)
class sage.combinat.dyck_word.DyckWord_class(l, latex_options={})

Bases: sage.combinat.combinat.CombinatorialObject

A class for representing a Dyck word. A Dyck word of length n is a list with n entries 1 and and n entries 0 such that the first k entries always has at least as many 1s as 0s. Alternatively, the alphabet 1 and 0 can be replaced by other characters.

A Dyck word is a representation of a Dyck path which is a lattice path in an n \times n rectangle from (0,0) to (n,n) using only North = (0,1) and East = (1,0) steps such that the path touches, but does not cross the x=y line. A North step is represented by a 1 in the list and an East step is represented by a 0.

associated_parenthesis(pos)

Report the position for the parenthesis that matches the one at position pos .

INPUT:

  • pos – the index of the parenthesis in the list.

OUTPUT:

  • Integer representing the index of the matching parenthesis. If no parenthesis matches, return None.

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)
classmethod from_heights(heights)

Compute a dyck word knowing its heights.

We view the Dyck word as a Dyck path from (0,0) to (2n,0) in the first quadrant by letting 1‘s represent steps in the direction (1,1) and 0‘s represent steps in the direction (1,-1).

The heights() is the sequence of y-coordinate reached.

EXAMPLES:

sage: from sage.combinat.dyck_word import DyckWord_class
sage: DyckWord_class.from_heights((0,))
[]
sage: DyckWord_class.from_heights((0, 1, 0))
[1, 0]
sage: DyckWord_class.from_heights((0, 1, 2, 1, 0))
[1, 1, 0, 0]
sage: DyckWord_class.from_heights((0, 1, 2, 1, 2, 1))
[1, 1, 0, 1, 0]

This also works for prefix of Dyck words:

sage: DyckWord_class.from_heights((0, 1, 2, 1))
[1, 1, 0]

TESTS:

sage: all(dw == DyckWord_class.from_heights(dw.heights())
...       for i in range(7) for dw in DyckWords(i))
True

sage: DyckWord_class.from_heights((1, 2, 1))
Traceback (most recent call last):
...
ValueError: heights must start with 0: (1, 2, 1)
sage: DyckWord_class.from_heights((0, 1, 4, 1))
Traceback (most recent call last):
...
ValueError: consecutive heights must differ by exactly 1: (0, 1, 4, 1)
sage: DyckWord_class.from_heights(())
Traceback (most recent call last):
...
ValueError: heights must start with 0: ()
height()

Returns the height of the Dyck word.

We view the Dyck word as a Dyck path from (0,0) to (2n,0) in the first quadrant by letting 1‘s represent steps in the direction (1,1) and 0‘s represent steps in the direction (1,-1).

The height is the maximum y-coordinate reached.

See also

heights()

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
heights()

Returns the heights of the Dyck word.

We view the Dyck word as a Dyck path from (0,0) to (2n,0) in the first quadrant by letting 1‘s represent steps in the direction (1,1) and 0‘s represent steps in the direction (1,-1).

The heights is the sequence of y-coordinate reached.

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)
is_complete()

Returns True is self is complete. This is if self 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
latex_options()

Returns the latex options for use in the _latex_ function as a dictionary. The default values are set in the __init__ function.

  • tikz_scale – (default:1) scale for use with the tikz package.
  • diagonal – (default:False) boolean value to draw the diagonal or not.
  • line width – (default:2*``tikz_scale``) value representing the line width.
  • color – (default:black) the line color.
  • bounce path – (default:False) boolean value to indicate if the bounce path should be drawn.
  • peaks – (default:False) boolean value to indicate if the peaks should be displayed.
  • valleys – (default:False) boolean value to indicate if the valleys should be displayed.

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}
length()

Returns 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
classmethod min_from_heights(heights)

Compute the smallest dyck word which lies some heights.

EXAMPLES:

sage: from sage.combinat.dyck_word import DyckWord_class
sage: DyckWord_class.min_from_heights((0,))
[]
sage: DyckWord_class.min_from_heights((0, 1, 0))
[1, 0]
sage: DyckWord_class.min_from_heights((0, 0, 2, 0, 0))
[1, 1, 0, 0]
sage: DyckWord_class.min_from_heights((0, 0, 2, 0, 2, 0))
[1, 1, 0, 1, 0]
sage: DyckWord_class.min_from_heights((0, 0, 1, 0, 1, 0))
[1, 1, 0, 1, 0]

TESTS:

sage: DyckWord_class.min_from_heights(())
Traceback (most recent call last):
...
ValueError: heights must start with 0: ()
number_of_close_symbols()

Returns 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
number_of_double_rises()

returns a the number of positions in the Dyck word where there are two consecutive 1s.

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
number_of_initial_rises()

Return the length of the initial run of self

OUPUT:

  • a non–negative integer indicating the length of the initial rise

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
number_of_open_symbols()

Returns 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
number_of_peaks()

The number of peaks of the Dyck path associated to self .

See also

peaks()

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
number_of_touch_points()

Returns the number of touches of self at the main diagonal.

OUTPUT:

  • a non–negative integer

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
number_of_valleys()

Returns 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
peaks()

Returns a list of the positions of the peaks of a Dyck word. A peak is 1 followed by a 0. 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]
position_of_first_return()

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
positions_of_double_rises()

returns a list of positions in the Dyck word where there are two consecutive 1s.

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()
[]
pretty_print(type='N-E', labelling=None, underpath=True)

Display a DyckWord as a lattice path in the \mathbb{Z}^2 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:

  • type – can either be
    • “N-E” to show self as a path of north and east steps, or
    • “NE-SE” to show self as a path of north-east and south-east steps.
  • labelling – (if type is “N-E”) a list of labels assigned to the up steps in self.

  • underpath – (if type is “N-E”, default:True)
    • if True, the labelling is shown under the path
    • otherwise, it is shown to the right of the path.

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()
.
return_to_zero(*args, **kwds)

Deprecated: Use returns_to_zero() instead. See trac ticket #13550 for details.

returns_to_zero()

Return a list of positions where the Dyck word has height 0.

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]
rise_composition()

The sequences of lengths of runs of 1s in the Dyck word. 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]
set_latex_options(D)

Sets the latex options for use in the _latex_ function. The default values are set in the __init__ function.

  • tikz_scale – (default:1) scale for use with the tikz package.
  • diagonal – (default:False) boolean value to draw the diagonal or not.
  • line width – (default:2*``tikz_scale``) value representing the line width.
  • color – (default:black) the line color.
  • bounce path – (default:False) boolean value to indicate if the bounce path should be drawn.
  • peaks – (default:False) boolean value to indicate if the peaks should be displayed.
  • valleys – (default:False) boolean value to indicate if the valleys should be displayed.

INPUT:

  • D – a dictionary with a list of latex parameters to change.

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"})
size(*args, **kwds)

Deprecated: Use number_of_open_symbols() instead. See trac ticket #13550 for details.

to_area_sequence()

Return the sequence of numbers representing of full cells below the Dyck path but above the diagonal in the successive rows.

A area sequence is a list of integer l such that l_0 = 0 and 0 \leq l_{i+1} \leq l_i + 1 for i > 0. This sequence is equal to the number of full cells below the path but above the diagonal in the corresponding Dyck path.

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: from sage.combinat.dyck_word import DyckWord_complete
sage: all(dw ==
...       DyckWord_complete.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]
to_path_string()

A path representation of the Dyck word consisting of steps / and \ .

EXAMPLES:

sage: DyckWord([1, 0, 1, 0]).to_path_string()
'/\\/\\'
sage: DyckWord([1, 1, 0, 0]).to_path_string()
' /\\ \n/  \\'
sage: DyckWord([1,1,0,1,1,0,0,1,0,1,0,0]).to_path_string()
'    /\\      \n /\\/  \\/\\/\\ \n/          \\'
to_standard_tableau(*args, **kwds)

Returns a standard tableau of shape (a,b) where a is the number of open symbols and b 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]]
touch_composition()

Returns a composition which indicates the positions where the Dyck path returns to the diagonal.

OUTPUT:

  • a composition of length equal to the length of the Dyck word.

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

Returns the positions greater than 0 and less than or equal to the length of self of the points where the Dyck path touches the main diagonal.

OUTPUT:

  • a list of integers indicating where the path touches the diagonal

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]
valleys()

Returns a list of the positions of the valleys of a Dyck word. A valley is 0 followed by a 1.

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]
class sage.combinat.dyck_word.DyckWord_complete(l, latex_options={})

Bases: sage.combinat.dyck_word.DyckWord_class

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.

a_statistic(*args, **kwds)

Deprecated: Use area() instead. See trac ticket #13550 for details.

area()

Returns the area for the Dyck word corresponding to the area of the Dyck path.

One can view a balanced Dyck word as a lattice path from (0,0) to (n,n) in the first quadrant by letting ‘1’s represent steps in the direction (1,0) and ‘0’s represent steps in the direction (0,1). The resulting path will remain weakly above the diagonal y = x.

The area statistic is the number of complete squares in the integer lattice which are below the path and above the line y = x. The ‘half-squares’ directly above the line y=x 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
area_dinv_to_bounce_area_map()

Returns the image of the Dyck word under the map which sends a Dyck word with area equal to r and dinv equal to s to a Dyck word with bounce equal to r and area equal to s .

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 \zeta. 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]
b_statistic(*args, **kwds)

Deprecated: Use bounce() instead. See trac ticket #13550 for details.

bounce()

Returns the bounce statistic of self due to J. Haglund, see [Hag2008].

One can view a balanced Dyck word as a lattice path from (0,0) to (n,n) in the first quadrant by letting ‘1’s represent steps in the direction (0,1) and ‘0’s represent steps in the direction (1,0). The resulting path will remain weakly above the diagonal y = x.

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 (n, n), which “bounces” down whenever it encounters a vertical step and “bounces” left when it encounters the line y = x.

The bouncing ball will strike the diagonal at places

(0, 0), (j_1, j_1), (j_2, j_2), \dots , (j_r-1, j_r-1), (j_r, j_r)
=
(n, n).

We define the bounce to be the sum \sum_{i=1}^{r-1} j_i.

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
bounce_area_to_area_dinv_map(D)

Returns the image of the Dyck word under the map which sends a Dyck word with bounce equal to r and area equal to s to a Dyck word with area equal to r and dinv equal to s .

This implementation uses a recursive method by saying that the last entry in the area sequence of D 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 \zeta^{-1}. 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]
bounce_path()

Returns the bounce path of the Dyck path formed by starting at (n,n) 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 (0,0) point is reached. The path followed by this walk is the bounce path.

See also

bounce()

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]
characteristic_symmetric_function(q=None, R=Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field)

The characteristic function of the Dyck path is the sum over all permutation fillings of the Dyck path q^{dinv(D,F)} Q_{ides(read(D,F))} where ides(read(D,F)) is the descent composition of the inverse of the reading word of the filling.

INPUT:

  • q – (default: q = R('q')) a parameter for the generating function power.
  • R – (default : R = QQ['q','t'].fraction_field()) the base ring to do the calculations over.

OUTPUT:

  • an element of the symmetric functions over the ring R.

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]
decomposition_reverse()

An involution on Dyck words with a recursive definition. If self decomposes as 1, D1 , 0, D2 where D1 and D2 are complete Dyck words then the decomposition reverse is 1, \phi( D2 ), 0, \phi( D1 ).

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]
dinv(labeling=None)

Returns 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:

  • self – a Dyck word.
  • labeling – an optional argument to be viewed as the labelings of the vertical edges of the Dyck path.

OUTPUT:

  • an integer – representing the dinv statistic of the Dyck path or the labelled Dyck path.

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
first_return_decomposition()

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])
classmethod from_Catalan_code(code)

Return the Dyck words associated to the given Catalan code

The Catalan code is a sequence of non–negative integers a_i such that if i<j and a_i > 0 and a_j>0 and a_{i+1} = a_{i+1} = \cdots = a_{j-1} = 0 then a_i - a_j < j-i.

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: from sage.combinat.dyck_word import DyckWord_complete
sage: DyckWord_complete.from_Catalan_code([])
[]
sage: DyckWord_complete.from_Catalan_code([0])
[1, 0]
sage: DyckWord_complete.from_Catalan_code([0, 1])
[1, 1, 0, 0]
sage: DyckWord_complete.from_Catalan_code([0, 0])
[1, 0, 1, 0]
classmethod from_area_sequence(code)

Return the Dyck words associated to the given area sequence.

The area sequence is a list of integers l such that l_0 = 0 and 0 \leq l_{i+1} \leq l_i + 1 for i > 0. This sequence is equal to the number of full cells below the path but above the diagonal in the corresponding Dyck path.

See also

area()

INPUT:

  • code – a list of integers satisfying 0 <= code[i+1] <= code[i]+1.

EXAMPLES:

sage: from sage.combinat.dyck_word import DyckWord_complete
sage: DyckWord_complete.from_area_sequence([])
[]
sage: DyckWord_complete.from_area_sequence([0])
[1, 0]
sage: DyckWord_complete.from_area_sequence([0, 1])
[1, 1, 0, 0]
sage: DyckWord_complete.from_area_sequence([0, 0])
[1, 0, 1, 0]
classmethod from_non_decreasing_parking_function(pf)

Bijection from non-decreasing parking functions. See there the method to_dyck_word() for more information.

EXAMPLES:

sage: from sage.combinat.dyck_word import DyckWord_complete
sage: DyckWord_complete.from_non_decreasing_parking_function([])
[]
sage: DyckWord_complete.from_non_decreasing_parking_function([1])
[1, 0]
sage: DyckWord_complete.from_non_decreasing_parking_function([1,1])
[1, 1, 0, 0]
sage: DyckWord_complete.from_non_decreasing_parking_function([1,2])
[1, 0, 1, 0]
sage: DyckWord_complete.from_non_decreasing_parking_function([1,1,1])
[1, 1, 1, 0, 0, 0]
sage: DyckWord_complete.from_non_decreasing_parking_function([1,2,3])
[1, 0, 1, 0, 1, 0]
sage: DyckWord_complete.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: DyckWord_complete.from_non_decreasing_parking_function(NonDecreasingParkingFunction([]))
[]
sage: DyckWord_complete.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]
list_parking_functions()

Returns 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]
major_index()

Returns the major index of self . This is the sum of the positions of the valleys of self (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
number_of_parking_functions()

Returns 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 [a_0, a_1, \ldots, a_{n-1}] is the area_sequence (see to_area_sequence) then the permutation \pi such that if a_{i} < a_{i+1} then \pi_i < \pi_{i+1}. This function counts the number of permutations \pi 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
number_of_tunnels(tunnel_type='centered')

A tunnel is a pair (a,b) where a is the position of an open parenthesis and b is the position of the matching close parenthesis. If a+b==n then the tunnel is called centered . If a+b<n then the tunnel is called left and if a+b>n, then the tunnel is called right .

INPUT:

  • self – a Dyck word.
  • tunnel_type – (default: 'centered') an optional parameter specifying 'left', 'right', 'centered', 'all'.

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
pyramid_weight()

A pyramid of the Dyck word is a subsequence of the form 1^h 0^h, a pyramid is maximal if it is not preceeded my a 1 and followed by a 0. The pyramid weight is the sums 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.
reading_permutation()

The permutation formed by taking the reading word of the Dyck path if the vertical edges of the Dyck path are labeled from bottom to top with 1 through n 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]
reverse()

Returns the reverse and complement of the Dyck word self . This operation corresponds to flipping the Dyck path across the y=-x 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: DyckWords(5).filter(lambda D: D.reverse()==D).cardinality()
10

TESTS:

sage: DyckWord([]).reverse()
[]
semilength()

Returns the semilength of self. This is the number of openers and the number of closers of a complete Dyck word.

EXAMPLES:

sage: DyckWord([1, 0, 1, 0]).semilength()
2

TESTS:

sage: DyckWord([]).semilength()
0
to_132_avoiding_permutation()

Uses the bijection by C. Krattenthaler in [Kra2001] to 132-avoiding permutations.

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
to_312_avoiding_permutation()

Converts the Dyck word to a 312-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
to_321_avoiding_permutation()

Uses the bijection [Knu1973] to 321-avoiding permutations. 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.
[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
to_Catalan_code()

Return the Catalan code associated to self . The Catalan code is a sequence of non–negative integers a_i such that if i<j and a_i > 0 and a_j>0 and a_{i+1} =a_{i+1} = \cdots = a_{j-1} = 0 then a_i - a_j < j-i.

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: from sage.combinat.dyck_word import DyckWord_complete
sage: all(dw ==
...       DyckWord_complete.from_Catalan_code(dw.to_Catalan_code())
...       for i in range(6) for dw in DyckWords(i))
True
to_non_decreasing_parking_function()

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
to_noncrossing_partition(bijection=None)

Bijection of Biane from Dyck words to noncrossing partitions. Thanks to Mathieu Dutour for describing the bijection. See also from_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 a paper by C. Stump, see also the method to_noncrossing_permutation().

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]]
to_noncrossing_permutation()

Uses the bijection by C. Stump in [Stu2008] to non-crossing permutations. 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() is sent to n(n-1) - maj(\sigma) - maj(\sigma^{-1}). Uses the function pealing()

REFERENCES:

[Stu2008](1, 2) 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
to_ordered_tree()

TESTS:

sage: DyckWord([1, 1, 0, 0]).to_ordered_tree()
Traceback (most recent call last):
...
NotImplementedError: TODO
to_pair_of_standard_tableaux()

Converts a Dyck word 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]])
to_partition()

Returns 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 n \times n grid and the partition is formed by reading the sequence of the number of cells in this collection in each row.

OUTPUT:

  • a partition representing the rows of cells in the square lattice and above the path

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]
to_permutation(map)

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]
to_triangulation()

This method is not yet implemented.

TESTS:

sage: DyckWord([1, 1, 0, 0]).to_triangulation()
Traceback (most recent call last):
...
NotImplementedError: TODO
tunnels()

Returns the list of ranges of the matching parentheses in the Dyck word. 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)]
sage.combinat.dyck_word.DyckWords(k1=None, k2=None)

Returns the combinatorial class of Dyck words. A Dyck word is a sequence (w_1, ..., w_n) consisting of 1 s and 0 s, with the property that for any i with 1 \le i \le n, the sequence (w_1,...,w_i) contains at least as many 1 s as 0 .

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 2k is given by the Catalan number C_k.

EXAMPLES: If neither k1 nor k2 are specified, then DyckWords returns the combinatorial class of all balanced Dyck words.

sage: DW = DyckWords(); DW
Dyck words
sage: [] in DW
True
sage: [1, 0, 1, 0] in DW
True
sage: [1, 1, 0] in DW
False

If just k1 is specified, then it returns the combinatorial class of 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 combinatorial class of 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]]
class sage.combinat.dyck_word.DyckWords_all

Bases: sage.combinat.combinat.InfiniteAbstractCombinatorialClass

TESTS:

sage: DW = DyckWords()
sage: DW == loads(dumps(DW))
True
class height_poset

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

The poset of complete Dyck word compared componentwise by heights. This is, D is smaller than or equal to D' if it is weakly below D'.

le(dw1, dw2)

Compare two Dyck words and return True if all of the heights of dw1 are less than or equal to the heights of dw2 .

See also

heights

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]
class sage.combinat.dyck_word.DyckWords_size(k1, k2=None)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: DW4 = DyckWords(4)
sage: DW4 == loads(dumps(DW4))
True
sage: DW42 = DyckWords(4,2)
sage: DW42 == loads(dumps(DW42))
True
cardinality()

Returns the number of complete Dyck words of semilength n, i.e. the n-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
list()

Returns a list of all the Dyck words with k1 opening and k2 closing parentheses.

EXAMPLES:

sage: DyckWords(0).list()
[[]]
sage: DyckWords(1).list()
[[1, 0]]
sage: DyckWords(2).list()
[[1, 0, 1, 0], [1, 1, 0, 0]]
sage.combinat.dyck_word.from_noncrossing_partition(ncp)

Converts a noncrossing partition 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
sage.combinat.dyck_word.from_ordered_tree(tree)

TESTS:

sage: sage.combinat.dyck_word.from_ordered_tree(1)
Traceback (most recent call last):
...
NotImplementedError: TODO
sage.combinat.dyck_word.is_a(obj, k1=None, k2=None)

If k1 is specified, then the object must have exactly k1 open symbols. If k2 is also specified, then obj must have exactly k2 close symbols.

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.combinat.dyck_word.is_a_prefix(obj, k1=None, k2=None)

If k1 is specified, then the object must have exactly k1 open symbols. If k2 is also specified, then obj must have exactly k2 close symbols.

EXAMPLES:

sage: from sage.combinat.dyck_word import is_a_prefix
sage: is_a_prefix([1,1,0])
True
sage: is_a_prefix([0,1,0])
False
sage: is_a_prefix([1,1,0],2,1)
True
sage: is_a_prefix([1,1,0],1,1)
False
sage.combinat.dyck_word.is_area_sequence(seq)

Tests if a sequence l of integers satisfies l_0 = 0 and 0 \leq l_{i+1} \leq l_i + 1 for i > 0.

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
sage.combinat.dyck_word.pealing(D, return_touches=False)

A helper function for computing the bijection from a Dyck word to a 231-avoiding permutations using the bijection “Stump”. For details see [Stu2008].

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]])
sage.combinat.dyck_word.replace_parens(x)

A map from '(' to open_symbol and ')' to close_symbol and otherwise an error is raised. The values of the constants open_symbol and close_symbol are subject to change. This is the inverse map of replace_symbols().

INPUT:

  • x – either an opening or closing parenthesis.

OUTPUT:

  • If x is an opening parenthesis, replace x with the constant open_symbol.
  • If x is a closing parenthesis, replace x with the constant close_symbol.
  • Raises a ValueError if x is neither an opening nor closing parenthesis.

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
sage.combinat.dyck_word.replace_symbols(x)

A map from open_symbol to '(' and close_symbol to ')' and otherwise an error is raised. The values of the constants open_symbol and close_symbol are subject to change. This is the inverse map of replace_parens().

INPUT:

  • x – either open_symbol or close_symbol.

OUTPUT:

  • If x is open_symbol, replace x with '('.
  • If x is close_symbol, replace x with ')'.
  • If x is neither open_symbol nor close_symbol, a ValueError` is raised.

See also

replace_parens()

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

Previous topic

Dancing links C++ wrapper

Next topic

The family of generalized Tamari lattices

This Page