Question

对满足 $a + b \le 6$ 的非负整数 $a$ 和 $b$ ，令 $T(a, b) = \binom{6}{a}\binom{6}{b}\binom{6}{a+b}$ 。设 $S$ 为所有满足 $a + b \le 6$ 的非负整数 $a$ 和 $b$ 对应的 $T(a, b)$ 之和。求 $S$ 除以 $1000$ 的余数。

For nonnegative integers $a$ and $b$ with $a + b \le 6,$ let $T(a, b) = \binom{6}{a}\binom{6}{b}\binom{6}{a+b}.$ Let $S$ denote the sum of all $T(a, b),$ where $a$ and $b$ are nonnegative integers with $a + b \le 6.$ Find the remainder when $S$ is divided by $1000.$

答案

答案：564

知识点：组合双重计数

难度评级：2650

解答：

利用对称性 $\binom{6}{a+b} = \binom{6}{6-(a+b)}$ ，令 $c = 6 - a - b$ 可将和改写为 $S = \sum_{a+b+c=6} \binom{6}{a}\binom{6}{b}\binom{6}{c}.$

每一项表示从一个 $6$ 元集合中选 $a$ 个元素、从第二个 $6$ 元集合中选 $b$ 个元素、从第三个六元集合中选 $c$ 个元素的方法数。对所有 $a + b + c = 6$ 求和，就数出了从合并后的 $18$ 元集合中选六个元素的所有方法，所以 $S = \binom{18}{6} = 18564$ 。

除以 $1000$ 的余数为 $564$ 。

By the symmetry $\binom{6}{a+b} = \binom{6}{6-(a+b)},$ substituting $c = 6 - a - b$ turns the sum into $S = \sum_{a+b+c=6} \binom{6}{a}\binom{6}{b}\binom{6}{c}.$

Each term counts the ways to choose $a$ elements from one $6$ -element set, $b$ from a second, and $c$ from a third. Summed over all $a + b + c = 6,$ this counts every way to choose $6$ elements from the combined $18$ -element set, so $S = \binom{18}{6} = 18564.$

The remainder upon division by $1000$ is $564.$

2017 AIME I 第 7 题

答案：564

难度评级：2650

解答：

其他年份的第 7 题