算法导论C.1 Exercises 答案

C.1-1

\[\begin{aligned} &n-k+1;\\ &\sum_{k=1}^n(n-k+1)=\sum_{k=1}^n k=\dfrac{n(n+1)}{2} \end{aligned}\]

C.1-2

对于每一个输入，都有\(2\)个输出。由于一共有\(2^n\)个输入，这意味着有\(2^{2^n}\)个不同的布尔函数。

更一般的，对于每一个输入，都有\(2^m\)个输出。由于一共有\(2^n\)个输入，这意味着有\((2^m)^{2^n}=2^{m\cdot 2^n}\)个不同的布尔函数。

C.1-3

这是一个循环排列，因此对于第\(1\)个被放置的物品而言，放在哪个位置都没有意义，此时仅有\(1\)种方法放置。第\(1\)个物品的位置确定后，放置第\(2\)个物品时，那么就有\(n-1\)种选择方式……放置第\(i\)个物品时，有\(n-i+1\)种方法。因此，最终的方法数量为\(1\times (n-1)\times (n-2)\times \dots \times 1=(n-1)!\)。

C.1-4

注意这里一共有\(49\)个偶数，\(50\)个奇数。为了使取出的\(3\)个数之和为偶数，有以下两种情况：

• 取出的\(3\)个数都为偶数，有\(\dbinom{49}{3}\)种取法。

• 取出的\(3\)个数中，\(1\)个为偶数，\(2\)个为奇数，有\(\dbinom{49}{1}\cdot \dbinom{50}{2}\)种取法。

因此最终有\(\dbinom{49}{3}+\dbinom{49}{1}\cdot \dbinom{50}{2}=78449\)种取出方法。

C.1-5

\(\begin{aligned} \dbinom{n}{k}&=\dfrac{n!}{k!\cdot(n-k)!}\\ &=\dfrac{n}{k}\cdot \dfrac{(n-1)!}{(k-1)!\cdot(n-k)!}\\ &=\dfrac{n}{k}\cdot \dfrac{(n-1)!}{(k-1)!\cdot((n-1)-(k-1))!}\\ &=\dfrac{n}{k}\cdot \dbinom{n-1}{k-1}\\ \end{aligned}\)

C.1-6

\(\begin{aligned} \dbinom{n}{k}&=\dfrac{n!}{k!\cdot(n-k)!}\\ &=\dfrac{n}{n-k}\cdot \dfrac{(n-1)!}{k!\cdot(n-k-1)!}\\ &=\dfrac{n}{n-k}\cdot \dfrac{(n-1)!}{k!\cdot((n-1)-k)!}\\ &=\dfrac{n}{n-k}\cdot \dbinom{n-1}{k}\\ \end{aligned}\)

C.1-7

目前求解\(\dbinom{n}{k}\)的递推式。考虑现在选择的是第\(n\)个物品，并且已经选择了\(k\)次。

• 如果第\(n\)个物品没有被选择，那么说明前面\(n-1\)个物品中需要选择\(k\)个，有\(\dbinom{n-1}{k}\)种方法。

• 如果第\(n\)个物品被选择，那么说明前面\(n-1\)个物品中需要选择\(k-1\)个，有\(\dbinom{n-1}{k-1}\)种方法。加上第\(n\)个物品就变成了从\(n\)个物品种选择\(k\)个。

因此有\(\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\)。

C.1-8

杨辉三角前\(7\)行：

\[\begin{aligned} &&1 \\ &&1 &&1 \\ &&1 &&2 &&1 \\ &&1 &&3 &&3 &&1 \\ &&1 &&4 &&6 &&4 &&1 \\ &&1 &&5 &&10 &&10 &&5 &&1 \\ &&1 &&6 &&15 &&20 &&15 &&6 &&1 \\ \end{aligned}\]

C.1-9

序列\(a_i=i\)是首项为\(1\)，公差为\(1\)的等差数列。因此有

\(\begin{aligned} \sum_{i=1}^n i&=\dfrac{n(n+1)}{2}=\dfrac{(n+1)!}{2!\cdot (n-1)!}=\dfrac{(n+1)!}{2!\cdot ((n+1)-2)!}=\dbinom{n+1}{2} \end{aligned}\)

C.1-10

对于\(k\ge 1\)，对行内相邻的两个组合数做商，得到：

\(\dfrac{\dbinom{n}{k}}{\dbinom{n}{k-1}}=\dfrac{n!}{k!(n-k!)}\cdot\dfrac{(k-1)!(n-k+1)!}{n!}=\dfrac{n-k+1}{k}\)

