排列组合入门提高篇
初日辉煌
·
·
个人记录
排列组合入门提高篇
---
##### $\space\space\space\space$ $Example\_1.$ $x_1,x_2,x_3\in\mathbb N_+,x_1+x_2+x_3=24$有多少组解？
$\space\space\space\space$我们把这个问题转换到实际生活中$\Longrightarrow$把$24$个石子划分为$3$堆，有多少种分法？
$\space\space\space\space$当然我相信没人会老老实实的一个一个去分，正常做法是把$24$个石子摆成一列，其中有$23$个空档，划两条分界线就是了。
$\space\space\space\space$一共$23$个，不能重复的选两个空档出来，很明显是$C_{23}^2$嘛。
$\space\space\space\space$这样下去我们可以得到一个一般规律：
$\space\space\space\space$ $x_1,x_2,\ldots,x_n\in\mathbb N_+,\sum_{i=1}^nx_i=k(k$为常数，且$k\geq n)$，这个不定方程解的个数为$C_{k-1}^{n-1}$。
$\space\space\space\space$这样下来我们又可以推出一个新东西：求不定方程$\sum_{i=1}^nx_i=k(k$为常数$),k,x_1,x_2,\ldots,x_n\in\mathbb N$的解的个数。
$\space\space\space\space$这个问题有两种解法，第一种是转化为上面的问题：$(x_1+1)+(x_2+1)+\ldots+(x_n+1)=k+n\Longleftrightarrow \sum_{i=1}^n(x_i+1)=k+n
\space\space\space\space$ $\Longrightarrow\sum_{i=1}^ny_i=k+n
\space\space\space\space$这时每个$y_i$都$\in\mathbb N_+
\space\space\space\space$所以解的个数为$C_{n+k-1}^{n-1}