Question

有两根可区分的旗杆，还有 $19$ 面旗，其中 $10$ 面是完全相同的蓝旗， $9$ 面是完全相同的绿旗。令 $N$ 为使用所有旗帜的可区分排列数，要求每根旗杆上至少有一面旗，并且任一旗杆上没有两面绿旗相邻。求 $N$ 除以 $1000$ 的余数。

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements using all of the flags in which each flagpole has at least one flag and no two green flags on either pole are adjacent. Find the remainder when $N$ is divided by $1000.$

答案

答案：310

知识点：有限制的排列组合补集计数范德蒙德卷积

难度评级：3060

解答：

假设第一根旗杆得到 $b$ 面蓝旗和 $g$ 面绿旗，第二根得到剩余的 $10 - b$ 面蓝旗和 $9 - g$ 面绿旗。在一根有 $b$ 面蓝旗的旗杆上，绿旗必须占据蓝旗周围 $b + 1$ 个空隙中的不同空隙，有 $\binom{b+1}{g}$ 种。暂时不考虑每根旗杆非空的要求，总数为 $\begin{aligned} &\sum_{b=0}^{10} \sum_{g=0}^{9} \binom{b+1}{g} \\ &\quad {}\cdot \binom{11-b}{9-g} \\ &= \sum_{b=0}^{10} \binom{12}{9} \\ &= 11 \cdot 220 = 2420, \end{aligned}$ 其中内层和由范德蒙德恒等式化简，因为 $(b + 1) + (11 - b) = 12$ 。

使一根旗杆为空的排列，是把全部 $19$ 面旗放在另一根旗杆上；对每个空旗杆选择有 $\binom{11}{9} = 55$ 种。因此 $N = 2420 - 2 \cdot 55 = 2310,$ 所以 $N$ 除以 $1000$ 的余数为 $310$ 。

Suppose the first pole gets $b$ blue and $g$ green flags, the second the remaining $10 - b$ blue and $9 - g$ green. On a pole with $b$ blue flags, the green flags must occupy distinct gaps among the $b + 1$ gaps around the blues, in $\binom{b+1}{g}$ ways. Temporarily ignoring the requirement that each pole be nonempty, the total is $\begin{aligned} &\sum_{b=0}^{10} \sum_{g=0}^{9} \binom{b+1}{g} \\ &\quad {}\cdot \binom{11-b}{9-g} \\ &= \sum_{b=0}^{10} \binom{12}{9} \\ &= 11 \cdot 220 = 2420, \end{aligned}$ where the inner sum collapses by Vandermonde's identity, since $(b + 1) + (11 - b) = 12.$

The arrangements that leave a pole empty put all $19$ flags on one pole, in $\binom{11}{9} = 55$ ways for each choice of pole. Hence $N = 2420 - 2 \cdot 55 = 2310,$ and the remainder when $N$ is divided by $1000$ is $310.$

2008 AIME II 第 12 题

答案：310

难度评级：3060

解答：

其他年份的第 12 题