组合数学中的采样(Sample)问题 (一):基本概念和两种形式

前面的一系列帖子介绍了组合数学中的分配问题。另一个组合数学的基本模型是采样模型,很多排列组合问题都可以从这个模型开始思考。

采样问题有两种基本形式,第一种是可以重复采样的,比如所有长度为10个字母的英文单词,可以看做该单词的每个字母都从26个英文字母中挑选一个,这样的挑选重复10次。很明显,所有可能的单词总数是:

(1)   \begin{equation*} 26^{10} \end{equation*}

第二种是不能重复采样的,比如假定我们有 n 个人,需要从其中挑出 r 个样本。很明显第一个人有 n 种选择,第二个人就只有 n-1 中选择了。所有可能的样本总数是:

(2)   \begin{equation*} n \times (n-1) \times (n-2) \times ... \times (n-r+1) = P_n^r \end{equation*}