排列组合公式 1

排列组合公式

1．分类计数原理（加法原理）

N =m 1+m 2+ +m n .

2．分步计数原理（乘法原理）

N =m 1⨯m 2⨯ ⨯m n .

3．排列数公式

n ！

m A n ！=n (n -1) (n -m +1) =(n -m ) .(n ，m ∈N*，且m ≤n ) ．

注:规定0! =1. 4．排列恒等式

m m -1

A =(n -m +1) A n n (1);

(2)

m A n =

n m

A n -1

n -m ;

m m -1

A =nA n n -1; (3)

n n +1n nA =A -A n n +1n (4); m m m -1A =A +mA n +1n n (5).

(6) 1! +2⋅2! +3⋅3! + +n ⋅n ! =(n +1)! -1. 5．组合数公式

A n m n (n -1) (n -m +1) n ！m m C n A ⋅(n -m ) ！1⨯2⨯ ⨯m m ===m ！(n ∈N*，m ∈N ，且m ≤n ).

6．组合数的两个性质

m n -m

C C n n (1)= ; m m -1m C C C n n n (2) +=+1. 0

C =1. n 注:规定

7．组合恒等式

m

C n =

(1)

n -m +1m -1

C n

m ;

(2)

m C n =

n m

C n -1

n -m ; n m -1

C n -1m ;

r n

(3)

m C n =

(4)r =0

∑C

n

=2;

n

r r r r r +1C +C +C + +C =C r r +1r +2n n +1. (5)

012r n n C +C +C + +C + +C =2n n n n n (6). 135024n -1C +C +C + =C +C +C + 2n n n n n n (7). 123n n -1C +2C +3C + +nC =n 2n n n n (8). r 0r -110r r r C C +C C + +C C =C m n m n m n m +n . (9)

021222n 2n (C ) +(C ) +(C ) + +(C ) =C n n n 2n . (10)n

8．排列数与组合数的关系

m m

A n =m ！⋅C n

.

9．单条件排列

以下各条的大前提是从n 个元素中取m 个元素的排列. （1）“在位”与“不在位”

m -1A n ①某（特）元必在某位有-1种；

m m -11m -1

A -A =A A n n -1n -1n -1（着眼位置）②某（特）元不在某位有（补集思想）m 1m -1

=A n +A A -1m -1n -1（着眼元素）种.

（2）紧贴与插空（即相邻与不相邻）

A A ①定位紧贴：k (k ≤m ≤n ) 个元在固定位的排列有k n -k 种.

A A ②浮动紧贴：n 个元素的全排列把k 个元排在一起的排法有n -k +1k 种.

注：此类问题常用捆绑法；

③插空：两组元素分别有k 、h 个（k ≤h +1），把它们合在一起来作全排列，k 个的

h k

A A h +1种. h 一组互不能挨近的所有排列数有

n -k +1

k

k m -k

（3）两组元素各相同的插空

m 个大球n 个小球排成一列，小球必分开，问有多少种排法？

n A m n +1

=C m +1n A n >m +1n ≤m +1当时，无解；当时，有n 种排法.

n

C m （4）两组相同元素的排列：两组元素有m 个和n 个，各组元素分别相同的排列数为+n .

10．分配问题

（1）(平均分组有归属问题) 将相异的m 、n 个物件等分给m 个人，各得n 件，其分配方

n n n n n

N =C mn ⋅C mn -n ⋅C mn -2n ⋅ ⋅C 2n ⋅C n =

法数共有

(mn )!

(n ! ) m .

（2）(平均分组无归属问题) 将相异的m ·n 个物体等分为无记号或无顺序的m 堆，其

分配方法数共有

n n n n n C mn ⋅C mn ⋅C ... ⋅C ⋅C (mn )! -n mn -2n 2n n

N ==

m ! m ! (n ! ) m .

（3）(非平均分组有归属问题) 将相异的