可以发现，随着\(k\)值上升，\(f(k)=\dfrac{n-k+1}{k}\)先递增，后递减。

当\(f(k)\)非严格递增时，满足\(f(k)\ge 1\)，也就是\(2k\le n+1\)时，满足递增。此时有\(k\le \dfrac{n+1}{2}=\left\lceil\dfrac{n}{2}\right\rceil\)。

当\(f(k)\)非严格递减时，满足\(f(k)\le 1\)，也就是\(2k\ge n+1\)时，满足递增。此时有\(k\ge \dfrac{n+1}{2}=\left\lceil\dfrac{n}{2}\right\rceil\)。

因此当\(k=\left\lceil\dfrac{n}{2}\right\rceil\)时，\(\dbinom{n}{k}\)能取到最大值。

另外由于对于所有正数\(n\)，\(\left\lfloor\dfrac{n}{2}\right\rfloor+\left\lceil\dfrac{n}{2}\right\rceil\)都成立。因此根据等式\(C.3\)，当\(k=\left\lfloor\dfrac{n}{2}\right\rfloor\)时，\(\dbinom{n}{k}\)也能取到最大值。

C.1-11

代数证明：

\(\begin{aligned} \dbinom{n}{j}\cdot \dbinom{n-j}{k}&=\dfrac{n!}{j!(n-j)!}\cdot\dfrac{(n-j)!}{k!(n-j-k)!}\\ &=\dfrac{n!}{j! k!(n-j-k)!}\\ &\ge\dfrac{n!}{(j+k)!(n-(j+k))!}&\qquad(A)\\ &=\dbinom{n}{j+k} \end{aligned}\)

其中，变换\((A)\)使用了\(i!\cdot j!\le (i+j)!\)。

直观证明：

\(\dbinom{n}{j+k}\)相当于直接在一个阶段下，取出了\(j+k\)个物品。右边等式将取物品划分成了\(2\)个独立的阶段，第\(1\)个阶段是从\(n\)个物品中取出\(j\)个，有\(\dbinom{n}{j}\)种取法；第\(2\)个阶段是从剩下的\(n-j\)个物品中取出\(k\)个，有\(\dbinom{n-j}{k}\)种取法。对于\(\dbinom{n}{j+k}\)中的同一种取法，在\(\dbinom{n}{j}\cdot \dbinom{n-j}{k}\)中，它们取出的阶段可能不同，被视为了不同的取法，因此有重复。故\(\dbinom{n}{j}\cdot \dbinom{n-j}{k}\ge \dbinom{n}{j+k}\)成立。

实例：\(n=2,j=k=1\)。此时有：\(2=\dbinom{2}{1}\cdot \dbinom{1}{1}> \dbinom{2}{1+1}=1\)

\(\star\) C.1-12

当\(k=0\)时，\(1=\dbinom{n}{0}\le \dfrac{n^n}{0^0\cdot n^n}=1\)，结论成立。

假设对于\(0,1,2,\dots,k-1\)使得\(k\le n/2\)，原结论都成立。考虑\(k+1\)时的情况。那么有：

\(\begin{aligned} \dbinom{n}{k}&=\dfrac{n-k+1}{k}\cdot \dbinom{n}{k-1}\\ &\le \dfrac{n-k+1}{k} \dfrac{n^n}{(k-1)^{k-1}(n-(k-1))^{n-(k-1)}}\\ &=\dfrac{n^n}{k(k-1)^{k-1}(n-k+1)^{n-k}}\\ &\le\dfrac{n^n}{k^k(n-k)^{n-k}}&\qquad(A)\\ \end{aligned}\)

那么此时只需要证明变换\((A)\)满足\(k(k-1)^{k-1}(n-k+1)^{n-k}\ge k^k(n-k)^{n-k}\)即可，即证明

\[\left(\dfrac{k-1}{k}\right)^{k-1}\ge\left(\dfrac{n-k}{n-k+1}\right)^{n-k}\]

考虑函数\(f(x)=\left(\dfrac{x}{x+1}\right)^x\)，那么\(f'(x)=\dfrac{x^x}{(x+1)^{x+1}}\cdot (1+(x+1)\cdot (\ln x-\ln (x+1)))\)。可以发现，当\(x>0\)时，\(f'(x)\le 0\)。因此\(f(x)\)在区间\([0,+\infty)\)上单调递减。

由于\(k\le n/2\)，因此\(k-1\le n-k\)成立。那么\(f(k-1)\ge f(n-k)\)，上面的不等式成立，证明完成。

