老师勾选的题

第一章 排列组合

$n=7^3\times 11^2\times 13^4$,求除尽$n$的整数个数

显然能除尽$n$的整数个数是

$7^{l_1}\times 11^{l_2}\times 13^{l_3},0\le l_1\le 3,0\le l_2\le 2,0\le l_3\le 4$

数目为$4\times 3\times 5=60$

---

有男运动7名，女运动3名，列队进场，若要求头尾两名运动员必须是男运动员，且女运动员不相邻，问多少种排列方案？

$7!\times 6\times 5\times 4$

若女运动员排在一起，排在队的头尾两端，又有多少种方案？

$2\times 3!\times 7!$

只要女运动员排在一起又有多少种方案

$7!\times 6\times 6$

---

5个女生，7个男生组成一个含5个人的小组，要求该小组不允许男生和女生某乙同时参数，请问有多少种方案？？

$C^5_{12}=\frac{12\times 11\times 10\times 9\times 8}{1\times 2\times 3\times 4\times 5}=792$

$C^3_{10}=\frac{10\times 9\times 8}{1\times 2\times 3}=120$

$792-120=672$

---

红，黄，蓝，绿4种颜色的旗帜各4面，共16面排成一列，问有多少种不同的方案？？

$\frac{16!}{(4!)^4}$

---

n对夫妻围一圆桌而坐，求每对夫妻相邻而坐的方案数

$(n-1)!\times 2^n$

---

有12个人分两桌，每桌6人，围成圆桌而坐。有几种方案数，若有12对夫妻平分为两桌，围圆桌有几种方案？

$C(12,6)(5!)^2$

第二问

$C(12,6)(5! 2^6)^2$

---

线性方程$x_1+x_2+\cdots+x_n=b$的非负整数解的个数为$C(n+b-1,b)$

从$A=\{1,2,\cdots,n\}$中取$r$个作不相邻的组合，其组合数为$C(n-r+1,r)$

从$n$个不同元素中取$r$个作允许重复分组合，其组合数为$C(n+r-1,r)$

---

$\begin{pmatrix}n\\ l\end{pmatrix}\begin{pmatrix}l \\ r\end{pmatrix}=\begin{pmatrix}n\\ r \end{pmatrix}\begin{pmatrix} n-r \\ l-r\end{pmatrix}$

另一个证明

$$\begin{pmatrix}m+n \\ r\end{pmatrix}=\begin{pmatrix}m \\ 0 \end{pmatrix}\begin{pmatrix}n \\ r\end{pmatrix} +\begin{pmatrix}m\\ 1\end{pmatrix}\begin{pmatrix}n\\ r-1\end{pmatrix}+\cdots +\begin{pmatrix}m \\ r\end{pmatrix}\begin{pmatrix}n \\ 0\end{pmatrix}$$

另一个证明

$$\begin{pmatrix}r \\ r\end{pmatrix}+\begin{pmatrix}r+1 \\r \end{pmatrix}+\cdots+\begin{pmatrix}n \\ r\end{pmatrix}=\begin{pmatrix}n+1\\ r+1\end{pmatrix}$$

第二章 母函数

Fibonacci数列递推关系

$F_n=F_{n-1}+F_{n-2},F_1=F_2=1$，所对应的特征方程$x^2-x-1=0$

其中

$$F_n=F_0+F_1x+F_2x^2+F_3x^3+\cdots \\ xF_n=F_0x+F_1x^2+F_2x^3+F_3x^4+\cdots \\ x^2F_n=F_)x^2+F_1x^3+F^2x^4+F_3x^5+\cdots+ \\ F(x)(x^2+x-1)=(F_0-F_1)x-F_0+(F_0+F_1-F_2)x^2+(F_1+F_2-F_3)x^3+\cdots \\ F(x)(x^2+x-1)=-x \\ F(x)=\frac{x}{1-x-x^2}$$

所以

$$G(x)=\frac{P(x)}{1-x-x^2}=\frac{P(x)}{(1-\frac{1+\sqrt{5}}{2}x)(1-\frac{1-\sqrt{5}}{2}x)} =\frac{A}{1-\alpha x}+\frac{B}{1-\beta x} \\ \alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$$

例子2-10

$$a_n-a_{n-1}-12a_{n-2}=0,a_0=3,a_1=26 \\ G(x)=\frac{P(x)}{1-x-12x^2}=\frac{P(x)}{(1-4x)(1+3x)}$$

---

线性常系数非齐次递推关系

