离散数学基础:排列组合计数问题 思维导图¶ ¶ P(n,r)=n!(n−r)! 个不同物体不允许重复地选个物体的排列数个不同物体不允许重复地选个物体的排列数n个不同物体不允许重复地选r个物体的排列数 元素的字符集上长度为且不含重复字符的字符串数元素的字符集上长度为且不含重复字符的字符串数n元素的字符集上长度为r且不含重复字符的字符串数 ¶ nr 类不同物体不允许重复地选个物体的排列数类不同物体不允许重复地选个物体的排列数n类不同物体不允许重复地选r个物体的排列数 元素的字符集上长度为且可含重复字符的字符串数元素的字符集上长度为且可含重复字符的字符串数n元素的字符集上长度为r且可含重复字符的字符串数 ¶ C(n,r)=n!r!(n−r)! 个不同物体不允许重复地选个物体的组合数个不同物体不允许重复地选个物体的组合数n个不同物体不允许重复地选r个物体的组合数 将个无区别的物体放到个无区别的容器里将个无区别的物体放到个无区别的容器里将r个无区别的物体放到n个无区别的容器里 长度为且有个或的二进制串数长度为且有个或的二进制串数长度为n且有r个1(或0)的二进制串数 元素集合的元素子集的个数元素集合的元素子集的个数n元素集合的r元素子集的个数 ¶ C(n−1+r,r)=(n−1+r)!r!(n−1)! 类不同物体允许重复地选个物体的组合数类不同物体允许重复地选个物体的组合数n类不同物体允许重复地选r个物体的组合数 将个无区别的物体放到个可区别的容器里将个无区别的物体放到个可区别的容器里将r个无区别的物体放到n个可区别的容器里 不定方程的非负整数解的个数不定方程的非负整数解的个数不定方程x1+x2+...+xn=r的非负整数解的个数 ¶ ∏i=1n(r−∑j=1i−1mjmi)=(rm1)(r−m1m2)...(r−m1−m2−...−mn−1mn)=r!m1!m2!...m3! 分别有个的类不同物体的排列数分别有个的类不同物体的排列数分别有m1,m2,...,mn个的n类不同物体的m1+m2+...+mn=r排列数 将个无区别的物体放到个可区别的容器里将个无区别的物体放到个可区别的容器里将r个无区别的物体放到n个可区别的容器里 个可区别的物体放到个可区别的容器使第个容器恰有个物体的方法数个可区别的物体放到个可区别的容器使第个容器恰有个物体的方法数m1+m2+...+mn=r个可区别的物体放到n个可区别的容器使第i个容器恰有mi个物体的方法数 ¶ 不定方程的满足的非负整数解个数等于不定方程即的非负整数解的个数不定方程的满足的非负整数解个数等于不定方程即的非负整数解的个数不定方程x1+x2+...+xn=r的满足xi≥mini的非负整数解个数等于不定方程(x1−min1)+(x2−min2)+...+(xn−minn)=r−∑i=1nmini即x1+x2+...+xn=r−∑i=1nmini的非负整数解的个数 ¶ 不定方程的满足的非负整数解个数令是不定方程的非负整数解构成的集合,性质表示等于中满足性质的元素个数所求解的个数利用容斥原理求解不定方程的满足的非负整数解个数令是不定方程的非负整数解构成的集合,性质表示等于中满足性质的元素个数所求解的个数利用容斥原理求解不定方程x1+x2+...+xn=r的满足maxi≥xi≥mini的非负整数解个数:令U是不定方程x1+x2+...+xn=r−∑i=1nmini的非负整数解构成的集合N=|U|,性质Pi表示xi≥maxi,N(Pi)等于U中满足性质Pi的元素个数所求解的个数=N−N(P1∪P2∪...∪Pn―)=N(P1―∩P2―∩...∩Pn―)利用容斥原理求解