# How to compute the set of Dyck paths ?

I am new to SAGE and try to experiment with it. So I apologize if my question is too trivial. I am interested to do Dyck paths with SAGE. I understand that

D=DyckWords(n)

D.list()

gives Dyck words as 2n-tuples of n numbers 0,1. But I want to get the corresponding Dyck paths by replacing 1 with an up-step (1,1) and 0 with a down-step (1,-1) represented by the (2n+1)-tuple of the heights of the path.

Thus instead of w=[1,1,1,0,0,1,0,0] I want d=[0,1,2,3,2,1,2,1,0] with height h(d)=3.

How do I get this? And how to compute the height of the path? More precisely how to compute the set of all (d,h(d))for d in D?

edit retag close merge delete

Sort by ยป oldest newest most voted

As you can see, d is a kind of discrete primitive of w. So you can compute it as follows:

sage: def primitive(w):
....:     height = 0
....:     d = [height]
....:     for i in w:
....:         if i == 1:
....:             height += 1
....:             d.append(height)
....:         else:
....:             height -= 1
....:             d.append(height)
....:     return d

sage: w=[1,1,1,0,0,1,0,0]
sage: primitive(w)
[0, 1, 2, 3, 2, 1, 2, 1, 0]


You can get its height as follows:

sage: max(primitive(w))
3


You can get all primitives of all Dyck words of a given length as follows:

sage: [primitive(w) for w in DyckWords(4)]
[[0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 2, 1, 0],
[0, 1, 0, 1, 2, 1, 0, 1, 0],
[0, 1, 0, 1, 2, 1, 2, 1, 0],
[0, 1, 0, 1, 2, 3, 2, 1, 0],
[0, 1, 2, 1, 0, 1, 0, 1, 0],
[0, 1, 2, 1, 0, 1, 2, 1, 0],
[0, 1, 2, 1, 2, 1, 0, 1, 0],
[0, 1, 2, 1, 2, 1, 2, 1, 0],
[0, 1, 2, 1, 2, 3, 2, 1, 0],
[0, 1, 2, 3, 2, 1, 0, 1, 0],
[0, 1, 2, 3, 2, 1, 2, 1, 0],
[0, 1, 2, 3, 2, 3, 2, 1, 0],
[0, 1, 2, 3, 4, 3, 2, 1, 0]]


Hence you can get the set of heights as follows:

sage: {max(primitive(w)) for w in DyckWords(4)}
{1, 2, 3, 4}

more

Thank you very much. I would also like to know where I can find more about lattice paths in SAGE, e.g. how to compute number of peaks or valleys, Motzkin paths, etc.

( 2015-12-23 09:32:53 +0100 )edit

A one line conversion

sage:  w = [1,1,1,0,0,1,0,0]
sage: for i in range(1,len(w)): w[i] = w[i-1] + 2*w[i]-1
sage: print w
[1, 2, 3, 2, 1, 2, 1, 0]

more

Thank you very much. I wanted to do the same as in the second answer: def prim(w):

for i in range(1,len(w)): w[i] = w[i-1] + 2*w[i]-1


[prim(w) for w in DyckWords(4)]

but got TypeError: 'CompleteDyckWords_size_with_category.element_class' object does not support item assignment. How can this be corrected?

( 2015-12-23 09:39:11 +0100 )edit

Yes. Dyck words are not list (even though they are printed as such). You need to convert them to list first

sage: d = DyckWords(5).an_element()
sage: print d
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
sage: print type(d)
<class 'sage.combinat.dyck_word.CompleteDyckWords_size_with_category.element_class'>
sage: l = list(d)
sage: print type(l)
<type 'list'>
sage: print l
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

( 2015-12-23 11:53:59 +0100 )edit