USTC课程资源分享在线

Contributors

• *1. 求下列序列的生成函数
  • (3) 0, 1$\cdot$3, 2$\cdot$4, $\cdots$, $n(n+2)$, $\cdots$;
• *2. 利用生成函数计算下列和式：
  • (2) 1$\cdot$3, 2$\cdot$4, $\cdots$, $n(n+2)$, $\cdots$;
  • 3. 序列$\{\frac{1}{n+1}\}$的指数型生成函数为$\frac{1}{x}[e(x)-1]$
  • 4. 从$\{n\cdot a,n\cdot b,n\cdot c\}$中取出n个字母，要求a的个数为偶数，问有多少种取法？
• *5. 由字母a,b,c,d,e组成的长为n的字中，要求a与b的个数之和为偶数，问这样的字有多少个？
• *6 证明： 方程
  • 7. 设多重集合$S=\{\infty \cdot e_1,\infty \cdot e_2,\infty \cdot e_3,\infty \cdot e_4\}$, $a_n$表示集合S满足下列条件的n组合数，分别求数列的生成函数。
  • 8.用恰好k种可能的颜色做旗子，使得每面旗子由$n(n\ge k)$条彩带构成，且相邻两条彩带的颜色不同，求不同的旗子数。
  • 9. 在 $10^2$和$10^6$之间有多少个整数，其各位数字之和等于5？
  • 10.用生成函数证明下列等式：
  • 11. 设多重集合$S=\{\infty \cdot e_1,\infty \cdot e_2,\cdots ,\infty \cdot e_k\}$, $a_n$表示集合S满足下列条件的n排列数，分别求数列$a_n$的指数型生成函数。
  • *12. 设有砝码重为1g的3个，重为2g的4个，重为4g的2个，问能称出多少种重量？各有几种方案？
  • 13.证明$m\equiv 0(mod6)$时，有：$B(m,3)=\frac{m^2}{12}$
  • *14 设将N无序分拆成正整数之和且使得这些正整数都小于或等于m的方法数为$B^{\prime }(N,M)$.证明$B^{\prime }(N,M)=B^{\prime }(N,m-1)+B^{\prime }(N-m,m)$
  • 15 设$(N,n,m)$表示将N有序分拆成n个分部量且每个分部量都小于或等于m的分拆数，证明$(N,n,m)$就是$(x+x+\cdots +x^m{)}^n$的展开式中$x^N$的系数
  • 16.假定工人A适合工作3,4,5,工人B适合工作2，3，而工人2,3，而工人C适合工作5。同样每一名工人至少指定一项工作，每一项工作不超过一名工人，一名工人只得到他适合的一项工作。建立一个生成函数并使用它回答问题。
  • 17.假设$a_{n+1}=(n+1)b_n$，且$a_0=b_0=1$，如果$A(x)$是序列$\{a_n\}$的指数生成函数，$B(x)$是序列$b_n$的指数生成函数，推导$A(x)$和$B(x)$之间的关系
  • 18. 令$h_n$表示具有$n+2$条边的凸边形区域被其对角线所分成的区域数，假设没有三条对角线共线。定义$h_0=0$。证明$$h_n=h_{n-1}+C_{n+1}^3+n(n\ge 1)$$
  • 19.如果要把棋盘上偶数个方格涂成红色，试确定用红色、白色和蓝色对$1\times n$棋盘的方格涂色的方法数。
  • *20 在一个程序设计课程里，每个学生的每个任务最多可以运行十次。教员发现某个任务共运行38次。设有15名学生，每个学生对这个任务至少做一次。求观察到的总次数的组合数。
  • 21. 证明：$$\sum _{k=0}^n{2}^k{C}_{2n-k}^k=2^{2n}$$

转载自liuzengh/combinatorial-mathematics

*1. 求下列序列的生成函数

(3) 0, 1$\cdot$3, 2$\cdot$4, $\cdots$, $n(n+2)$, $\cdots$;

