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