10.2 排列与组合
本章目录 · 1 节
本章导读
【四种基本选择模型】先分清是否计较顺序、是否允许重复:不重复而有序是集合排列;不重复而无序是集合组合;有可重复元素时使用多重集的排列、组合。只有所需库存足够时,才可把有限多重集当成无限重复来选。
【定义10.2.1与定理10.2.1】从n元集选 个不同元素并排顺序,称r排列,记 ;只选出集合而不排顺序,称r组合,记 。约定 ,当 时
当 时两者均为0, 时均为1。排列各步可选数为 ,相乘得到前式;每个r组合有 种内部排列,所以 ,得到后式。 时为全排列,共 。
【推论10.2.1:环排列】 个不同元素首尾相接,若旋转视作相同而镜像通常仍视为不同,则r环排列数为 。每个环对应r种选择起点的线排列,故除以r;不能在 时仍除以0,也不能未约定镜像等价就再除以2。
【推论10.2.2:三个基本恒等式】在对应的非负整数范围内有
越界的非负上项组合数取0。第二式由取补集一一对应;第三式把r子集按是否含一个指定元素分类,分别有 与 种。它就是Pascal递推,构成杨辉三角:
例如 ,可借对称性简化计算。
【定义10.2.2:多重集】 有k类不同元素, 为第i类的重复度,可为足够使用的无穷库存。子多重集由 决定。有限总数为 ;同类副本不再当作可区分个体。
【定理10.2.2:多重集排列】有限多重集全排列数为 。可依次选择各类所占位置,得到 ,约去后即为该式。若每类库存均至少r,则长r有序串每位置有k种,数目为 ;条件是 对每一类都成立,不只是 。
【定理10.2.3:多重集组合】k类元素库存均至少r, 时,无序选r个对应方程 的非负整数解,数目为
证明把r颗星与 条隔板排成一行,各段星数就是各 。隔板可相邻或位于两端,表示某类选0个。若有限库存会被超过,须加 的约束,不能直接套这个无限库存式。多重集全排列系数也称多项式系数,10.4将继续讨论。
【例10.2.1】26个不同字母全排列,a、b之间恰有7个其他字母,求方法数。
【解】先定a、b的先后,有2种;从其余24字母有序选7个放在中间,有 种;这9个字母组成一块,与剩余17字母共18个对象全排列,故 。另一验证是两个端点位置相差8,左端有18个位置,方向2种,剩余24字母任排,仍为 。
【例10.2.2】把2n名不同的人分成n个无标号二人组。
【解】先给全部人排序,共 ;相邻每两人一组,每组内部次序重复2次,共除以 ;n个组之间无序,再除以 。答案为 ,也等于先依次选两人的乘积 再除以 。若组已有不同编号,就不再除这个 。
【例10.2.3】k重循环的指标满足 ,初始计数0,每次最内层加1,输出多少?
【解】设 。每次执行对应一个非增k元组,等价于从1至n无序可重复选k个元素,故输出 。指标允许相等,不能错按严格递增元组得到 。
【例10.2.4】从1至n中选k个两两不相邻的数。
【解】按递增顺序记为 ,要求 。令 ,则 ,反向 唯一恢复,所以答案为 。 时为空选集一种; 时无解,记0,不把负的上项代入普通阶乘公式。
