Skip to content

组合数学

2021-08-21

INFO

若无特殊说明,本章涉及的变量皆为正整数。

简介

  • 排列:从 n 个元素中取出 m 个,按一定顺序排列;
  • 组合:从 n 个元素中取出 m 个,不计排列顺序。

加法原理

一算法有 n 种方式,第 i 种方式有 ai 种方法,该算法共有 i=1nai 种实现方法。

EXAMPLE

A 地到 B 地有爬行、骑车、飞行三种方式,可以任选一个。而爬行、骑车、飞行分别有 a1,a2,a3 种方法,那么 AB 共有 a1+a2+a3 种方法。

乘法原理

一算法有 n 个步骤,第 i 个步骤有 ai 种方法,该算法共有 i=1nai 种实现方法。

EXAMPLE

A 地到 B 地必须先爬行到车站,再骑车到机场,最后飞行到北京,而爬行、骑车、飞行分别有 a1,a2,a3 种方法,那么 AB 共有 a1a2a3 种方法。

排列数

n 个元素中取出 m 个,按一定顺序排列的方案数,用符号 Anm 表示。

Anm=n(n1)(n2)(nm+1)=n!(nm)!

n=m 时的排列称为全排列,Ann=n!

组合数

n 个元素中取出 m 个,不计排列顺序的方案数,用符号 Cnm(nm) 表示。

(nm)=Anmm!=n!m!(nm)!

特别地,当 m>n 时,Anm=Cnm=0

互补性

(nm)=(nnm)
(nnm)=n!(nm)![n(nm)]!=n!(nm)!m!=(nm)

帕斯卡法则

(nm)=(n1m)+(n1m1)
(n1m)=(n1)!m!(nm1)!=1m(n1)!(m1)!(nm1)!(n1m1)=(n1)!(m1)!(nm)!=1nm(n1)!(m1)!(nm1)!(n1m)+(n1m1)=(1m+1nm)(n1)!(m1)!(nm1)!=nm(nm)(n1)!(m1)!(nm1)!=n!m!(nm)!=(nm)