文章目录

一、排列组合内容概要二、选取问题三、集合排列四、环排列五、集合组合

参考博客 :

【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )

一、排列组合内容概要

排列组合内容概要 :

选取问题集合的排列与组合问题基本计数公式应用多重集的排列与组合问题

二、选取问题

n

n

n 元集

S

S

S , 从

S

S

S 集合中选取

r

r

r 个元素 ;

根据 元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :

元素不重复元素可以重复有序选取集合排列

P

(

n

,

r

)

P(n,r)

P(n,r)多重集排列无序选取集合组合

C

(

n

,

r

)

C(n,r)

C(n,r)多重集组合

选取问题中 :

不可重复的元素 , 有序的选取 , 对应 集合的排列不可重复的元素 , 无序的选取 , 对应 集合的组合可重复的元素 , 有序的选取 , 对应 多重集的排列可重复的元素 , 无序的选取 , 对应 多重集的组合

三、集合排列

n

n

n 元集

S

S

S , 从

S

S

S 集合中 有序 , 不重复 选取

r

r

r 个元素 ,

该操作称为

S

S

S 集合的一个

r

−

r-

r− 排列 ,

S

S

S 集合的

r

−

r-

r− 排列记作

P

(

n

,

r

)

P(n, r)

P(n,r)

P

(

n

,

r

)

=

{

n

!

(

n

−

r

)

!

n

≥

r

0

n

<

r

P(n,r)=\begin{cases} \dfrac{n!}{(n-r)!} & n \geq r \\\\ 0 & n < r \end{cases}

P(n,r)=⎩⎪⎪⎨⎪⎪⎧​(n−r)!n!​0​n≥rn

该排列公式使用乘法法则得到 : 将整个排列看做

r

r

r 个位置

第

1

1

1 个位置有

n

n

n 种放置方法 , 即从当前的

n

n

n 个元素中任选一个 , 剩下

n

−

1

n-1

n−1 个元素 ;第

2

2

2 个位置有

n

−

1

n-1

n−1 种放置方法 , 即从当前的

n

−

1

n-1

n−1 个元素中任选一个 , 剩下

n

−

2

n-2

n−2 个元素 ;第

3

3

3 个位置有

n

−

2

n-2

n−2 种放置方法 , 即从当前的

n

−

2

n-2

n−2 个元素中任选一个 , 剩下

n

−

3

n-3

n−3 个元素 ;

⋮

\vdots

⋮

第

r

r

r 个位置有

n

−

(

r

−

1

)

=

n

−

r

+

1

n-(r-1) = n - r + 1

n−(r−1)=n−r+1 种放置方法 , 即从当前的

n

−

r

+

1

n - r + 1

n−r+1 个元素中任选一个 , 剩下

n

−

r

n-r

n−r 个元素 ;

0

!

=

1

0! = 1

0!=1

四、环排列

n

n

n 元集

S

S

S , 从

S

S

S 集合中 有序 , 不重复 选取

r

r

r 个元素 ,

S

S

S 集合的

r

−

r-

r− 环排列数

=

P

(

n

,

r

)

r

=

n

!

r

(

n

−

r

)

!

= \dfrac{P(n,r)}{r} = \dfrac{n!}{r (n-r)!}

=rP(n,r)​=r(n−r)!n!​

r

r

r 个不同的线性排列 , 相当于同一个环排列 ;

一个环排列 , 从任意位置剪开 , 可以构成

r

r

r 种不同的线性排列 ;

五、集合组合

n

n

n 元集

S

S

S , 从

S

S

S 集合中 无序 , 不重复 选取

r

r

r 个元素 ,

该操作称为

S

S

S 集合的一个

r

−

r-

r− 组合 ,

S

S

S 集合的

r

−

r-

r− 组合记作

C

(

n

,

r

)

C(n, r)

C(n,r)

C

(

n

,

r

)

=

{

P

(

n

,

r

)

r

!

=

n

!

r

!

(

n

−

r

)

!

n

≥

r

0

n

<

r

C(n,r)=\begin{cases} \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!} & n \geq r \\\\ 0 & n < r \end{cases}

C(n,r)=⎩⎪⎪⎨⎪⎪⎧​r!P(n,r)​=r!(n−r)!n!​0​n≥rn

r

−

r-

r− 排列也可以这样理解 ( 先组合后排列 ) : 选出

r

r

r 个有序的排列

C

(

n

,

r

)

C(n,r)

C(n,r) , 可以先将其

r

r

r 个无序的选择做出来 , 然后再对选择好的元素进行全排列

C

(

n

,

r

)

r

!

=

P

(

n

,

r

)

C(n,r) r! = P(n,r)

C(n,r)r!=P(n,r) ;

组合恒等式 :

C

(

n

,

r

)

=

C

(

n

,

n

−

r

)

C(n,r) = C(n, n-r)

C(n,r)=C(n,n−r)