Question

在办公室里，一天中的不同时刻，老板会交给秘书一封待打字的信，并每次都把信放在秘书收件箱中信堆的最上面。秘书有空时，就从最上面取下一封信并打字。当天共有九封信要打，老板依次按 $1$ 、 $2$ 、 $3$ 、 $4$ 、 $5$ 、 $6$ 、 $7$ 、 $8$ 、 $9$ 的顺序送来。

离开去吃午饭时，秘书告诉同事信 $8$ 已经打完，但没有透露上午打字工作的其他情况。同事想知道九封信中哪些留到午饭后打，以及它们将按什么顺序打。根据以上信息，午饭后的打字顺序共有多少种可能？（没有任何信剩下也是一种可能。）

In an office at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary’s in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day, and the boss delivers them in the order $1,$ $2,$ $3,$ $4,$ $5,$ $6,$ $7,$ $8,$ $9.$

While leaving for lunch, the secretary tells a colleague that letter $8$ has already been typed, but says nothing else about the morning’s typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Based upon the above information, how many such after-lunch typing orders are possible? (That there are no letters left to be typed is one of the possibilities.)

答案

答案：704

知识点：有限制的排列子集乘法原理

难度评级：2520

小提示：

信 $8$ 打完后， $1,\ldots,7$ 中剩余的信以后必须按递减顺序打

After $8$ has been typed, any remaining letters among $1,\ldots,7$ must later be typed in decreasing order

大提示：

根据 $9$ 是午饭前已经打完，还是仍需插入之后的顺序，分情况讨论

Separate the cases according to whether $9$ was typed before lunch or remains to be inserted into the later order

解答：

信 $8$ 打完后， $1,\ldots,7$ 的任意子集都可能留在信堆中，而剩余的信以后必须按递减顺序打。如果 $9$ 已经打完，选择该子集便给出 $2^7=128$ 种可能顺序。

如果 $9$ 留下，则从七封编号较小的信中选 $k$ 封，并把 $9$ 插入它们递减顺序中的任意 $k+1$ 个位置之一。共有 $\begin{aligned}\sum_{k=0}^7\binom7k(k+1)&=7\cdot2^6+2^7\\&=576\end{aligned}$ 种。每种顺序都可通过恰当安排上午的送信与打字过程实现，所以总数为 $128+576=704$ 。

Any subset of $1,\ldots,7$ can remain in the stack after $8$ has been typed, and those remaining letters must later be typed in decreasing order. If $9$ was already typed, choosing that subset gives $2^7=128$ possible orders.

If $9$ remains, choose $k$ of the seven smaller letters and insert $9$ into any of the $k+1$ positions in their decreasing order. This gives $\begin{aligned}\sum_{k=0}^7\binom7k(k+1)&=7\cdot2^6+2^7\\&=576.\end{aligned}$ Every such order can be realized by suitable morning choices, so the total is $128+576=704.$

1988 AIME 第 15 题

答案：704

难度评级：2520

小提示：

大提示：

解答：

其他年份的第 15 题