Question

设 $(a_1, a_2, \ldots, a_{10})$ 是前 $10$ 个正整数的一个排列，并且对每个 $2 \le i \le 10$ ， $a_i + 1$ 或 $a_i - 1$ 或两者都在 $a_i$ 之前的某处出现。这样的排列有多少个？

Let $(a_1, a_2, \ldots, a_{10})$ be a list of the first $10$ positive integers such that for each $2 \le i \le 10$ either $a_i + 1$ or $a_i - 1$ or both appear somewhere before $a_i$ in the list. How many such lists are there?

$120$

$512$

$1024$

$181{,}440$

$362{,}880$

答案：B

知识点：双射组合

难度评级：1990

小提示：

大于或等于 $a_1$ 的数必须按递增顺序出现，小于 $a_1$ 的数必须按递减顺序出现

The numbers greater than or equal to $a_1$ must appear in increasing order, and those less than $a_1$ in decreasing order

大提示：

选择哪些位置放较小的数即可确定整个排列，得到 $\sum_k \binom{9}{k}$

Choosing which positions hold the small numbers determines the list, giving $\sum_k \binom{9}{k}$

解答：

一旦固定 $a_1=k$ ，数 $k,k+1,\ldots,10$ 必须从左到右按递增顺序出现，而数 $1,\ldots,k-1$ 必须从右到左按递增顺序出现（这样每个新出现的较小数都有它的后继已经放好）。

对每个 $k$ ，只需选择第一个位置之后的 $9$ 个位置中哪些放小于 $k$ 的数，因此有 $\binom{9}{k-1}$ 个排列。

求和得 $\begin{aligned} \sum_{k=1}^{10}\binom{9}{k-1} &= \sum_{j=0}^{9}\binom{9}{j} \\ &= 2^9=512 \end{aligned}\text{。}$

因此正确答案是 B。

Once $a_1=k$ is fixed, the numbers $k,k+1,\ldots,10$ must appear left to right in increasing order, and the numbers $1,\ldots,k-1$ must appear from right to left in increasing order (so each new small number has its successor already placed).

For each $k,$ the list is determined by choosing which of the $9$ positions after the first hold the numbers below $k,$ giving $\binom{9}{k-1}$ lists.

Summing, $\begin{aligned} \sum_{k=1}^{10}\binom{9}{k-1} &= \sum_{j=0}^{9}\binom{9}{j} \\ &= 2^9=512. \end{aligned}$

Thus, the correct answer is B.

2012 AMC 12B 第 18 题

答案：B

难度评级：1990

小提示：

大提示：

解答：

其他年份的第 18 题