须被分完，分别得到

P(P=n1+n2+ +nm ) 个物体分给m 个人，

物件必

n 1，n 2，…，n m 件，且n 1，n 2，…，n m 这m 个数彼此不相

n m n 1n 2

N =C p ⋅C p C n ⋅m ! =-n 1... m

等，则其分配方法数共有

p ! m !

n 1! n 2!... n m ! .

（4）(非完全平均分组有归属问题) 将相异的

件必须被分完，分别得到

P(P=n1+n2+ +nm ) 个物体分给m 个人，物

n 1，n 2，…，n m 件，且n 1，n 2，…，n m 这m 个数中分别

N =

n m n 1n 2

C p ⋅C p C n ⋅m ! -n 1... m

有a 、b 、c 、…个相等，则其分配方法数有

a ! b ! c !...

=

p ! m !

n 1! n 2!... n m !(a ! b ! c !...) .

（5）(非平均分组无归属问题) 将相异的

P(P=n +n1+n2+m ) 个物体分为任意的n 1，

n 2，…，n m 件无记号的m 堆，且n 1，n 2，…，n m 这m 个数彼此不相等，则其分

N =

配方法数有

p !

n 1! n 2!... n m ! .

（6）(非完全平均分组无归属问题) 将相异的

P(P=n1+n2+ +nm ) 个物体分为任意的n 1，

n 2，…，n m 件无记号的m 堆，且n 1，n 2，…，n m 这m 个数中分别有a 、b 、c 、…

N =

个相等，则其分配方法数有

p !

n 1! n 2!... n m ! (a ! b ! c !...) .

p =n 1+n 2+ +n m ）

（7）(限定分组有归属问题) 将相异的p （个物体分给甲、乙、丙，……

等m 个人，物体必须被分完，如果指定甲得则无论

n 1件，乙得n 2件，丙得n 3件，…时，

n 1，n 2，…，n m 等m 个数是否全相异或不全相异其分配方法数恒有

p !

n 1! n 2!... n m ! .

n m n 1n 2

N =C p ⋅C p C n =-n 1... m

11．“错位问题”及其推广

贝努利装错笺问题:信n 封信与n 个信封全部错位的组合数为

f (n ) =n ![

1111-+- +(-1) n ]2! 3! 4! n ! .

推广: n 个元素与n 个位置, 其中至少有m 个元素错位的不同组合总数为

1234

f (n , m ) =n ! -C m (n -1)! +C m (n -2)! -C m (n -3)! +C m (n -4)!

p m

- +(-1) p C m (n -p )! + +(-1) m C m (n -m )!

1234p m C m C m C m C m p C m m C m

=n ![1-1+2-2+4- +(-1) p + +(-1) m ]

A n A n A n A n A n A n .

12．不定方程

x 1+x 2+ +x n =m 的解的个数

n -1

*

C x +x + +x =m n , m ∈N 12n (1)方程（）的正整数解有m -1个.

1*

C n n +-x +x + +x =m n , m ∈N 12n m -1个. (2) 方程（）的非负整数解有

*

x +x + +x =m x ≥k (k ∈N *, 2≤i ≤n -1) 的非负n , m ∈N 12n (3) 方程（）满足条件i

整数解有

n -1

C m

+1-(n -2)(k -1)

个.

*

x +x + +x =m x ≤k (k ∈N *, 2≤i ≤n -1) 的正整n , m ∈N 12n (4) 方程（）满足条件i

数解有

11n -12n -1n -2n -2n -1

C n n +--C C +C C - +(-1) C n -2C m +1-(n -2) k

m -1n -2m +n -k -2n -2m +n -2k -3

个.

n 0n 1n -12n -22r n -r r n n (a +b ) =C a +C a b +C a b + +C a b + +C n n n n n b ; 13．二项式定理

二项展开式的通项公式

r n -r r

T r +1=C n a b (r =0，1，2 ，n ) .