Question

一只青蛙位于坐标平面的原点。从点 $(x, y)$ 出发，青蛙可以跳到 $(x + 1, y)$ 、 $(x + 2, y)$ 、 $(x, y + 1)$ 或 $(x, y + 2)$ 中任一点。求青蛙从 $(0, 0)$ 出发并最终到达 $(4, 4)$ 的不同跳跃序列个数。

A frog is positioned at the origin in the coordinate plane. From the point $(x, y),$ the frog can jump to any of the points $(x + 1, y),$ $(x + 2, y),$ $(x, y + 1),$ or $(x, y + 2).$ Find the number of distinct sequences of jumps in which the frog begins at $(0, 0)$ and ends at $(4, 4).$

答案

答案：556

知识点：分拆与有序分拆多重集排列分类讨论

难度评级：2920

解答：

水平跳跃是若干长度为 $1$ 或 $2$ 的步长，总和为 $4$ ，所以作为多重集合只能是 $\{1,1,1,1\}$ 、 $\{1,1,2\}$ ，或 $\{2,2\}$ ，竖直跳跃也一样。对任意一对多重集合，所有跳跃的任意排列都是有效序列，排列数就是合并后多重集合的多项式系数。

九种情况给出 $\begin{aligned} &\binom{8}{4} = 70, \\ &\quad \frac{7!}{4!\,2!} = 105 \text{ (twice)}, \\ &\quad \frac{6!}{4!\,2!} = 15 \text{ (twice)}, \end{aligned}$ $\begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30 \text{ (twice)}, \\ &\quad \binom{4}{2} = 6. \end{aligned}$

总数为 $70 + 2 \cdot 105 + 2 \cdot 15$ $+ 180 + 2 \cdot 30 + 6$ $= 556$ 。

The horizontal jumps are steps of $1$ or $2$ summing to $4,$ so as a multiset they are $\{1,1,1,1\},$ $\{1,1,2\},$ or $\{2,2\},$ and the same holds for the vertical jumps. For any choice of the two multisets, every ordering of all the jumps is a valid sequence, and the number of orderings is the multinomial coefficient of the combined multiset.

The nine cases give $\begin{aligned} &\binom{8}{4} = 70, \\ &\quad \frac{7!}{4!\,2!} = 105 \text{ (twice)}, \\ &\quad \frac{6!}{4!\,2!} = 15 \text{ (twice)}, \end{aligned}$ $\begin{aligned} &\frac{6!}{2!\,2!} = 180, \\ &\quad \frac{5!}{2!\,2!} = 30 \text{ (twice)}, \\ &\quad \binom{4}{2} = 6. \end{aligned}$

The total is $70 + 2 \cdot 105 + 2 \cdot 15$ $+ 180 + 2 \cdot 30 + 6$ $= 556.$

2018 AIME II 第 8 题

答案：556

难度评级：2920

解答：

其他年份的第 8 题