PUMaC 2023 · 团队赛 · 第 14 题

PUMaC 2023 — Team Round — Problem 14

Kelvin the frog is hopping on the coordinate plane R . He starts at the origin, and every second, he hops one unit to the right, left, up, or down, such that he always remains in the first quadrant { ( x, y ) : x ≥ 0 , y ≥ 0 } . In how many ways can Kelvin make his first 14 jumps such that his 14th jump lands at the origin?

解析

Kelvin the frog is hopping on the coordinate plane R . He starts at the origin, and every second, he hops one unit to the right, left, up, or down, such that he always remains in the first quadrant { ( x, y ) : x ≥ 0 , y ≥ 0 } . In how many ways can Kelvin make his first 14 jumps such that his 14th jump lands at the origin? Proposed by Ben Zenker Answer: 613470 Let 2 L = 14 be the length of the walk. Let 2 k denote the number of jumps made to the left/right, so that 2( L − k ) jumps are made up/down. The number of paths is therefore L X 2 L C C (1) k L − k 2 k k =0 2 k 1 where C = denotes the k -th Catalan number. We claim that the above is precisely k k +1 k C C , which for L = 7 equals C · C = 429 · 1430 = 613470, our answer. L L +1 7 8 We now prove the claim. For convenience replace L with the variable n . Note that 2 n 2 n 1 2 k 1 2( n − k ) C C = · · (2) k n − k 2 k 2 k k + 1 k n − k + 1 n − k (2 n )! = (3) ( k + 1)!( n − k )! · ( n − k + 1)! k ! 1 2 n n + 1 n + 1 = (4) 2 ( n + 1) n k k + 1 1 n + 1 n + 1 = C · (5) n n + 1 k n − k Summing over k and applying Vandermonde’s identity, this becomes 1 2 n + 2 1 2( n + 1) C · = C · (6) n n n + 1 n n + 2 n + 1 = C · C (7) n n +1 as claimed. The result follows.