HMMT 二月 2002 · 冲刺赛 · 第 24 题

HMMT February 2002 — Guts Round — Problem 24

[7] A restricted path of length n is a path of length n such that for all i between 1 and n − 2 inclusive, if the i th step is upward, the i + 1st step must be rightward. Find the number of restricted paths that start at (0 , 0) and end at (7 , 3). 4

解析

A restricted path of length n is a path of length n such that for all i between 1 and n − 2 inclusive, if the i th step is upward, the i + 1st step must be rightward. Find the number of restricted paths that start at (0 , 0) and end at (7 , 3). Solution: This is equal to the number of lattice paths from (0 , 0) to (7 , 3) that use only rightward and diagonal (upward+rightward) steps plus the number of lattice paths from (0 , 0) to (7 , 2) that use only rightward and diagonal steps, which is equal to the number of paths (as defined above) from (0 , 0) to (4 , 3) plus the number of paths from (0 , 0) to (5 , 2), ( ) ( ) 4+3 5+2 or + = 56 . 3 2