老板将要打印的信件交给秘书，每次给一封，且放在信堆的最上面，秘书一有空就从最上面拿一封信来打，有一天共有9封信要打，老板按第一封、第二封、…、第九封的顺序交给秘书．午饭的时候，秘书告诉同事，已把第八封信打好了，但未透露上午工作的其他情况．这个同事很想知道还剩下哪些信件没有打，还想知道按什么样的顺序来打印．
根据以上的信息，下午打的信的顺序有多少种可能（没有要打的信也是一种可能）？
根据以上的信息，下午打的信的顺序有多少种可能（没有要打的信也是一种可能）？
【难度】
【出处】
1988年第6届美国数学邀请赛（AIME）
【标注】
【答案】
704
【解析】
分两种情况考虑．
第一种情况：第九封信在中午以前送给秘书．
这可能的顺序就是集合 $T=\left\{1 2 \cdots 6 7 9 \right\}$ 的可能的子集数目．事实上，每一个子集都是可能出现的顺序，因此秘书可以把每个不在子集中的号码的信一送来就打完它，而不打别的信．$T$ 有8个元素，所以有 ${{2}^{8}}=256$ 个子集（包括空集）．
第二种情况：第九封信在午饭以后才送到秘书处．
现在的问题是在第九封信会“夹”在什么地方？$v=\left\{1 2 \cdots 6 7 \right\}$ 的每个子集中每个位子都是可能的．例如，中午剩下的信为6，3，2，那么如果老板在秘书刚打完后就把第九封信送到，则6，3，9，2的打字顺序将会产生．
对于 $k$ 封信的排列有 $k+1$ 个位置可以放入9，但是如果9位于数列的最前头，也就是说，在秘书下午还未工作之前，老板便把第九封从送到，这样便与第一种情况重复，除去这种情形，共有 $\displaystyle \sum\limits_{k=0}^{7}{k\text{C}_{7}^{k}}=7\left( {{2}^{7}}-1\right)=448$．
所以，共有 $256+448=704$ 种可能的打信顺序．
第一种情况：第九封信在中午以前送给秘书．
这可能的顺序就是集合 $T=\left\{1 2 \cdots 6 7 9 \right\}$ 的可能的子集数目．事实上，每一个子集都是可能出现的顺序，因此秘书可以把每个不在子集中的号码的信一送来就打完它，而不打别的信．$T$ 有8个元素，所以有 ${{2}^{8}}=256$ 个子集（包括空集）．
第二种情况：第九封信在午饭以后才送到秘书处．
现在的问题是在第九封信会“夹”在什么地方？$v=\left\{1 2 \cdots 6 7 \right\}$ 的每个子集中每个位子都是可能的．例如，中午剩下的信为6，3，2，那么如果老板在秘书刚打完后就把第九封信送到，则6，3，9，2的打字顺序将会产生．
对于 $k$ 封信的排列有 $k+1$ 个位置可以放入9，但是如果9位于数列的最前头，也就是说，在秘书下午还未工作之前，老板便把第九封从送到，这样便与第一种情况重复，除去这种情形，共有 $\displaystyle \sum\limits_{k=0}^{7}{k\text{C}_{7}^{k}}=7\left( {{2}^{7}}-1\right)=448$．
所以，共有 $256+448=704$ 种可能的打信顺序．
答案
解析
备注