由于\(\dfrac{n^n}{k^k(n-k)^{n-k}}=\dfrac{n^n}{(n-k)^{n-k}k^k}\)，并且根据等式\(C.3\)，因此对于\(0\le k\le n\)，不等式均成立。

\(\star\) C.1-13

直接代入斯特林公式，有

\(\begin{aligned} \dbinom{2n}{n}&=\dfrac{\sqrt{4\pi n}\cdot\left(\dfrac{2n}{e}\right)^{2n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{\left(\sqrt{2\pi n}\cdot\left(\dfrac{n}{e}\right)^{n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\right)^2}\\ &=\dfrac{2\sqrt{\pi n}\cdot\left(2n\right)^{2n}\cdot\dfrac{1}{e^{2n}}}{2\pi n\cdot n^{2n}\cdot \dfrac{1}{e^{2n}}} \cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+\Theta\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+O\left(\dfrac{1}{n}\right)\right) \end{aligned}\)

\(\star\) C.1-14

\(H(\lambda)=-\lambda\lg\lambda-(1-\lambda)\lg(1-\lambda)\)

那么可以求出\(H'(\lambda)=\dfrac{\ln (1-\lambda)-\ln \lambda}{\ln 2},H''(\lambda)=\dfrac{1}{\lambda(\lambda-1)\cdot\ln 2}\)。

由于\(H'(1/2)=0,H''(1/2)=-\dfrac{4}{\ln 2}<0\)，因此\(H(\lambda)\)在\(\lambda=1/2\)处取到最大值.此时最大值为\(H(1/2)=1\).

\(\star\) C.1-15

根据二项式定理，有

\[(x+1)^n=\sum_{k=0} ^n \dbinom{n}{k} x^k\]

对此式两边对\(x\)进行求导（注意常数项），得到

\[n(x+1)^{n-1}=\sum_{k=1} ^n \dbinom{n}{k} \cdot kx^{k-1}\]

回代\(x=1\)，得到

\[n2^{n-1}=\sum_{k=1}^n\dbinom{n}{k} \cdot k \]

当\(k=0\)时，\(\dbinom{n}{0}\cdot 0=0\)，因此有

\[n2^{n-1}=\sum_{k=0}^n\dbinom{n}{k} \cdot k \]

\(\star\) C.1-16

当\(k=0\)时容易验证不等式成立。当\(n=1,2,3\)时，通过枚举可以验证原不等式成立：

\(\begin{array}{|l|l|l|l|} \hline n&k&\dbinom{n}{k}&\dfrac{n^k}{4k!}\\ \hline 1&1&1&1/4\\ \hline 2&1&2&1/2\\ \hline 3&1&3&3/4\\ \hline \end{array}\)

以下将证明\(n\ge 4\)时的情况。

为了证明\(\forall k\le \sqrt{n},\dbinom{n}{k} \ge\dfrac{n^k}{4k!}\)成立，相当于证明\(\dfrac{\prod_{i=n-k+1}^n i}{k!}\ge\dfrac{n^k}{4k!}\)。

化简后，相当于证明\(\displaystyle{\prod_{i=n-k+1}^n \dfrac{i}{n}}\ge \dfrac{1}{4}\)成立。

转换下标后，相当于证明\(\displaystyle{\prod_{i=0}^{k-1} \left(1-\dfrac{i}{n}\right)}\ge\frac{1}{4}\)成立。

那么有：

\(\begin{aligned} \prod_{i=0}^{k-1} \left(1-\dfrac{i}{n}\right)&\ge\prod_{i=0}^{k-1}\left(1-\dfrac{\sqrt{n}}{n}\right)\\ &\ge\left(1-\dfrac{1}{\sqrt{n}}\right)^{\lfloor\sqrt{n}\rfloor}\\ &\ge\left(1-\dfrac{1}{\sqrt{n}}\right)^{\sqrt{n}} \end{aligned}\)

考虑函数\(f(x)=\left(1-\dfrac{1}{x}\right)^x\)，那么对\(f(x)\)进行求导，得到\(f'(x)=\left(1-\dfrac{1}{x}\right)^x\cdot\left(\dfrac{1}{x-1}+\ln\left(\dfrac{x-1}{x}\right)\right)\)。

可以发现，\(\forall x>1,f'(x)>0\)恒成立。因此，\(\forall x\ge 2,f(x)\ge\dfrac{1}{4}\)成立。

由于\(n\ge 4,\sqrt{n}\ge 2\)，因此\(\displaystyle{\prod_{i=0}^{k-1}\left(1-\dfrac{i}{n}\right)\ge\dfrac{1}{4}}\)成立。故原结论成立。