经理将要打印的信件交给秘书，每次给一封，且放在信封的最上面，秘书一有空就从最上面拿一封信来打．有一天共有9封信打，经理按第1封，第2封，…，第9封的顺序交给秘书．午饭时，秘

Question

经理将要打印的信件交给秘书，每次给一封，且放在信封的最上面，秘书一有空就从最上面拿一封信来打．有一天共有9封信打，经理按第1封，第2封，…，第9封的顺序交给秘书．午饭时，秘书告诉同事，已把第8封信打印好了，但未透露上午工作的其他情况，这个同事很想知道是按什么顺序来打印．根据以上信息，下午打印的信的顺序有多少种可能？（没有要打的信也是一种可能）

Answer 1

根据最后一封信来计数：
（1）第9封信在上午送给秘书；
于是，T={1，2，3，4，5，6，7，9}
则下午打印的每种可能都是T的一个子集，
因为秘书可以把不在子集中的信件上午一送来就打完了，而未打别的信．
集T有8个元素，故有2⁸=256个不同子集（包括空集）．
（2）第9封信在午后才送给秘书；
令S={1，2，3，4，5，6，7}，
则上午未打印的信的号码是S的一个子集．若将9排在子集之后，则与（1）中的情形相同，
故只有子集中至少有一封信已把号码9放在该子集的非最后的位置上．
对于有k个元素的子集，号码9有k个位置可放，
即可放在第i一1个元素之后和i个元素之前，i=1，2，…，k．于是不同的顺序总数为：
0×C

0

7

+1×C

1

7

+2×C

2

7

+…+7×C

7

7

=7×2⁷÷2=7×2⁶=448
即下午有448种可能的打印顺序．
所以，下午共有256+448=704种打印的方法；
答：下午打印的信的顺序有704种可能．