$$f(x)=\sum _{i=0}^{\infty }i(i+2)x^i$$

*2. 利用生成函数计算下列和式：

(2) 1$\cdot$3, 2$\cdot$4, $\cdots$, $n(n+2)$, $\cdots$;

序列的生成函数为： $$f(x)=\sum _{i=0}^{\infty }(i+1)(i+3)x^i=\sum _{i=0}^{\infty }{i}^2{x}^i+4\sum _{i=0}^{\infty }i{x}^i+3\sum _{i=0}^{\infty }{x}^i=\frac{x(1+x)}{(1-x{)}^3}+\frac{4x}{(1-x{)}^2}+\frac{3}{1-x}=\frac{3-x}{(1-x{)}^3}=(3-x)\sum _{k=0}^{\infty }{C}_{k+3}^k{x}^k$$

对应有$$\sum _{i=1}^{n}i(i+2)=3C_{n+3}^n-C_{n+2}^{n-1}=\frac{n(n+1)(2n+7)}{6}$$

3. 序列$\{\frac{1}{n+1}\}$的指数型生成函数为$\frac{1}{x}[e(x)-1]$

(1)证明： 序列$\{{\sum }_{i=0}^n\frac{n!}{(n-i+1)!(i+1)!}\}$的指数型生成函数为$\frac{1}{x^2}[e(x)-1{]}^2$

$\frac{1}{x^2}[e(x)-1{]}^2=({\sum }_{i=0}^{\infty }\frac{1}{i+1}\frac{x^i}{i!})({\sum }_{j=0}^{\infty }\frac{1}{j+1}\frac{x^j}{j!})={\sum }_{n=0}^{\infty }({\sum }_{i=0}^n\frac{1}{(i+1)i!}\frac{1}{(n-i+1)(n-i)!})x^n={\sum }_{n=0}^{\infty }({\sum }_{i=0}^n\frac{n!}{(i+1)!(n-i+1)!})\frac{x^n}{n!}$
所以序列$\{{\sum }_{i=0}^n\frac{n!}{(n-i+1)!(i+1)!}\}$的指数型生成函数为$\frac{1}{x^2}[e(x)-1{]}^2$

(2)计算${\sum }_{i=0}^n\frac{n!}{(n-i+1)!(i+1)!}$

$\frac{1}{x^2}[e(x)-1{]}^2=\frac{1}{x^2}(e(2x)-2e(x)+1)=\frac{1}{x^2}({\sum }_{k=0}^{\infty }(2^k-2)\frac{x^k}{k!}+1)={\sum }_{k=2}^{\infty }(2^k-2)\frac{x^{k-2}}{k!}={\sum }_{n=0}^{\infty }(2^{n+2}-2)\frac{x^n}{(n+2)!}$
第n项为： ${\sum }_{i=0}^n\frac{n!}{(n-i+1)!(i+1)!}=\frac{n!(2^{n+2}-2)}{(n+2)!}=\frac{(2^{n+2}-2)}{(n+2)(n+1)}$

4. 从$\{n\cdot a,n\cdot b,n\cdot c\}$中取出n个字母，要求a的个数为偶数，问有多少种取法？

$(1+x^2+x^4+\cdots )(1+x+x^2+\cdots {)}^2=\frac{1}{1-x^2}\frac{1}{(1-x{)}^2}=\frac{1}{(1-x{)}^3}\frac{1}{1+x}={\sum }_{n=0}{C}_{n+2}^n{x}^n{\sum }_{n=0}^{\infty }(-x{)}^n$
第n项: ${\sum }_{i=0}^n(-1{)}^i{C}_{n-i+2}^{n-i}={\sum }_{i=0}^n(-1{)}^i{C}_{n-i+2}^2$

*5. 由字母a,b,c,d,e组成的长为n的字中，要求a与b的个数之和为偶数，问这样的字有多少个？

排列型分配问题的指数生成函数。

1.a 与 b 的个数均为奇数:

