中山大学2013组合数学与数论复习

  • 格式:doc
  • 大小:27.00 KB
  • 文档页数:1

一、排列组合
⎪⎪
⎪⎪
⎪⎪⎩
⎪⎪⎪⎪⎪⎪⎨⎧⎪⎪⎩⎪⎪
⎨⎧⎪⎩⎪⎨⎧++++++++=-=⎪

⎩⎪

⎨⎧⎪⎪⎩⎪
⎪⎨⎧==
=
-=∏∏∑∑

=-+==≤≤≤≤=+++≤≤≤≤=+++-----m
k n n m n n n m n m m k i n i
m
k t n
t t t m
k t n t t t m t t t n t t n t n
m m n
n
m x x x
x x x x x C n m n m C n x i x t t t n C
C
C x P m n m m P n m k k
k k m k k m m
m 1
2
21101,01,02121)1(6)1(4)
)!(!/(!2!!
!!!!);,,,(53)!
/(!121211
121
1的系数
中)
(有限可重复组合的系数
中)(无限可重复组合可重复组合)(无重复组合组合倍
系数的中)(有限可重复排列)(无限可重复排列可重复排列)(无重复排列排列选λλλλλλλ m n m n
j m
j n j
m
n k n C j C m n m S Stirling m m m C 1
212121)
1(!
)1(),(/))!(!!!!/(!),,,;(-+=∑--=
-----=无限可重复有序分组
数第二类组合无重复无序分组无重复有序分组λλλλλλλλλ
二、鸽笼原理 1、n 个笼子n +1只鸽子,至少存在一个笼子至少装2只鸽子。

2、n 个笼子N ≧n +1只鸽子,至少存在一个笼子至少装2只鸽子。

3、n 个笼子m 只鸽子,至少存在一个笼子至少装11+⎥⎦


⎣⎡-n m 只鸽子。

4、n 个笼子(m-1)n+1只鸽子,至少存在一个笼子至少装m 只鸽子。

5、n 个笼子至少m 1+m 2+…+m n +1-n 只鸽子,至少存在一个笼子至少装m k 只鸽子。

三、递推关系 k 阶常系数线性齐次递推关系,特征根,特征方程
两类Stirling 数、Catlan 数的概念
四、整除理论: GCD 求法与组合系数,求逆 五、同余式
同余的本质(等价)含义 六、不定方程: 一次不定方程有解的充要条件 欧拉定理和费尔马定理
二元一次方程的解法 线性同余方程(组)有解的充要条件和解法
多元一次方程的解法
二次同余的概念(模素数的Legendre 符号及其应用)。