求 $1,2,3,4,5\text{,}6$ 满足条件的排列的个数数，对任意 $1\leqslant k\leqslant 5$，前 $k$ 项中至少一个比 $k$ 大
【难度】
【出处】
2018年第36届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
461
【解析】
我们下面用枚举法分类计算。
1．如果第一个数字为 $6$，则剩余数字任意排列均满足条件，共 $5\text{!=}120$ 个；
2．如果第一个数字为 $5$，则 $6$ 有四种可能的位置，剩余数有 $4\text{!}$ 种排列方法，一共有 $4\cdot4!=96$ 个；
3．如果第一个数字为 $4$，则可能的形式为 $4\quad6\quad\_\quad\_\quad\_\quad\_\Rightarrow \text{24}$ 个，$4\quad\_\quad6\quad\_\quad\_\quad\_\Rightarrow \text{24}$ 个，$4\quad\_\quad\_\quad6\quad\_\quad\_\Rightarrow \text{24}$ 个，$4\quad\_\quad\_\quad\_\quad6 \quad\_\Rightarrow 5$ 必须在 $46$ 之间，$3\cdot 3\text{!=}18$ 个。一共有 $24+24+24+18\text{=}90$ 个；
4．如果第一个数字为 $3$，则可能的形式为\[\begin{align}
3\quad6\quad\_\quad\_\quad\_\quad\_\Rightarrow \text{24} \\
3\quad\_\quad6\quad\_\quad\_\quad\_\Rightarrow \text{24} \\
3\quad1\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
3\quad2\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
3\quad4\quad\_\quad6 \quad\_\quad\_\Rightarrow 6 \\
3\quad5\quad\_\quad6 \quad\_\quad\_\Rightarrow 6 \\
3\quad5\quad\_\quad\_\quad6 \quad\_\Rightarrow 6 \\
3\quad\_\quad5\quad\_\quad6\quad\_\Rightarrow 6 \\
3\quad\_\quad\_\quad5\quad6\quad\_\Rightarrow \text{4} \\
\end{align}\]，共 $24\cdot 2+4\cdot 2+6\cdot 4+4=84$ 种
5．如果第一个数字为 $3$，则可能的形式为\[\begin{align}
2\quad6\quad\_\quad\_\quad\_\quad\_\Rightarrow \text{24} \\
2\quad\_\quad6\quad\_\quad\_\quad\_\Rightarrow \text{18} \\
2\quad3\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
2\quad4\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
2\quad4\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{6} \\
2\quad5\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{6} \\
2\quad5\quad\_\quad\_\quad6 \quad\_\Rightarrow 6 \\
2\quad\_\quad5\quad\_\quad6\quad\_\Rightarrow 4 \\
2\quad4\quad\_\quad5\quad6\Rightarrow 2 \\
234561\Rightarrow 1 \\
\end{align}\]，共 $24+18+4\cdot2+6\cdot 3+4+2+1\text{=}71$ 种
故一共有 $120+96+90+84+71\text{=}461$ 种
1．如果第一个数字为 $6$，则剩余数字任意排列均满足条件，共 $5\text{!=}120$ 个；
2．如果第一个数字为 $5$，则 $6$ 有四种可能的位置，剩余数有 $4\text{!}$ 种排列方法，一共有 $4\cdot4!=96$ 个；
3．如果第一个数字为 $4$，则可能的形式为 $4\quad6\quad\_\quad\_\quad\_\quad\_\Rightarrow \text{24}$ 个，$4\quad\_\quad6\quad\_\quad\_\quad\_\Rightarrow \text{24}$ 个，$4\quad\_\quad\_\quad6\quad\_\quad\_\Rightarrow \text{24}$ 个，$4\quad\_\quad\_\quad\_\quad6 \quad\_\Rightarrow 5$ 必须在 $46$ 之间，$3\cdot 3\text{!=}18$ 个。一共有 $24+24+24+18\text{=}90$ 个；
4．如果第一个数字为 $3$，则可能的形式为\[\begin{align}
3\quad6\quad\_\quad\_\quad\_\quad\_\Rightarrow \text{24} \\
3\quad\_\quad6\quad\_\quad\_\quad\_\Rightarrow \text{24} \\
3\quad1\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
3\quad2\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
3\quad4\quad\_\quad6 \quad\_\quad\_\Rightarrow 6 \\
3\quad5\quad\_\quad6 \quad\_\quad\_\Rightarrow 6 \\
3\quad5\quad\_\quad\_\quad6 \quad\_\Rightarrow 6 \\
3\quad\_\quad5\quad\_\quad6\quad\_\Rightarrow 6 \\
3\quad\_\quad\_\quad5\quad6\quad\_\Rightarrow \text{4} \\
\end{align}\]，共 $24\cdot 2+4\cdot 2+6\cdot 4+4=84$ 种
5．如果第一个数字为 $3$，则可能的形式为\[\begin{align}
2\quad6\quad\_\quad\_\quad\_\quad\_\Rightarrow \text{24} \\
2\quad\_\quad6\quad\_\quad\_\quad\_\Rightarrow \text{18} \\
2\quad3\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
2\quad4\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{4} \\
2\quad4\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{6} \\
2\quad5\quad\_\quad6 \quad\_\quad\_\Rightarrow \text{6} \\
2\quad5\quad\_\quad\_\quad6 \quad\_\Rightarrow 6 \\
2\quad\_\quad5\quad\_\quad6\quad\_\Rightarrow 4 \\
2\quad4\quad\_\quad5\quad6\Rightarrow 2 \\
234561\Rightarrow 1 \\
\end{align}\]，共 $24+18+4\cdot2+6\cdot 3+4+2+1\text{=}71$ 种
故一共有 $120+96+90+84+71\text{=}461$ 种
答案
解析
备注
