AUTHORS:
Returns a Dyck word object
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(noncrossing_partition=[[1],[2]])
[1, 0, 1, 0]
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:
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
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)]
Returns a string consisting of matched parentheses corresponding to the Dyck word.
EXAMPLES:
sage: print DyckWord([1, 0, 1, 0])
()()
sage: print DyckWord([1, 1, 0, 0])
(())
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.
EXAMPLES:
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
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]).associated_parenthesis(1)
2
sage: DyckWord([1, 1]).associated_parenthesis(0)
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”.
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), ... , (j_r-1, j_r-1), (j_r, j_r) = (n, n)$.
We define the b-statistic to be the sum .
(0, 0), (j_1, j_1), (j_2, j_2), ... , (j_r-1, j_r-1), (j_r, j_r) = (n, n).
We define the b-statistic to be the sum
.
EXAMPLES:
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:
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.
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
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.
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]
Returns the size of the Dyck word, which is the number of opening parentheses in the Dyck word.
EXAMPLES:
sage: DyckWord([1, 0, 1, 0]).size()
2
sage: DyckWord([1, 0, 1, 1, 0]).size()
3
Bijection of Biane from Dyck words to non crossing partitions Thanks to Mathieu Dutour for describing the bijection.
EXAMPLES:
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]]
TESTS:
sage: DyckWord([1, 1, 0, 0]).to_ordered_tree()
...
NotImplementedError: TODO
EXAMPLES:
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]]
TESTS:
sage: DyckWord([1, 1, 0, 0]).to_triangulation()
...
NotImplementedError: TODO
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
.
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: 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]]
TESTS:
sage: [] in DyckWords()
True
sage: [1] in DyckWords()
False
sage: [0] in DyckWords()
False
sage: [1, 0] in DyckWords()
True
TESTS:
sage: DW = DyckWords()
sage: DW == loads(dumps(DW))
True
TESTS:
sage: repr(DyckWords())
'Dyck words'
Needed by InfiniteAbstractCombinatorialClass to build __iter__.
TESTS:
sage: DyckWords()._infinite_cclass_slice(4) == DyckWords(4)
True
sage: it = iter(DyckWords()) # indirect doctest
sage: [it.next() for i in range(10)]
[[], [1, 0], [1, 0, 1, 0], [1, 1, 0, 0], [1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0], [1, 0, 1, 0, 1, 0, 1, 0]]
EXAMPLES:
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
TESTS:
sage: DW4 = DyckWords(4)
sage: DW4 == loads(dumps(DW4))
True
sage: DW42 = DyckWords(4,2)
sage: DW42 == loads(dumps(DW42))
True
Returns an iterator for Dyck words with k1 opening and k2 closing parentheses.
EXAMPLES:
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
TESTS:
sage: repr(DyckWords(4))
'Dyck words with 4 opening parentheses and 4 closing parentheses'
Returns the number of Dyck words of size 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
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]]
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
TESTS:
sage: sage.combinat.dyck_word.from_ordered_tree(1)
...
NotImplementedError: TODO
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
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
EXAMPLES:
sage: from sage.combinat.dyck_word import replace_parens
sage: replace_parens('(')
1
sage: replace_parens(')')
0
sage: replace_parens(1)
...
ValueError
EXAMPLES:
sage: from sage.combinat.dyck_word import replace_symbols
sage: replace_symbols(1)
'('
sage: replace_symbols(0)
')'
sage: replace_symbols(3)
...
ValueError