$$a_n-a_{n-1}-6a_{n-2}=5\cdot 4^n,a_0=5,a_1=3 \\ G(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+ \\ xG(x)=a_0x+a_1x^2+a_2x^3+\cdots+ \\ 6x^2G(x)=6a_0x^2+6a_1x^3+6a_2x^4+6a_3x^5+\cdots \\ G(x)(1-x-6x^2)=a_0+(a_1-a_0)x+(a_2-a_1-6a_0)x^2+(a_3-a_2-6a_1)x^3+\cdots \\ G(x)(1-x-6x^2)=-2x+5+5\cdot\frac{4^2x^2}{1-4x} \\ =\frac{5-22x+88x^2}{(1-3x)(1+2x)(1-4x)} \\ =\frac{A}{1+2x}+\frac{B}{1-3x}+\frac{C}{1-4x}$$

---

整数拆分成1,2,3，m的和，并且允许重复，求其母函数

$$G(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^m+x^{2m}+\cdots) \\ =\frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}$$

设1,2,4,8,16,32克的砝码各一枚，问你能称出那些重量

$$G(x)=(1+x)(1+x^2)(1+x^4)(1+x^8)(1+x^{16})(1+x^{32}) \\ =\frac{1-x^2}{1-x}\cdot \frac{1-x^4}{1-x^2}\cdot \frac{1-x^8}{1-x^4}\cdots \frac{1-x^{32}}{1-x^{16}}\frac{1-x^{64}}{1-x^{32}} \\ =\frac{1-x^{64}}{1-x} \\ =1+x+x^2+x^3+\cdots+x^{63}$$

n拆分成重复数不超过2的数之和的拆分数，等于拆分成不被3除尽的数之和的拆分书

$$G(x)=(1+x+x^2)(1+x^2+x^4)(1+x^3+x^6)\cdots \\ =\frac{(1-x)(1+x+x^2)}{1-x}\cdot\frac{(1-x^2)(1+x^2+x^4)}{1-x^2}\cdot \frac{(1-x^3)(1+x^3+x^6)}{1-x^3}\cdots \\ =\frac{1-x^3}{1-x}\cdot\frac{1-x^6}{1-x^2}\cdot\frac{1-x^9}{1-x^3}\cdot\frac{1-x^{12}}{1-x^4} \\ =\prod_{k=1}^\infty(\frac{1}{1-x^k})$$

---

n条直线将平面分成多少个域？假定无三线共点，且两两相交

$$D_n=1+\frac{1}{2}n(n+1)$$

设$n$条椭圆曲线，两两相交与两点，任意3条椭圆曲线不相交于一点，试问这样子的$n$个椭圆将平面分隔成多少个部分？？

$$a_n=a_{n-1}+2(n-1) \\ \to a_n=n(n-1)+2$$

---

定理

第2类司特林满足下面的递推式

$S(n,m)$的组合意义：将n个有标志的球放入m个无区别的盒子，而且无一空盒的方案数

$$S(n,m)=mS(n-1,m)+S(n-1,m-1)$$

卡特兰数

$$C_{n+1}=C_2C_n+C_3C_{n-1}+\cdots+C_{n-1}C_3+C_nC_2 \\ (n-3)C_n=\frac{n}{2}(C_3C_{n-1}+C_4C_{n-2}+\cdots+C_{n-2}C_4+C_{n-1}C_3)$$

第三章 容斥原理和鸽巢原理

求$a,b,c,d,e,f$这6个字符构成的全排列中不允许出现$ace$和$df$的排列数

求不超过120的素数个数

---

错排问题

即$1,2,\cdots,n$的全排列中每个元素都不在各位置上的排列数

设$A_i$表示数$i$仍在第$i$位的全排列

$$D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+\pm \frac{1}{n!})$$

---

求整数解的个数

$$x_1+x_2+x_3=15 \\ 0\le x_1\le 5,0\le x_2\le 6,0\le x_3\le 7$$

解：

设$A_1$为$x_1\ge 6$的解，$y_1+6+x_2+x_3=15$

$|A_1|=C(9+3-1,9)=C(11,2)$

设$A_2$为$x_2\ge 7$的解，$x_1+y_2+7+x_3=15$

$|A_2|=C(8+3-1,8)=C(10,2)$

设$A_3$为$x_3\ge 8$的解，$x_1+x_2+y_3+8=15$

$|A_3|=C(7+3-1,7)=C(9,2)$

$A_1\cap A_2:y_1+6+y_2+7+x_3=15,|A_1\cap A_2|=C(4,2)$

$A_1\cap A_3:y_1+6+x_2+y_3+8=15,|A_1\cap A_3|=C(3,1)$

$A_2\cap A_3:x_1+y_2+7+y_3+8=15,|A_2\cap A_3|=1$

---

n对夫妻问题

n对夫妻围圆桌而坐，夫妻不相邻的方案数？

$$N=(2n-1)!-2\begin{pmatrix}n\\ 1\end{pmatrix}(2n-2)!+2^2\begin{pmatrix}n\\ 2\end{pmatrix}(2n-3)!-\cdots+(-1)^n2^n\begin{pmatrix}n\\ n\end{pmatrix}(n-1)! \\ =\sum_{h=0}^n(-1)^h2^h\begin{pmatrix}n\\ h\end{pmatrix}(2n-h-1)!$$

---

鸽巢原理举例

