Question

罗伯特有 $4$ 枚无法区分的金币和 $4$ 枚无法区分的银币。每枚硬币的一面刻有人脸，另一面没有。他想把这八枚硬币在桌上叠成一摞，使得没有两枚相邻硬币是人脸对着人脸。求 $8$ 枚硬币可能的可区分排列数。

Robert has $4$ indistinguishable gold coins and $4$ indistinguishable silver coins. Each coin has an engraving of a face on one side, but not on the other. He wants to stack the eight coins on a table into a single stack so that no two adjacent coins are face to face. Find the number of possible distinguishable arrangements of the $8$ coins.

答案

答案：630

知识点：有限制的排列组合乘法原理

难度评级：2300

小提示：

分别处理朝向和颜色。把每枚硬币从底到顶的朝向记为 $U$ （人脸朝上）或 $D$ （人脸朝下）。

Handle orientations and colors separately. Record each coin’s orientation, bottom to top, as $U$ (face up) or $D$ (face down).

大提示：

人脸对人脸恰好发生在一个 $U$ 正好位于一个 $D$ 下方时，所以所有 $D$ 都必须在所有 $U$ 之前

Face to face happens exactly when a $U$ sits directly below a $D,$ so all the $D$ ’s must come before all the $U$ ’s

解答：

独立地选择硬币朝向以及金银位置。把从底到顶的朝向记录成由 $U$ （刻有人脸的一面朝上）和 $D$ （刻有人脸的一面朝下）组成的字符串。两枚相邻硬币人脸对着人脸，当且仅当下方硬币的刻面朝上而上方硬币的刻面朝下，也就是当且仅当一个 $U$ 后面紧接着一个 $D$ 。

一个由 $U$ 和 $D$ 组成的字符串避免模式 $UD$ ，当且仅当每个 $D$ 都在每个 $U$ 之前，所以字符串形如 $\text{D}^i\text{U}^{8-i}$ ，其中 $i = 0, 1, \ldots, 8$ ：共有 $9$ 种允许的朝向字符串。独立地，金币占据 $8$ 个位置中的 $4$ 个，有 $\binom{8}{4} = 70$ 种方式。

总数为 $9 \cdot 70 = 630$ 。

Choose the coin orientations and the gold/silver positions independently. Record the orientations from bottom to top as a string of $U$ (engraved face up) and $D$ (engraved face down). Two adjacent coins are face to face exactly when the lower coin’s engraved side faces up and the upper coin’s engraved side faces down — that is, exactly when a $U$ is immediately followed by a $D.$

A string of $U$ ’s and $D$ ’s avoids the pattern $UD$ exactly when every $D$ precedes every $U,$ so the string is $\text{D}^i\text{U}^{8-i}$ for some $i = 0, 1, \ldots, 8:$ there are $9$ allowable orientation strings. Independently, the gold coins occupy $4$ of the $8$ positions in $\binom{8}{4} = 70$ ways.

The total is $9 \cdot 70 = 630.$

2005 AIME I 第 5 题

答案：630

难度评级：2300

小提示：

大提示：

解答：

其他年份的第 5 题