How to compute the set of Dyck paths ?

asked 2015-12-22 16:42:36 +0100

hans
21 ●2 ●5

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 flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2015-12-22 17:44:23 +0100

tmonteil
27413 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2015-12-22 17:49:19 +0100

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}

edit flag offensive delete link

Comments

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.

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

add a comment

answered 2015-12-22 21:36:04 +0100

vdelecroix
7645 ●20 ●85 ●168 http://www.labri.fr/pe...

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]

edit flag offensive delete link

Comments

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?

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

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

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

How to compute the set of Dyck paths ?

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

How to compute the set of Dyck paths ? edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

How to compute the set of Dyck paths ?