Question

用数字 $0$ ， $1$ ， $2$ ， $3$ ， $4$ 组成长度为 $5$ 的字符串。有多少个这样的字符串满足：对每个 $j\in\{1,2,3,4\}$ ，至少有 $j$ 个数字小于 $j$ ？（例如， $02214$ 满足条件，因为它含有至少 $1$ 个小于 $1$ 的数字，至少 $2$ 个小于 $2$ 的数字，至少 $3$ 个小于 $3$ 的数字，且至少 $4$ 个小于 $4$ 的数字。字符串 $23404$ 不满足条件，因为它不含至少 $2$ 个小于 $2$ 的数字。）

How many strings of length $5$ formed from the digits $0,$ $1,$ $2,$ $3,$ $4$ are there such that for each $j\in\{1,2,3,4\},$ at least $j$ of the digits are less than $j?$ (For example, $02214$ satisfies the condition because it contains at least $1$ digit less than $1,$ at least $2$ digits less than $2,$ at least $3$ digits less than $3,$ and at least $4$ digits less than $4.$ The string $23404$ does not satisfy the condition because it does not contain at least $2$ digits less than $2.$ )

$500$

$625$

$1089$

$1199$

$1296$

答案：E

知识点：有限制的排列分类讨论

难度评级：2380

小提示：

“至少有 $j$ 个数字小于 $j$ ” 意味着第 $j$ 小的数字至多为 $j-1$ 。

“At least $j$ digits are less than $j$ ” means the $j$ th smallest digit is at most $j-1$

大提示：

这些正是长度为 $5$ 的停车函数；使用 $6$ 个车位的圆形停车计数

These are parking functions of length $5;$ use the circular-parking count with $6$ spaces

解答：

将五个数字排序为 $d_{(1)}\le d_{(2)}\le\cdots\le d_{(5)}$ 。条件“至少有 $j$ 个数字小于 $j$ ”等价于对 $j=1,2,3,4$ ，有 $d_{(j)}\le j-1$ ，即 $d_{(1)}=0,\ d_{(2)}\le1$ ， $\ d_{(3)}\le2,\ d_{(4)}\le3$ （而 $d_{(5)}\le4$ 自动成立）。

这些字符串恰好是长度为 $5$ 的停车函数。为计数，将 $6$ 个停车位排成圆形，让 $5$ 辆有标号的汽车任意选择首选车位。每辆车向前行驶到第一个空位。在 $6^5$ 个偏好字符串中，同时旋转所有偏好会使唯一的空位依次经过全部 $6$ 个位置。因此，恰有 $\frac{6^5}{6}=6^4=1296$ 个字符串使指定车位为空。将这个车位选作额外的第六个车位，恰好得到上述排序不等式。

因此，正确答案是 E。

Sort the five digits as $d_{(1)}\le d_{(2)}\le\cdots\le d_{(5)}.$ The requirement “at least $j$ digits less than $j$ ” is equivalent to $d_{(j)}\le j-1$ for $j=1,2,3,4,$ i.e. $d_{(1)}=0,\ d_{(2)}\le1,$ $\ d_{(3)}\le2,\ d_{(4)}\le3$ (with $d_{(5)}\le4$ automatic).

These strings are exactly the parking functions of length $5.$ To count them, arrange $6$ parking spaces in a circle and let $5$ labeled cars choose arbitrary preferred spaces. Each car moves forward to the first open space. Among the $6^5$ preference strings, rotating all preferences cycles the unique empty space through all $6$ positions. Therefore exactly $\frac{6^5}{6}=6^4=1296$ strings leave a specified space empty. Choosing that space as the extra sixth space gives precisely the sorted inequalities above.

Thus, the correct answer is E.

2022 AMC 12A 第 24 题

答案：E

难度评级：2380

小提示：

大提示：

解答：

其他年份的第 24 题