Let m_n be the number ways to form "mountain ranges" with n upstrokes and n downstrokes that all stay above th?

An ESL Learner

2009-12-04 10:31 am

Let m_n be the number ways to form "mountain ranges" with n upstrokes and n downstrokes that all stay above the original line. For example, when n = 3,
........................................./∖
............../∖..../∖......./∖/∖..../..∖
/∖/∖/∖, /∖/..∖, /..∖/∖, /.....∖, /....∖

Show that m_n = p_n.

更新1:

........................../∖ ./ = ....../...∖ /.......∖............./......∖

更新2:

........................../∖ ./.............= ....../...∖ /.......∖............./......∖

回答 (1)

[匿名]

2009-12-06 5:06 pm

✔ 最佳答案

Given the other question, this is only a matter of establishing, for each n, a bijection between the set of "moutain ranges" and the set of parenthesis sequences with n pairs.

Given a "range", transform it into a parenthesis sequence by associating "/" with "(" and "\" with ")".

I'll leave the detailed verification that this defines a bijection to you.

👍 2 👎 0