离散数学作业 20251023 第七章
离散数学作业 20251023 第七章
3. 某单位有 9 位先生， 5 位女士，要从他们中产生一个小组，规定先生必须偶数个，女士至少要有两位，问有多少种产生小组的方法？
解：生成函数为 $f(x)=(1+x^2+x^4+x^6+x^8)(x^2+x^3+x^4+x^5)$.
答案即为系数和，即为 $f(1)=20$.
10. 解下列递推关系：
(1) $a_r-7a_{r-1}+10a_{r-2}=3^r$. 其中 $a_0=0,a_1=1$ .
解：特征方程是 $(r^2-7r+10)(r-3)=0$.
解得 $r_1=2,r_2=3,r_3=5$.
故 $a_n=c_1 2^n+c_2 3^n + c_3 5^n, a_0=0,a_1=1,a_2=16$.
解得 $a_n=\dfrac{8}{3}\times 2^n-\dfrac{9}{2}\times 3^n + \dfrac{11}{6}\times 5^n$.
(2) $a_r-2a_{r-1}+2a_{r-2}-a_{r-3}=0$. 其中 $a_0=0,a_1=1,a_2=1$.
解：特征方程是 $r^3-2r^2+2r-1=0$. 解得 $r_1=1,r_{2,3}=\dfrac{1\plusmn \sqrt 3 i}{2}$.
故 $a_n=c_1 +c_2 (\dfrac{1+ \sqrt 3 i}{2})^n + c_3 (\dfrac{1- \sqrt 3 i}{2})^n$.
解得 $a_n = \dfrac{i}{\sqrt{3}}\left[ \left(\dfrac{1 - \sqrt{3}i}{2}\right)^n - \left(\dfrac{1 + \sqrt{3}i}{2}\right)^n \right]$.
12. 求由 $A={0, 1, 2, 3}$ 中的数构成的：
(1) 具有偶数个 0 的 $n$ 位数的个数。
解：一共 $n$ 个位置，首位不放 $0$。
考虑选择 $k$ 个位置放 $0$，共 $C_{n-1}^k\times3^{n-k}$ 种选择。
故答案为$\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}C_{n-1}^{2k}\times3^{n-2k}= \dfrac{3}{2} (4^{n-1} + 2^{n-1})$.
(2) 具有偶数个 0 和偶数个 1 的 $n$ 位数的个数。
不考虑 $0$ 在首位，生成函数为
$S(x) = \left[\dfrac{x^{n}}{n!}\right]\left( \dfrac{e^x + e^{-x}}{2} \right) \left( \dfrac{e^x + e^{-x}}{2} \right) (e^x)(e^x)$
考虑 $0$ 在首位，则 $0$ 的个数为奇数，生成函数为
$T(x) = \left[\dfrac{x^{n-1}}{(n-1)!}\right]\left( \dfrac{e^x - e^{-x}}{2} \right) \left( \dfrac{e^x + e^{-x}}{2} \right) e^{2x}$
计算得 $a_n = \begin{cases} 2 & \text{if } n=1 \ 3 \cdot 4^{n-2} + 2^{n-1} & \text{if } n \ge 2 \end{cases}$
13. 在一个核反应器内有两类粒子，在每一秒种里，1 个 $a$ 粒子分裂为 3 个 $\beta$ 粒子，1 个 $\beta$ 粒子分裂为 1 个 $a$ 粒子和 2 个 $\beta$ 粒子。如果在时间 $t=0$ 时，反应器里只有 1 个 $a$ 粒子，则在时间 $t=100$ 时，总共有多少粒子？
解：$a_n=b_{n-1}, b_n=2b_{n-1}+3a_{n-1},a_0=1,b_0=0$.
设 $T_n$ 为 $n$ 时刻的总粒子数，则 $T_n=a_n+b_n=3a_{n-1}+3b_{n-1}=3T_{n-1}$.
$t=100$ 时，共有 $3^{100}$ 个粒子.
14. 用生成函数的方法解下列递推关系。
(1) $a_n = 5a_{n-1} - 6a_{n-2}$ ($n \ge 2$)，这里 $a_0 = 1, a_1 = -2$。
解：设 $OGF$ 为 $A(x) = \sum_{n=0}^\infty a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots$
则有 $$\sum_{n=2}^\infty a_n x^n = \sum_{n=2}^\infty (5a_{n-1} - 6a_{n-2}) x^n$$
$$\sum_{n=2}^\infty a_n x^n = 5 \sum_{n=2}^\infty a_{n-1} x^n - 6 \sum_{n=2}^\infty a_{n-2} x^n$$
故 $$A(x) - a_0 - a_1 x = 5x(A(x) - a_0) - 6x^2 A(x)$$
代入 $a_0=1,a-1=-2$，有
$$A(x) - 1 - (-2)x = 5x(A(x) - 1) - 6x^2 A(x)$$
$$A(x) = \dfrac{1 - 7x}{1 - 5x + 6x^2}=\dfrac{5}{1 - 2x} - \dfrac{4}{1 - 3x}$$
所以 $$A(x) = 5 \sum_{n=0}^\infty (2x)^n - 4 \sum_{n=0}^\infty (3x)^n$$
$$A(x) = \sum_{n=0}^\infty (5 \cdot 2^n - 4 \cdot 3^n) x^n$$
得到 $$a_n = 5 \cdot 2^n - 4 \cdot 3^n$$
(2) $a_n = \sum_{k=1}^{n-1} a_k a_{n-k}$ ($n \ge 2$)，这里 $a_1 = 1$。
定义 $a_0=0$.
设 $OGF$ 为 $A(x) = \sum_{n=0}^\infty a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots = \sum_{n=1}^\infty a_n x^n$.
$$A(x)^2 = \left( \sum_{n=1}^\infty a_n x^n \right) \left( \sum_{k=1}^\infty a_k x^k \right)$$
$$A(x)^2 = \sum_{n=2}^\infty \left( \sum_{k=1}^{n-1} a_k a_{n-k} \right) x^n$$
故由递推关系得 $$A(x)^2 = \sum_{n=2}^\infty a_n x^n$$
由于 $$A(x) = a_0 x^0 + a_1 x^1 + \sum_{n=2}^\infty a_n x^n$$
$$A(x) = 0 + a_1 x + \sum_{n=2}^\infty a_n x^n$$
$$A(x) = a_1 x + A(x)^2$$
代入 $a_1=1$ 有 $$A(x) = x + A(x)^2$$
解得 $$A(x) = \dfrac{1 \pm \sqrt{1 - 4x}}{2}$$
由于 $a_0=0$，故取减号，所以 $$A(x) = \dfrac{1 - \sqrt{1 - 4x}}{2}$$
由二项式定理，$\sqrt{1-4x}=1+\sum_{k=1}^{\infty}\binom{1/2}{k}(-4x)^k$
故 $x^n$ 的系数为 $\dfrac{1}{2(2n-1)}\dbinom{2n}{n}$.
15. 平面上有 $n$ 条直线，任意两条不平行，任意三条不交于一点。问这 $n$ 条直线共有多少个交点？这些直线把平面分割成多少个不相交的区域？
解：交点数：$a_n=a_{n-1}+n-1, a_1=0$，解得 $a_n=\dfrac{n(n-1)}{2}$.
分平面数：$b_n=b_n-1+n,b_1=2$，解得 $b_n=1+\dfrac{n(n+1)}{2}$.