18.11 Dyck Words

Module: sage.combinat.dyck_word

Dyck Words

Author Log:

Module-level Functions

DyckWord( [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]

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 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$ .

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

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

from_ordered_tree( tree)

TESTS:

sage: sage.combinat.dyck_word.from_ordered_tree(1)
Traceback (most recent call last):
...
NotImplementedError: TODO

is_a( 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

is_a_prefix( 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

replace_parens( 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

replace_symbols( 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

class DyckWord_class

Functions: a_statistic,$ \,$ associated_parenthesis,$ \,$ b_statistic,$ \,$ height,$ \,$ peaks,$ \,$ size,$ \,$ to_noncrossing_partition,$ \,$ to_ordered_tree,$ \,$ to_tableau,$ \,$ to_triangulation

a_statistic( self)

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.

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

b_statistic( self)

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 $ (1,0)$ and '0's represent steps in the direction $ (0,1)$ . 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". Quoting from [1]:

We can think of our bounce path as describing the trail of a billiard ball shot North from $ (0,0)$ , which "bounces" right whenever it encounters a horizontal step and "bounces" up 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} n - j_i$ .

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

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.

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( 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 $ 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.

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

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

to_ordered_tree( self)

TESTS:

sage: DyckWord([1, 1, 0, 0]).to_ordered_tree()
Traceback (most recent call last):
...
NotImplementedError: TODO

to_tableau( 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]]

to_triangulation( self)

TESTS:

sage: DyckWord([1, 1, 0, 0]).to_triangulation()
Traceback (most recent call last):
...
NotImplementedError: TODO

Special Functions: __str__

__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

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

DyckWordBacktracker( 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

_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

class DyckWords_all
DyckWords_all( self)

TESTS:

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

Functions: list

list( self)

TESTS:

sage: DyckWords().list()
Traceback (most recent call last):
...
NotImplementedError

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

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

__repr__( self)

TESTS:

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

Class: DyckWords_size

class DyckWords_size
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

count( 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

iterator( 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

list( 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__

__contains__( 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

__repr__( self)

TESTS:

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

See About this document... for information on suggesting changes.