$M_a=M_b=\{1,3,,5,\dots ,2k+1\};M_c=M_d=M_e=\{0,1,2,3,4,\dots ,k\}$

2.a 与 b 的个数均为偶数:

$M_a=M_b=\{0,2,,4,\dots ,2k\};M_c=M_d=M_e=\{0,1,2,3,4,\dots ,k\}$

$$(\frac{x}{1!}+\frac{x^3}{3!}+\cdots {)}^2(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots {)}^3+(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots {)}^2(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots {)}^3=(\frac{e(x)-e(-x)}{2}{)}^2{e}^3(x)+(\frac{e(x)+e(-x)}{2}{)}^2{e}^3(x)=(\frac{e(2x)+e(-2x)}{2})e(3x)=\frac{e(5x)+e(x)}{2}$$
$\frac{x^n}{n!}$的系数为 $\frac{5^n+1}{2}$, 该系数即为总的字个数。

*6 证明： 方程

$x_1+x_2+\cdots +x_7=13$和 $x_1+x_2+\cdots +x_{14}=6$有相同数目的非负整数解。 证明： $C_{13+7-1}^{13}=C_{19}^{13}$, $C_{14+6-1}^6=C_{19}^6$

$(1+x+x^2+\cdots {)}^7=\frac{1}{(1-x{)}^7}={\sum }_{n=0}^{\infty }{C}_{n+7-1}^n{x}^n$, $x^{1}3$的系数为$C_{19}^{13}$
$(1+x+x^2+\cdots {)}^{1}4=\frac{1}{(1-x{)}^{1}4}={\sum }_{n=0}^{\infty }{C}_{n+14-1}^n{x}^n$,$x^6$的系数为$C_{19}^6$
因为$C_{19}^{13}=C_{19}^6$，所以方程$x_1+x_2+\cdots +x_7=13$和$x_1+x_2+\cdots +x_{14}=6$有相同数目的非负整数解。

7. 设多重集合$S=\{\infty \cdot e_1,\infty \cdot e_2,\infty \cdot e_3,\infty \cdot e_4\}$, $a_n$表示集合S满足下列条件的n组合数，分别求数列的生成函数。

(1)每个$e_i(i=1,2,3,4)$出现奇数次；

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

(2)每个$e_i(i=1,2,3,4)$出现3的倍数次；

$(1+x^3+x^6+\cdots {)}^4=\frac{1}{(1-x^3{)}^4}$

(3)$e_1$不出现，$e_2$至多出现1次；

$(1+x)(1+x+x^2+x^3+\cdots {)}^2=\frac{1+x}{(1-x{)}^2}$

*(4)$e_i(i=1,2,3,4)$出现1，3或11次，$e_2$出现2，4或5次；

$(x+x^3+x^{11})(x^2+x^4+x^5)(1+x+x^2+x^3+\cdots {)}^2=\frac{x^3+2x^5+x^6+x^7+x^8+x^{13}+x^{15}+x^{16}}{(1-x{)}^2}==(x^3+2x^5+x^6+x^7+x^8+x^{13}+x^{15}+x^{16}){\sum }_{k=0}^{\infty }{C}_{k+1}^k{x}^k$

(5)每个$e_i(i=1,2,3,4)$至少出现10次;

$(x^{10}+x^{11}+x^{12}+\cdots {)}^4=\frac{x^{40}}{(1-x{)}^4}$

8.用恰好k种可能的颜色做旗子，使得每面旗子由$n(n\ge k)$条彩带构成，且相邻两条彩带的颜色不同，求不同的旗子数。

$k(k-1{)}^{n-1}$

9. 在 $10^2$和$10^6$之间有多少个整数，其各位数字之和等于5？

0到100之间各位数字之和等于5的数有6个： 05，14，23，32，41，50

$(1+x+x^2+x^3+x^4+x^5+\cdots {)}^6=\frac{1}{(1-x{)}^6}={\sum }_{n=0}^{\infty }{C}_{n+5}^n{x}^n$

