Dyck Words

AUTHORS:

  • Mike Hansen
  • Dan Drake (2008-05-30): DyckWordBacktracker support
sage.combinat.dyck_word.DyckWord(dw=None, noncrossing_partition=None)

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

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)
__init__(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
_rec(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 sage.combinat.dyck_word.DyckWord_class(l)
__str__()

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

Returns the a-statistic for the Dyck word.

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 a-statistic, or 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.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
associated_parenthesis(pos)

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

Returns the b-statistic for the Dyck word.

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 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 \sum_{i=1}^{r-1} j_i.

(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 \sum_{i=1}^{r-1} n - j_i.

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:

  • [1] 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.
height()

Returns the height of the Dyck word.

We view the Dyck word as a Dyck path from (0,0) to (n,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.

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
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 by Haglund in: 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.

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

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

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

TESTS:

sage: DyckWord([1, 1, 0, 0]).to_ordered_tree()
...
NotImplementedError: TODO
to_tableau()

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

TESTS:

sage: DyckWord([1, 1, 0, 0]).to_triangulation()
...
NotImplementedError: TODO
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
__contains__(x)

TESTS:

sage: [] in DyckWords()
True
sage: [1] in DyckWords()
False
sage: [0] in DyckWords()
False 
sage: [1, 0] in DyckWords()
True
__init__()

TESTS:

sage: DW = DyckWords()
sage: DW == loads(dumps(DW))
True
__repr__()

TESTS:

sage: repr(DyckWords())
'Dyck words'
_infinite_cclass_slice(n)

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

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
__init__(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
__iter__()

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

TESTS:

sage: repr(DyckWords(4))
'Dyck words with 4 opening parentheses and 4 closing parentheses'
cardinality()

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

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)
...
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.replace_parens(x)

EXAMPLES:

sage: from sage.combinat.dyck_word import replace_parens
sage: replace_parens('(')
1
sage: replace_parens(')')
0
sage: replace_parens(1)
...
ValueError
sage.combinat.dyck_word.replace_symbols(x)

EXAMPLES:

sage: from sage.combinat.dyck_word import replace_symbols
sage: replace_symbols(1)
'('
sage: replace_symbols(0)
')'
sage: replace_symbols(3)
...
ValueError

Previous topic

Dancing links C++ wrapper

Next topic

Finite combinatorial classes

This Page