离散数学基础:排列组合计数问题
思维导图¶
¶
\[
P(n,r)=\frac{n!}{(n-r)!}
\]
\[
n个不同物体不允许重复地选r个物体的排列数
\]
\[
n元素的字符集上长度为r且不含重复字符的字符串数
\]
¶
\[
n^r
\]
\[
n类不同物体不允许重复地选r个物体的排列数
\]
\[
n元素的字符集上长度为r且可含重复字符的字符串数
\]
¶
\[
C(n,r)=\frac{n!}{r!(n-r)!}
\]
\[
n个不同物体不允许重复地选r个物体的组合数
\]
\[
将r个无区别的物体放到n个无区别的容器里
\]
\[
长度为n且有r个1(或0)的二进制串数
\]
\[
n元素集合的r元素子集的个数
\]
¶
\[
C(n-1+r,r)=\frac{(n-1+r)!}{r!(n-1)!}
\]
\[
n类不同物体允许重复地选r个物体的组合数
\]
\[
将r个无区别的物体放到n个可区别的容器里
\]
\[
\begin{aligned} &不定方程x_1 +x_2 +...+x_n =r\\
&的非负整数解的个数
\end{aligned}
\]
¶
\[
\begin{aligned} &\prod_{i=1}^{n}
\begin{pmatrix}r-\sum_{j=1}^{i-1}m_j\\m_i\end{pmatrix}\\
=&
\begin{pmatrix}r\\m_1\end{pmatrix}
\begin{pmatrix}r-m_1\\m_2\end{pmatrix}
...
\begin{pmatrix}r-m_1-m_2-...-m_{n-1}\\m_n\end{pmatrix}
\\
=&\frac{r!}{m_1!m_2!...m_3!}
\end{aligned}
\]
\[
\begin{aligned} &分别有m_1,m_2,...,m_n个的n类不同物体的\\
&m_1+m_2+...+m_n=r排列数
\end{aligned}
\]
\[
将r个无区别的物体放到n个可区别的容器里
\]
\[
\begin{aligned} &m_1+m_2+...+m_n=r个可区别的物体\\
&放到n个可区别的容器使第i个容器\\
&恰有m_i个物体的方法数
\end{aligned}
\]
¶
\[
\begin{aligned} &不定方程x_1 +x_2 +...+x_n =r的满足x_i\geq min_i的非负整数解个数等于\\
&不定方程(x_1-min_1)+(x_2-min_2)+...+(x_n-min_n)=r-
\sum_{i=1}^{n}min_i
\\
&即x_1 +x_2 +...+x_n =r-
\sum_{i=1}^{n}min_i
\\
&的非负整数解的个数
\end{aligned}
\]
¶
\[
\begin{aligned} &不定方程x_1 +x_2 +...+x_n =r的满足max_i\geq x_i\geq min_i的非负整数解个数:\\
&令U是不定方程x_1 +x_2 +...+x_n =r-
\sum_{i=1}^{n}min_i
的非负整数解构成的集合\\
&N=|U|，性质P_i表示x_i\geq max_i,N(P_i)等于U中满足性质P_i的元素个数\\
&所求解的个数=
N-N(\overline{P_1\cup P_2\cup...\cup P_n})
=N(\overline{P_1}\cap\overline{P_2}\cap...\cap\overline{P_n})\\
&利用容斥原理求解
\end{aligned}
\]