组合数学2
例8.9
从1，2，...，300之中任取3个数。它们的和能被3整除,问有多少种方法?
解 把1,2,...,300分成A、B、C3个组。
A={x | x `-=` 1 (mod 3) },
B={x | x `-=` 2 (mod 3) },
C={x | x `-=` 0 (mod 3) }.
设任取3个数i、j、k，那么选取是无序的且满足i+j+k `-=` 0 (mod 3).将选法分成两类：
i、j、k都取自同一组，方法数`N_1`=3`C_100^3`;
i、j、k分别取自A、B、C，方法数`N_2`=`(C_100^1)^3`.由加法法则,总取法数
N=3`C_100^3`+`(C_100^1)^3`= 1485100.
定理8.4
设S为n元集，则S的子集总数是
`2^n`= `C_n^0`+ `C_n^1`+ ... +`C_n^n`
证明
对于r=0,1,...,n, S的每个r子集就是S的一个r组合。而`C_n^r`就是S的r子集数。由加法法则，S的子集数是
`C_n^0` + `C_n^1`+ ...+ `C_n^n`
另一方面，在构成S的某个子集时可以对每个元素有两种选择，属于该子集或不属于该子集。根据乘法法则，n个元素的选法数是`2^n`,即S的子集数为`2^n`
定理8.5
设多重集S={`oo * a_1`,`oo * a_2`, ... ,`oo * a_k`},则S的r排列数是`k^r`。
证明 在构造S的一个r排列时,第1位有k种选法，第2位也有k种选法，..., 第r位仍然有r种选法，这是因为S中的每种元素都可以无限重复选取。排列中每一位的选择都不依赖于以前各位的选择，由乘法法则不同的选法数是`k^r`
定理8.6 设多重集，S={`n_1 * a_1 ` ,`n_1 * a_1 ` , ... , `n_1 * a_1 `} 且n=`n_1` + `n_2` + ... + ,`n_k` ,则S的排列数等于
`(n!) / (n_1! n_2! ... n_k!)`
证明 S的一个排列就是n个元素的全排列，因为S中有`n_1`个`a_1`,在排列中要占据`n_1`个位置，这些位置的选法是`C_n^(n_1)`种。接下去，在剩下的`n - n_1`个位置中选择`n_2`个放`a_2`,选法数是`C_(n-n_1)^(n_2)`.类似地，有C_(n-n_1-n_2)^(n_3) 种方法放`a_3`, ... ,有C_(n-n_1-...-n_(k-1))^(n_k)种方法放`a_k`.由乘法法则，S的排列数
N=`C_n^(n_1)` `C_(n-n_1)^(n_2)` ... `C_(n_n_10...n_k-1)^(n_k)`
=`(n!)/(n_1!(n-n_1)!)` `((n-n_1)!) / ((n_2!)(n-n_1-n_2)! ` ... `((n-n_1- ... - n_(k-1))!) / (n_k! * 0!)`
=`(n!) / (n_1! n_2! ... n_k!)`
关于多重集的排列问题可以小结如下:
设S={`n_1 * a_1` , `n_2 * a_2` , ... , `n_k * a_k`},n=`n_1` + `n_2` + ... + `n_k`,则S的r排列数N满足
(1) 若r>n,则N=0
(2)若r=n,则N=`(n!) / (n_1! n_2! ... n_k!)`，
(3)若r
(4)若r`<`n且存在着某个`n_i <r`,则对n没有一般的求解公式，可以使用其他的组合数学方法解决。
定理8.7
设多重集S={`oo * a_1`,`oo * a_2`, ... ,`oo * a_k`},则S的r组合数是`C_(k+r-1)^r`
证明 S的任何一个r组合都具有如下性质:
{`x_1 * a_1`,`x_2 * a_2`, ... ,`x_k * a_k`} ,
其中`x_1`,`x_2`, ... ,`x_k`是非负整数且满足方程
x_1 + x_2 + ... + x_k = r
反之，对于每一组满足上述方程的非负整数解`x_1`,`x_2`，... ,`x_k` , {`x_1 * a_1` ,`x_2 * a_2` , ... ,`x_k * a_k` }就是S的一个r组合，所以多重集S的r组合数等于上述方程的非负整数解的个数。下面将证明这种解的个数等于多重集T={(k-1) * 0, r* 1}的排列数。
给定T的一个排列，在这个排列中k-1个0把r个1分成k组。从左边数,第1组1的个数记为`x_1`，第2组1的个数记作`x_2`, ... ,第k组1的个数记作x_k，则所得到的`x_1`,`x_2`, ... ,`x_k`都是非负整数，并且其和等于的。反之，给定方程`x_1` + `x_2` + ... +`x_k` = r 的一组非负整数解`x_1`,`x_2`, ... ,`x_k` ,可以如下构造排列：
它就是多重集T的一个排列。根据地理8.6 ,T的排列数
N=`((k-1+r)!) / ((k-1)!r!)` = `C_(k+r-1)^r`
推论2 设多重集S={ `oo * a_1` ,`oo * a_2` , ... ,`oo * a_k` }, r`>=`k ,则S中每个元素至少取一个的r组合数是`C_(r-1)^(k-1)`。
证明 任取一个所求的r组合，从中拿走元素`a_1`,`a_2`, ... , `a_k`, 就得到S的一个(r-k)组合。反之,任取一个S的(r-k)组合, 加入元素`a_1`,`a_2`, ... , `a_k`。就得到所求的组合。所以,S中每个元素至少取一个的r组合数就是S的(r-k)组合数。由定理8.7有
N=`C_(k+(r-k)-1)^(r-k)`=`C_(r-1)^(r-k)`=`C_(r-1)^(k-1)`
设多重集S={`n_1 * a_1` ,`n_2 * a_2` , ... , `n_k * a_k` }, n= `n_1` + `n_2` + ... +`n_k` ,则S的r组合数N满足:
(1)若r>n ,则N=0.
(2)若r=n，则N=1.
(3)若r`<`n,且对一切i=1,2,...,k 有`n_i < r`,则有`n_i >= r`,则N=`C_(k+r-1)^r).
(4)若r`<`n,且存在某个`n_i <="" r="" `,则对n没有一般的求解公式，可以用包含排斥原理或其他的组合数学方法求解。