Dyck Words

A class of an object enumerated by the Catalan numbers, see [Sta-EC2], [StaCat98] 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
  • Jean–Baptiste Priez, Travis Scrimshaw (2013-05-17): Added ASCII art
  • Travis Scrimshaw (2013-07-09): Removed CombinatorialClass and added global options.

REFERENCES:

[Sta-EC2]Richard P. Stanley. Enumerative Combinatorics, Volume 2. Cambridge University Press, 2001.
[StaCat98]Richard Stanley. Exercises on Catalan and Related Numbers excerpted from Enumerative Combinatorics, vol. 2 (CUP 1999), version of 23 June 1998. http://www-math.mit.edu/~rstan/ec/catalan.pdf
[Hag2008]James Haglund. The \(q,t\)Catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials. University of Pennsylvania, Philadelphia – AMS, 2008, 167 pp.
sage.combinat.dyck_word.CompleteDyckWords

Abstract base class for all complete Dyck words.

sage.combinat.dyck_word.CompleteDyckWords_all

All complete Dyck words.

sage.combinat.dyck_word.CompleteDyckWords_size

All complete Dyck words of a given size.

sage.combinat.dyck_word.DyckWord

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 \(n\) is a list with \(k\) entries 1 and \(n - k\) entries 0 such that the first \(i\) 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 \(\ZZ^2\) grid, starting at the origin \((0,0)\), and with steps in the North \(N = (0,1)\) and east \(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. 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 \(NE = (1,1)\) and the \(SE = (1,-1)\) direction such that it does not pass below the horizontal axis.

../../_images/dyck_word-1.png

A path representing a Dyck word (either using \(N\) and \(E\) steps, or using \(NE\) and \(SE\) steps) is called a Dyck path.

EXAMPLES:

sage: dw = DyckWord([1, 0, 1, 0]); dw
[1, 0, 1, 0]
sage: print(dw)
()()
sage: 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
 _|  .
|  . .
class sage.combinat.dyck_word.DyckWordBacktracker(k1, k2)

Bases: sage.combinat.backtrack.GenericBacktracker

This class is an iterator for all Dyck words with \(n\) opening parentheses and \(n - k\) 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)
sage.combinat.dyck_word.DyckWord_complete

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.

sage.combinat.dyck_word.DyckWords

Dyck words.

A Dyck word is a sequence \((w_1, \ldots, w_n)\) consisting of 1 s and 0 s, with the property that for any \(i\) with \(1 \leq i \leq n\), the sequence \((w_1, \ldots, w_i)\) 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 \(2k\) is given by the Catalan number \(C_k\).

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]]
sage.combinat.dyck_word.DyckWords_all

All Dyck words.

sage.combinat.dyck_word.DyckWords_size

Dyck words with \(k_1\) openers and \(k_2\) closers.

sage.combinat.dyck_word.is_a(obj, k1=None, k2=None)

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
sage.combinat.dyck_word.is_area_sequence(seq)

Test 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 permutation using the bijection “Stump”. For details see [Stu2008].

See also

to_noncrossing_partition()

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

  • 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.
  • Raise a ValueError if x is neither an opening nor a 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 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:

  • 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