Ask Your Question
1

How to compute the set of Dyck paths ?

asked 2015-12-22 09:42:36 -0600

hans gravatar image

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

2 answers

Sort by ยป oldest newest most voted
0

answered 2015-12-22 14:36:04 -0600

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 more

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 gravatar imagehans ( 2015-12-23 02:39:11 -0600 )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 gravatar imagevdelecroix ( 2015-12-23 04:53:59 -0600 )edit
0

answered 2015-12-22 10:44:23 -0600

tmonteil gravatar image

updated 2015-12-22 10:49:19 -0600

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 more

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 gravatar imagehans ( 2015-12-23 02:32:53 -0600 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-12-22 09:38:20 -0600

Seen: 90 times

Last updated: Dec 22 '15