现在的位置: 首页 > 综合 > 正文

广义组合(学习笔记)

2013年09月12日 ⁄ 综合 ⁄ 共 653字 ⁄ 字号 评论关闭


[定理] X为包含k个元素的集合,对X中元素进行不记顺序的n次复制,共有

C(n+k-1,k-1)种可能的结果。

注意是集合,元素是可区分的

换种不那么抽象的说法: 有k种颜色的小球,从中取n个小球, 可能的结果数

(每种颜色小球不加区分,个数极大:对任意n, 每种颜色小球的个数N>n)

教材上或许会出现这么一个难听的名字叫“隔板法”:在n+k-1个凳子中放k-1个“隔板”

(k-1个隔板可以把剩下的n个凳子分成k类, 每一类对应一种颜色)

上图中 k=3, n=6;  绿色对应隔板, 黄色对应小球..

[例]

设有一堆红色球、一堆蓝色球和一堆绿色球,每一堆都不少于8个。
(1) 从中抽出8个球,有多少种不同的抽法?
(2) 从中抽出8个球,要求每种颜色的球都得有,有多少种不同的抽法?
[解] (1) k=3,n=8,故方案数 C(8+3-1,3-1) = 45
(2)先将每种颜色的球拿一个出来后,问题转化为
(1)的情况,此时k=3,n=5,故方案数 C(5+3-1,3-1) = 21

[例] 设有整数域上的方程:x1 + x2 + x3 + x4 = 29 ,问:
(1) 该方程有多少非负整数解?
(2) 该方程有多少满足 x1>0, x2>1, x3>2, x4

>=0 的整数解?

[解] (1) 方程的每一个非负整数解相当于从4个元素中复制29个 的一个方案,其中从第i个元素中复制的个数为 xi ,i =1..4。故方案数 C(29+4-1,4-1) = 4960
(2) 第1个元素至少选1个,第2个元素至少选2个,第3个元素至少选3个,剩下的23个可任意选择。故方案数为 C(23+4-1,4-1) = 2600

抱歉!评论已关闭.