$C_{5+5}^5-6=C_{10}^5-6$

10.用生成函数证明下列等式：

(1) $C_{n-1}^r+C_{n-1}^{r-1}=C_n^r$

$\frac{1}{(1-x{)}^{n-r}}+\frac{x}{(1-x{)}^{n-r+1}}=\frac{1}{(1-x{)}^{n-r+1}}$

(2) $C_{n+2}^r-2C_{n+1}^r+C_n^r=C_n^{r-2}$

$\frac{1}{(1-x{)}^{n+3-r}}-\frac{2}{(1-x{)}^{n+2-r}}+\frac{1}{(1-x{)}^{n-r+1}}=\frac{x^2}{(1-x{)}^{n-r+3}}$

(3)${\sum }_{j=0}^q(-1{)}^j{C}_q^j{C}_{n+q-j}^r=C_n^{r-q}$

11. 设多重集合$S=\{\infty \cdot e_1,\infty \cdot e_2,\cdots ,\infty \cdot e_k\}$, $a_n$表示集合S满足下列条件的n排列数，分别求数列$a_n$的指数型生成函数。

(1)S的每个元素出现奇数次；

$(\frac{x}{1}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots {)}^k=(\frac{e(x)-e(-x)}{2}{)}^k$

(2)S的每个元素至少出现4次；

$(\frac{x^4}{4!}+\frac{x^5}{5!}+\cdots {)}^k=(e(x)-\frac{x^3}{3!}-\frac{x^2}{2}-\frac{x}{1}-1{)}^k$

*(3)$e_i$至少出现i次($i=1,2,\cdots ,k$);

$$(\frac{x}{1!}+\frac{x^2}{2!}+\cdots )(\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots )\cdots (\frac{x^k}{k!}+\frac{x^{k+1}}{(k+1)!}+\cdots )=(e(x)-1)(e(x)-1-x)(e(x)-1-x-\frac{x^2}{2!})(e(x)-1-x-\cdots -\frac{x^{k-1}}{(k-1)!})$$

(4)$e_i$至多出现i次($i=1,2,\cdots ,k$);

$$(1+\frac{x}{1!})(1+\frac{x}{1!}+\frac{x^2}{2!})(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})\cdots (1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots +\frac{x^k}{k!})$$

*12. 设有砝码重为1g的3个，重为2g的4个，重为4g的2个，问能称出多少种重量？各有几种方案？

能称出 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16, 17, 18, 19 一共20种重量,其中 $x^i$的系数代表称出i种重量的方案数 $(1+x+x^2+x^3)(1+x^2+x^4+x^6+x^8)(1+x^4+x^8)=x^{19}+x^{18}+2x^{17}+2x^{16}+3x^{15}+3x^{14}+4x^{13}+4x^{12}+5x^{11}+5x^{10}+5x^9+5x^8+4x^7+4x^6+3x^5+3x^4+2x^3+2x^2+x+1$

13.证明$m\equiv 0(mod6)$时，有：$B(m,3)=\frac{m^2}{12}$

import sympy
from sympy import init_printing
x = sympy.Symbol("x")
f = (1+x+x**2+x**3) * (1+x**2 + x**4 + x**6 + x**8) *(1+x**4 + x**8)
sympy.latex(sympy.expand(f))

'x^{19} + x^{18} + 2 x^{17} + 2 x^{16} + 3 x^{15} + 3 x^{14} + 4 x^{13} + 4 x^{12} + 5 x^{11} + 5 x^{10} + 5 x^{9} + 5 x^{8} + 4 x^{7} + 4 x^{6} + 3 x^{5} + 3 x^{4} + 2 x^{3} + 2 x^{2} + x + 1'

*14 设将N无序分拆成正整数之和且使得这些正整数都小于或等于m的方法数为$B^{\prime }(N,M)$.证明$B^{\prime }(N,M)=B^{\prime }(N,m-1)+B^{\prime }(N-m,m)$

