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.
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, andDWB(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 inDyckWords
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
andcomplete
.If neither
k1
nork2
are specified, thenDyckWords
returns the combinatorial class of all balanced (=complete) Dyck words, unless the keywordcomplete
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 withk1
opening parentheses andk1
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 tok1
, then it returns the Dyck words withk1
opening parentheses andk2
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 exactlyk1
open symbols and exactlyk2
close symbols.If
k1
is not specified, then the number of open symbols can be arbitrary. Ifk1
is specified butk2
is not, thenk2
is set to bek1
.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
'('
toopen_symbol
and')'
toclose_symbol
, and raising an error on any input other than'('
and')'
. The values of the constantsopen_symbol
andclose_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, replacex
with the constantopen_symbol
. - If
x
is a closing parenthesis, replacex
with the constantclose_symbol
. - Raise a
ValueError
ifx
is neither an opening nor a closing parenthesis.
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
-
sage.combinat.dyck_word.
replace_symbols
(x)¶ A map sending
open_symbol
to'('
andclose_symbol
to')'
, and raising an error on any input other thanopen_symbol
andclose_symbol
. The values of the constantsopen_symbol
andclose_symbol
are subject to change.This is the inverse map of
replace_parens()
.INPUT:
x
– eitheropen_symbol
orclose_symbol
.
OUTPUT:
- If
x
isopen_symbol
, replacex
with'('
. - If
x
isclose_symbol
, replacex
with')'
. - If
x
is neitheropen_symbol
norclose_symbol
, aValueError
is raised.
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