从$1\sim 2n$的$2n$个正整数中任取$n+1$个，则这$n+1$个数中至少有一对数，其中一个数是另一个数的倍数

设所取$n+1$数是$a_1,a_2,\cdots,a_n,a_{n+1}$

对$a_1,a_2,\cdots,a_n,a_{n+1}$序列中的每一个数去掉所有2的因子，直至剩下一个奇数为止，例如$68=2\times 34=2^2\times 17$,去掉$2$的因子$2^2$,留下了奇数$17$,结果得到由奇数组成的序列$r_1,r_2,\cdots,r_{n+1}$

$1\sim 2n$中只有$n$个奇数，故序列$(*)$中至少有两个是相同的，设$r_i=r_j=r$

对应地有$a_i=2^{ai}r,a_j=2^{aj}r$,

若$a_i>a_j$,则$a_i$是$a_j$的倍数

---

设$a_1,a_2,\cdots,a_m$是正整数的序列，则至少存在整数$k$和$l$,其中$1\le k<l\le m$,使得$a_k+a_{k+1}+\cdots+a_l$是$m$的倍数

构造一个序列$s_1=a_1,s_2=a_1+a_2,s_3=a_1+a_2+a_3,\cdots,s_m=a_1+a_2+\cdots+a_m$，

其中$s_1<s_2<s_3<\cdots<s_m$

有两种情况

(1)若有一个$s_h$是m的倍数，则定理已经得以证明

(2)设在上面的序列没有任何一个是$m$的倍数，则零$s_h=r_h\ mod \ m$

其中$h=1,2,\cdots,m$，假定上面的序列中所有的项都非$m$的倍数，其中$r_1,r_2,\cdots,r_m$无一为0，而且所有的$r_h$均小于m,不超过$m-1$的正整数只有$m-1$个，根据鸽巢原理，其中至少存在一对$r_h=r_k$,满足$r_h=r_k$,即$s_h$和$s_h$满足

$s_k\equiv s_h\ mod \ n$

不妨设$h>k$

$s_h=a_1+a_2+\cdots+a_k+a_{k+1}+\cdots+a_h$

$s_k=a_1+a_2+\cdots+a_k$

$s_h-s_k=a_{k+1}+a_{k+2}+\cdots+a_h\equiv0\ mod \ n$

---

设$a_1,a_2,a_3$是3个任意整数，$b_1,b_2,b_3$是$a_1,a_2,a_3$的任一排列，则$a_1-b_1,a_2-b_2,a_3-b_3$至少有一个是偶数

$a_1,a_2,a_3$中至少有两个数同为偶数，或同为奇数，不妨假设这两个数为$a_1$和$a_2$,且同为奇数，则$a_1,a_2,a_3$中至少有一个偶数。$b_1,b_2$至少有一个是奇数

而且有一个和$a_1,a_2$中某一个相等，奇数与奇数之差为偶数，故$a_1-b_1,a_2-b_2$中至少有一个为偶数。

---

设$a_1,a_2,\cdots,a_{100}$是由1和2组成的序列，已知从其任一数开始的顺序10个数的和不超过16，即

$a_i+a_{i+1}+\cdots+a_{i+9}\le 16$

则至少存在$h$和$k,k>h$,使得$a_{h+1}+\cdots a_k=39$

• 根据假定$a_i+a_{i+1}+\cdots+a_{i+9}\le 16,1\le i\le 91$,有$S_{100}\le 10\times 16=160$，$S_1,S_2,\cdots,S_{100}$相互不相同

• 做序列$S_1,S_2,\cdots,S_{100},S_1+39,\cdots,S_{100}+39$共200项。其中最大项

  $S_{100}+39\le 160+39=199$

  因为一共200项，最大值是199,。所以根据鸽巢原理，必有两项相等。而且必是前段中某个项与后段中某一项相等

  $S_k=S_h+39,k>h,S_k-S_h=39$

第四章 Polya定理

用3个红珠子和2个蓝珠子镶嵌在圆环上，试问有多少种方案？

用红，蓝，绿3种颜色的珠子镶上，试问 有多少种不同的方案？

甲烷$CH_4$的4个键任意用$H,CI,CH_3,C_2H_5$链接，有多少种方案？

$CH_4$的结构是一个空间正4面体，$C$原则居于正4面体的中心。正4面体的转动群按转动轴分类：

不动旋转，$(A)(B)(C)(D)$共有1个$(1)^4$循环

以顶点与对面的中心连线为轴，按反时针方向旋转120度。共有8个$(1)^1(3)^1$循环

以正四面体的$3$对对边之中点联线为旋转转180度，共有3个$(2)^2$循环

$(1\times 4^4+8\times 4^2+3\times 4^2)/12=36$

1表示不动循环有1个，$4$表示进行的4着色，上面的4表示有多少个循环，不动旋转中有4个循环，所以写4

正六面体的6个面分别用红，蓝两种颜色着色，问有多少种不同方案？