$N=x_1+x_2+x_i+\cdots ,x_i\le m$, $B^{\prime }(N,M)$可以划分为两类，一类是$\exists x_i=M$,直接从N去掉该分部量$x_i$, $B^{\prime }(N-m,m)$; 另外一类是$\nexists x_i=M$, 所以$\forall x_i\le m-1$, 即$B^{\prime }(N,m-1)$。 根据加法原理有：$B^{\prime }(N,M)=B^{\prime }(N,m-1)+B^{\prime }(N-m,m)$

15 设$(N,n,m)$表示将N有序分拆成n个分部量且每个分部量都小于或等于m的分拆数，证明$(N,n,m)$就是$(x+x+\cdots +x^m{)}^n$的展开式中$x^N$的系数

$x_1+x_2+\cdots +x_n=N,1\le x_i\le m$

16.假定工人A适合工作3,4,5,工人B适合工作2，3，而工人2,3，而工人C适合工作5。同样每一名工人至少指定一项工作，每一项工作不超过一名工人，一名工人只得到他适合的一项工作。建立一个生成函数并使用它回答问题。

有多少种方法给一名工人指定一项工作？

有多少种方法给两名工人指定一项工作？

有多少种方法给三名工人指定一项工作？

17.假设$a_{n+1}=(n+1)b_n$，且$a_0=b_0=1$，如果$A(x)$是序列$\{a_n\}$的指数生成函数，$B(x)$是序列$b_n$的指数生成函数，推导$A(x)$和$B(x)$之间的关系

$A(x)={\sum }_{k=0}^{\infty }\frac{x^k}{k!}={\sum }_{k=1}^{\infty }k{b}_{k-1}\frac{x^k}{k!}+a_0={\sum }_{k=1}^{\infty }{b}_{k-1}\frac{x^k}{(k-1)!}+1$

$\frac{A(x)-1}{x}={\sum }_{k=1}^{\infty }(b_{k-1}\frac{x^k-1}{(k-1)!})=B(x)$

$A(x)=xB(x)+1$

18. 令$h_n$表示具有$n+2$条边的凸边形区域被其对角线所分成的区域数，假设没有三条对角线共线。定义$h_0=0$。证明$$h_n=h_{n-1}+C_{n+1}^3+n(n\ge 1)$$

然后确定生成函数，并由此得出$h_n$的公式。

19.如果要把棋盘上偶数个方格涂成红色，试确定用红色、白色和蓝色对$1\times n$棋盘的方格涂色的方法数。

$(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots )(1+\frac{x}{1}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots {)}^2=(e(x)+e(-x))e(x{)}^2=e(3x)+e(x)$, 其中 $\frac{x^n}{n!}$的系数$3^n+1$就是满足要求的涂色方法数.

*20 在一个程序设计课程里，每个学生的每个任务最多可以运行十次。教员发现某个任务共运行38次。设有15名学生，每个学生对这个任务至少做一次。求观察到的总次数的组合数。

$x_1+x_2+\cdots +x_{15}=38,1\le x_i\le 10$ 组合数的生成函数$(x+x^2+\cdots +x^{10}{)}^{15}=(\frac{x(1-x^{10})}{1-x}{)}^{15}=(x-x^{11}{)}^{15}\frac{1}{(1-x{)}^{15}}=(x-x^{11}{)}^{15}{\sum }_0^{\infty }{C}_{14+k}^k{x}^k=x^{15}{\sum }_{i=0}^{15}{C}_{15}^i(-1{)}^i{x}^{10i}{\sum }_{k=0}^{\infty }{C}_{14+k}^k{x}^k$
$x^{38}$的系数为$C_{14+23}^{23}+C_{15}^1(-1{)}^1{C}_{14+13}^{13}+C_{15}^2(-1{)}^2{C}_{14+3}^3=5806283700$就是观察到的总次数的组合数。

21. 证明：$$\sum _{k=0}^n{2}^k{C}_{2n-k}^k=2^{2n}$$