Module: sage.combinat.dyck_word
Dyck Words
Author Log:
Module-level Functions
[dw=None], [noncrossing_partition=None]) |
Returns a Dyck word object
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(noncrossing_partition=[[1],[2]]) [1, 0, 1, 0]
[k1=None], [k2=None]) |
Returns the combinatorial class of 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
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
.
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.count() 2 sage: DyckWords(100).count() == 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]]
ncp) |
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
tree) |
TESTS:
sage: sage.combinat.dyck_word.from_ordered_tree(1) Traceback (most recent call last): ... NotImplementedError: TODO
obj, [k1=None], [k2=None]) |
If k1 is specificied, then the object must have exactly k1 open symbols. If k2 is also specified, then obj must have exactly k2 close symbols.
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
obj, [k1=None], [k2=None]) |
If k1 is specificied, then the object must have exactly k1 open symbols. If k2 is also specified, then obj must have exactly k2 close symbols.
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
x) |
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
x) |
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
Class: DyckWord_class
Functions: a_statistic,
associated_parenthesis,
b_statistic,
height,
peaks,
size,
to_noncrossing_partition,
to_ordered_tree,
to_tableau,
to_triangulation
self) |
Returns the a-statistic for the Dyck word.
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 a-statistic, or 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.
sage: dw = DyckWord([1,0,1,0]) sage: dw.a_statistic() # 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.a_statistic() 19
sage: DyckWord([1,1,1,1,0,0,0,0]).a_statistic() 6 sage: DyckWord([1,1,1,0,1,0,0,0]).a_statistic() 5 sage: DyckWord([1,1,1,0,0,1,0,0]).a_statistic() 4 sage: DyckWord([1,1,1,0,0,0,1,0]).a_statistic() 3 sage: DyckWord([1,0,1,1,0,1,0,0]).a_statistic() 2 sage: DyckWord([1,1,0,1,1,0,0,0]).a_statistic() 4 sage: DyckWord([1,1,0,0,1,1,0,0]).a_statistic() 2 sage: DyckWord([1,0,1,1,1,0,0,0]).a_statistic() 3 sage: DyckWord([1,0,1,1,0,0,1,0]).a_statistic() 1 sage: DyckWord([1,0,1,0,1,1,0,0]).a_statistic() 1 sage: DyckWord([1,1,0,0,1,0,1,0]).a_statistic() 1 sage: DyckWord([1,1,0,1,0,0,1,0]).a_statistic() 2 sage: DyckWord([1,1,0,1,0,1,0,0]).a_statistic() 3 sage: DyckWord([1,0,1,0,1,0,1,0]).a_statistic() 0
self, pos) |
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]).associated_parenthesis(1) 2 sage: DyckWord([1, 1]).associated_parenthesis(0)
self) |
Returns the b-statistic for the Dyck word.
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 b-statistic of such a path in terms of what is known as the "bounce path". Quoting from [1]:
We can think of our bounce path as describing the trail of a
billiard ball shot North from
, which "bounces" right
whenever it encounters a horizontal step and "bounces" up when it
encounters the line
. The bouncing ball will strike the
diagonal at places
. We define the b-statistic to be the
sum
.
sage: dw = DyckWord([1,1,1,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0]) sage: dw.b_statistic() 7
sage: DyckWord([1,1,1,1,0,0,0,0]).b_statistic() 0 sage: DyckWord([1,1,1,0,1,0,0,0]).b_statistic() 1 sage: DyckWord([1,1,1,0,0,1,0,0]).b_statistic() 2 sage: DyckWord([1,1,1,0,0,0,1,0]).b_statistic() 3 sage: DyckWord([1,0,1,1,0,1,0,0]).b_statistic() 3 sage: DyckWord([1,1,0,1,1,0,0,0]).b_statistic() 1 sage: DyckWord([1,1,0,0,1,1,0,0]).b_statistic() 2 sage: DyckWord([1,0,1,1,1,0,0,0]).b_statistic() 1 sage: DyckWord([1,0,1,1,0,0,1,0]).b_statistic() 4 sage: DyckWord([1,0,1,0,1,1,0,0]).b_statistic() 3 sage: DyckWord([1,1,0,0,1,0,1,0]).b_statistic() 5 sage: DyckWord([1,1,0,1,0,0,1,0]).b_statistic() 4 sage: DyckWord([1,1,0,1,0,1,0,0]).b_statistic() 2 sage: DyckWord([1,0,1,0,1,0,1,0]).b_statistic() 6
REFERENCES:
[1] The
-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.
self) |
Returns the height of the Dyck word.
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.
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
self) |
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 by Haglund in: The
-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: 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]
self) |
Returns the size of the Dyck word, which is the number of opening parentheses in the Dyck word.
sage: DyckWord([1, 0, 1, 0]).size() 2 sage: DyckWord([1, 0, 1, 1, 0]).size() 3
self) |
Bijection of Biane from Dyck words to non crossing partitions Thanks to Mathieu Dutour for describing the bijection.
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]]
self) |
TESTS:
sage: DyckWord([1, 1, 0, 0]).to_ordered_tree() Traceback (most recent call last): ... NotImplementedError: TODO
self) |
sage: DyckWord([]).to_tableau() [] sage: DyckWord([1, 0]).to_tableau() [[2], [1]] sage: DyckWord([1, 1, 0, 0]).to_tableau() [[3, 4], [1, 2]] sage: DyckWord([1, 0, 1, 0]).to_tableau() [[2, 4], [1, 3]] sage: DyckWord([1]).to_tableau() [[1]] sage: DyckWord([1, 0, 1]).to_tableau() [[2], [1, 3]]
self) |
TESTS:
sage: DyckWord([1, 1, 0, 0]).to_triangulation() Traceback (most recent call last): ... NotImplementedError: TODO
Special Functions: __str__
self) |
Returns a string consisting of matched parentheses corresponding to the Dyck word.
sage: print DyckWord([1, 0, 1, 0]) ()() sage: print DyckWord([1, 1, 0, 0]) (())
Class: DyckWordBacktracker
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)
self, k1, k2) |
TESTS:
sage: from sage.combinat.dyck_word import DyckWordBacktracker sage: len(list(DyckWordBacktracker(5, 5))) 42 sage: len(list(DyckWordBacktracker(6,4))) 90 sage: len(list(DyckWordBacktracker(7,0))) 1
Special Functions: __init__,
_rec
self, path, state) |
TESTS:
sage: from sage.combinat.dyck_word import DyckWordBacktracker sage: dwb = DyckWordBacktracker(3, 3) sage: list(dwb._rec([1,1,0],(3, 2))) [([1, 1, 0, 0], (4, 1), False), ([1, 1, 0, 1], (4, 3), False)] sage: list(dwb._rec([1,1,0,0],(4, 0))) [([1, 1, 0, 0, 1], (5, 1), False)] sage: list(DyckWordBacktracker(4, 4)._rec([1,1,1,1],(4, 4))) [([1, 1, 1, 1, 0], (5, 3), False)]
Class: DyckWords_all
self) |
TESTS:
sage: DW = DyckWords() sage: DW == loads(dumps(DW)) True
Functions: list
self) |
TESTS:
sage: DyckWords().list() Traceback (most recent call last): ... NotImplementedError
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: [] in DyckWords() True sage: [1] in DyckWords() False sage: [0] in DyckWords() False sage: [1, 0] in DyckWords() True
self) |
TESTS:
sage: repr(DyckWords()) 'Dyck words'
Class: DyckWords_size
self, k1, [k2=None]) |
TESTS:
sage: DW4 = DyckWords(4) sage: DW4 == loads(dumps(DW4)) True sage: DW42 = DyckWords(4,2) sage: DW42 == loads(dumps(DW42)) True
Functions: count,
iterator,
list
self) |
Returns the number of Dyck words of size n, i.e. the n-th Catalan number.
sage: DyckWords(4).count() 14 sage: ns = range(9) sage: dws = [DyckWords(n) for n in ns] sage: all([ dw.count() == len(dw.list()) for dw in dws]) True
self) |
Returns an iterator for Dyck words with k1 opening and k2 closing parentheses.
sage: [ w for w in DyckWords(0) ] [[]] sage: [ w for w in DyckWords(1) ] [[1, 0]] sage: [ w for w in DyckWords(2) ] [[1, 0, 1, 0], [1, 1, 0, 0]] sage: len([ 'x' for _ in DyckWords(5) ]) 42
self) |
Returns a list of all the Dyck words with k1 opening and k2 closing parentheses.
sage: DyckWords(0).list() [[]] sage: DyckWords(1).list() [[1, 0]] sage: DyckWords(2).list() [[1, 0, 1, 0], [1, 1, 0, 0]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: [1, 0] in DyckWords(1) True sage: [1, 0] in DyckWords(2) False sage: [1, 1, 0, 0] in DyckWords(2) True sage: [1, 0, 0, 1] in DyckWords(2) False sage: [1, 0, 0, 1] in DyckWords(2,2) False sage: [1, 0, 1, 0] in DyckWords(2,2) True sage: [1, 0, 1, 0, 1] in DyckWords(3,2) True sage: [1, 0, 1, 1, 0] in DyckWords(3,2) True sage: [1, 0, 1, 1] in DyckWords(3,1) True
self) |
TESTS:
sage: repr(DyckWords(4)) 'Dyck words with 4 opening parentheses and 4 closing parentheses'