1.12 放回抽样和无放回抽样

考虑一个有限集合的抽样问题.例如，一张2美元的强力球彩票由5个1到69之间的整数组成.如果这5个号码都与中奖号码相匹配，玩家就能赢得[7]一百万美元的奖金！

要计算中奖的概率，需要计算所有可能的彩票总数.答案取决于两个因素：（1）数字能重复吗？（2）是否考虑顺序？根据这两个因素，彩票总数有四种不同的值.

根据数字能否重复，第一个问题被称为“放回抽样”和“无放回抽样”.在实际的强力球游戏中，69个编号的乒乓球被放入一个有小出口的旋转空气机中.随着球的反弹，一些球从出口弹出.最先弹出的五个是中奖号码.这种设置称为“无放回抽样”，因为某个球一旦从出口弹出，它就不会出现在剩下的球中.在这种设置中，一张中奖彩票不能有重复的号码.然而，还有另一种游戏方法，抽取第一个球，将其放回空气机中，然后重复.这种设置称为“放回抽样”.在这种设置中，一张中奖彩票可以有重复的号码.

第二个问题，是否考虑顺序，与上一节中讨论的排列和组合的区别相同.在强力球游戏中，球以特定的顺序出现.然而，这个顺序不影响彩票是否中奖.这就是不考虑顺序的情况.如果游戏的规则不同，球的顺序可能会影响是否中奖.此时，应使用考虑顺序的计数方法.

现在描述四个抽样问题.我们想要计算从N个元素中抽取K个元素的可能结果数.例如，计算从集合{1,2,···,69}中抽取5个整数的可能结果数.

有序，放回（ordered，with replacement）考虑按顺序选择元素.第一个可以从N个元素中任选一个，第二个也可以从N个元素中任选一个，第三个还可以从N个元素中任选一个，等等.利用计数法则，可能的结果总数为

N×N×···×N=NK

在强力球彩票例子中，总数为

695=1564031359

这是一个非常大的数！

有序，无放回（ordered，without replacement）排列数为N！/（N-K）！.在强力球彩票例子中，总数为

这几乎与放回抽样的总数一样大.

无序，无放回（unordered，without replacement）组合数为N！/（K！（N-K）！）.在强力球彩票例子中，总数为

这尽管是一个很大的数，但比有序抽样的数小很多.

无序，放回（unordered，with replacement）这是个复杂的问题.结果不是NK（有序放回抽样数）除以K！，因为每组内的有序排列数依赖于组内是否有重复元素.诀窍在于把该问题表述为另一个问题.事实上，要计算的数与N个和为K的非负整数{x1,x2,···,xN}的组数相同.为证明这一点，一张彩票（无序且放回）可表示为选出“1”的数量x1，“2”的数量x2，“3”的数量x3等，且设其和x1+x2+···+xN必须等于K.根据经典的证明记号，该问题的答案有一个巧妙的名字.

定理1.12 星号和隔板定理（stars and bars theorem）[8].和为K的N个任意非负整数的总数等于.

由于该定理的证明相当冗长，故省略.该定理给出了我们一开始所提问题的答案，即放回条件下无序集的总数.在强力球彩票的例子中，总数为

表1-5总结了四种抽样结果.

实际的强力球游戏使用的是无序无放回抽样.因此，大约有1100万张可能的彩票.每张彩票出现的机会相同（如果随机抽取的过程是公平的），中奖的概率约为1/11000000.由于每出售1100万张彩票，有一个人赢得100万美元，因此预期赔率（忽略其他赔率）约为0.09美元.这是一个低赔率（大大低于“公平”的赌注，因为一张彩票售价2美元），但足以使一些人产生很大兴趣.