About Warm-ups Problems News

Problem 24

Posted 03/01/2016
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

This problem is about colored Motzkin paths. Motzkin paths are paths from $(0,0)$ to $(n,0)$ using $(1,0)$, $(1,1)$, $(1,-1)$ as steps that never go below the $X$-axis. Then we shall color each horizontal step. In this problem, we do not want adjacent horizontal steps share a color.

Two steps are said to be adjacent if there are no other steps in between.
Suppose $a(n)$ is the $3$-colored Motzkin paths such that no adjacent horizontal stpes share a color.

Find $a(n)$.


A more general problem is that how many $k$-colored Motzkin paths such that no adjacent horizontal steps share a color.







Back to top