免費試閱
Consider \(x_1+x_2+\cdots+x_n=r\), where \(a\le x_i\le b\) for \(1\le i\le n\). What is the generating function for the number of integer solutions to the above equation (where the desired count appears as the coefficient of \(x^r\), where \(r=0,1,\ldots\))?
每個 \(x_i\)：\(x^a+x^{a+1}+\cdots+x^b=\dfrac{x^a-x^{b+1}}{1-x}\)
共 \(n\) 個變數 → \(n\) 次方
\(\left(\dfrac{x^a-x^{b+1}}{1-x}\right)^{n}\)
What is the number of functions from \(\{1,2,\ldots,n\}^m\) to \(\{1,2,\ldots,i\}^j\)?
\(|\text{domain}|=n^m\)，\(|\text{codomain}|=i^j\)
函數個數 \(=|\text{codomain}|^{|\text{domain}|}\)
\(\left(i^{j}\right)^{n^m}\)
Consider \(x_1+x_2+\cdots+x_n\lt r\), where \(x_i\ge 0\) for \(1\le i\le n\). What is its number of nonnegative integer solutions when \(n=4\) and \(r=8\)?
\(x_1+x_2+x_3+x_4\lt 8 \iff x_1+x_2+x_3+x_4\le 7\)
加 slack \(y\ge 0\)：\(x_1+x_2+x_3+x_4+y=7\)
\(H(5,7)=\dbinom{11}{7}=\dbinom{11}{4}=\dfrac{11\cdot10\cdot9\cdot8}{4\cdot3\cdot2\cdot1}\)
\(330\)
Derive the solution for \(a_n\) that satisfies the recurrence equation \(a_n=3a_{n-1}+n\) with \(a_0=1\).
齊次：\(r=3\) \(a_n^{(h)}=A\cdot 3^n\)
特解：設 \(a_n^{(p)}=Cn+D\)
\(Cn+D-3\big(C(n-1)+D\big)=n\)
\(-2Cn+(3C-2D)=n\) → \(C=-\tfrac12,\ D=-\tfrac34\)
\(a_n=A\cdot3^n-\tfrac12 n-\tfrac34\)，\(a_0=1\Rightarrow A=\tfrac74\)
驗 \(a_1\)：\(\tfrac{21}{4}-\tfrac24-\tfrac34=4=3\cdot1+1\)
\(a_n=\tfrac74\cdot3^n-\tfrac12 n-\tfrac34\)
The generating function in partial fraction decomposition for the above recurrence equation is ______. (Note that expressions like \(\dfrac{x-8}{(x-3)^2}-\dfrac{9}{x-1}\) are not partial fraction decompositions.)
\(A(x)=\sum_{n\ge0}a_nx^n\)，遞迴式兩邊乘 \(x^n\)、對 \(n\ge1\) 加總：
\(\big(A(x)-1\big)-3xA(x)=\dfrac{x}{(1-x)^2}\)
\(A(x)=\dfrac{1-x+x^2}{(1-3x)(1-x)^2}=\dfrac{\alpha}{1-3x}+\dfrac{\beta}{1-x}+\dfrac{\gamma}{(1-x)^2}\)
\(1-x+x^2=\alpha(1-x)^2+\beta(1-3x)(1-x)+\gamma(1-3x)\)
\(x=1\)：\(1=-2\gamma\) → \(\gamma=-\tfrac12\)
\(x=\tfrac13\)：\(\tfrac79=\tfrac49\alpha\) → \(\alpha=\tfrac74\)
\(x^2\) 係數：\(1=\alpha+3\beta\) → \(\beta=-\tfrac14\)
對第 4 題：\([x^n]=\tfrac74 3^n-\tfrac14-\tfrac12(n+1)\)，一致
\(\dfrac{7/4}{1-3x}-\dfrac{1/4}{1-x}-\dfrac{1/2}{(1-x)^2}\)
Prove the following inequality: \(\dbinom{n}{\lfloor n/2\rfloor}\ge\dfrac{2^n}{n}\), where \(2\le n\).
\(\sum_{k=0}^{n}\binom nk=2^n\)
把 \(\binom n0+\binom nn=2\) 併成一項，共 \(n\) 項：
\(2,\ \binom n1,\ \binom n2,\ \ldots,\ \binom n{n-1}\)，總和 \(2^n\)
\(\binom n{\lfloor n/2\rfloor}\ge\binom nk\ \ \forall k\)，且 \(\binom n{\lfloor n/2\rfloor}\ge\binom n1=n\ge2\)
⇒ \(\binom n{\lfloor n/2\rfloor}\) 是這 \(n\) 項中最大的
最大值 \(\ge\) 平均值：\(\dbinom n{\lfloor n/2\rfloor}\ge\dfrac{2^n}{n}\)
得證
If the polynomial function \(f(x)=ax^4+bx^3+cx^2+dx+e\) satisfies
\(f(-2)=150,\ f(-1)=16,\ f(0)=2,\ f(1)=18,\ f(2)=166,\)
then \(a,b,c,d,e\) are ___, ___, ___, ___, ___, respectively.
\(f(0)=e=2\)
\(f(x)+f(-x)=2(ax^4+cx^2+e)\)
\(x=1\)：\(34=2(a+c+2)\) → \(a+c=15\)
\(x=2\)：\(316=2(16a+4c+2)\) → \(4a+c=39\)
→ \(a=8,\ c=7\)
\(f(x)-f(-x)=2(bx^3+dx)\)
\(x=1\)：\(2=2(b+d)\) → \(b+d=1\)
\(x=2\)：\(16=2(8b+2d)\) → \(4b+d=4\)
→ \(b=1,\ d=0\)
\(8,\ 1,\ 7,\ 0,\ 2\)
The nullities of the matrices \(BB^T-\lambda I\) for \(\lambda=0,1,2,3,4\)
\(B=\begin{bmatrix}0&0&1&0\\-2&0&0&0\\0&0&0&0\\0&0&0&-1\\0&0&-1&0\end{bmatrix}\)
are ___, ___, ___, ___, ___, respectively.
\(B\) 的 column 兩兩正交，算 \(B^TB\)（4×4）比較快：
\(B^TB=\operatorname{diag}(4,\,0,\,2,\,1)\)
\(BB^T\) 與 \(B^TB\) 非零 eigenvalue 相同，\(BB^T\) 是 5×5
→ \(BB^T\) 的 eigenvalue：\(4,\,2,\,1,\,0,\,0\)
\(BB^T\) 對稱 ⇒ 可對角化，nullity \(=\) 重數
\(2,\ 1,\ 1,\ 0,\ 1\)
Let \(A=\begin{bmatrix}2&0&0&2\\0&0&0&0\\0&0&0&0\\2&0&0&2\end{bmatrix}\). Let
\(U=\left\{a\begin{bmatrix}1\\0\\1\\0\end{bmatrix}+b\begin{bmatrix}0\\1\\0\\1\end{bmatrix}+c\begin{bmatrix}-1\\0\\1\\0\end{bmatrix}: a,b,c\in\mathbb R\right\}.\)
The numbers of elements \(-2,-1,0,1,2\) in a matrix \(B\) with \(Bx=\begin{cases}Ax & \text{if } x\in U\\ 0 & \text{if } x\in U^\perp\end{cases}\) are ___, ___, ___, ___, ___, respectively.
\(U=\operatorname{span}\{e_1,\ e_3,\ e_2+e_4\}\)，\(U^\perp=\operatorname{span}\{e_2-e_4\}\)
\(Be_1=Ae_1=(2,0,0,2)^T\)
\(Be_3=Ae_3=0\)
\(B(e_2+e_4)=A(e_2+e_4)=(2,0,0,2)^T\)
\(B(e_2-e_4)=0\)
→ \(Be_2=Be_4=(1,0,0,1)^T\)
\(B=\begin{bmatrix}2&1&0&1\\0&0&0&0\\0&0&0&0\\2&1&0&1\end{bmatrix}\)
\(0,\ 0,\ 10,\ 4,\ 2\)
If \(A=\begin{bmatrix}0&-0.5&0&0&0\\0&0&0&0&0\\0.5&0&0&0&-0.5\\0&0&0&-1&0\end{bmatrix}\),
then the numbers of elements \(-2,-1,0,1,2\) in a matrix \(B\) with
\(ABA=A,\quad BAB=B,\quad (AB)^T=AB,\quad (BA)^T=BA\)
are ___, ___, ___, ___, ___, respectively.
四個條件 ⇒ \(B=A^{+}\)（Moore–Penrose）
\(A\) 的 row：\(r_1,r_3,r_4\) 兩兩正交，\(r_2=0\)
\(AA^T=\operatorname{diag}\!\left(\tfrac14,\,0,\,\tfrac12,\,1\right)\)
\(A^{+}=A^T(AA^T)^{+}=A^T\operatorname{diag}(4,\,0,\,2,\,1)\)
\(B=\begin{bmatrix}4r_1^T & 0 & 2r_3^T & r_4^T\end{bmatrix}=\begin{bmatrix}0&0&1&0\\-2&0&0&0\\0&0&0&0\\0&0&0&-1\\0&0&-1&0\end{bmatrix}\)
跟第 8 題的 \(B\) 是同一個矩陣
\(1,\ 2,\ 16,\ 1,\ 0\)
The numbers of elements \(0,1,2,3,4\) in a Jordan normal form of the matrix
\(A=\begin{bmatrix}4&4&2&1\\0&0&-1&-1\\-1&-1&2&0\\1&1&-1&1\end{bmatrix}\)
are ___, ___, ___, ___, ___, respectively.
col 1 \(=\) col 2 ⇒ \(\lambda=0\)
\(A-I\)：row 3 \(=-\)row 4 ⇒ \(\lambda=1\)
\(\operatorname{tr}A=7\) ⇒ \(\lambda_3+\lambda_4=6\)
2×2 主子式和：\(0+10+3-1+1+2=15=\lambda_3\lambda_4+(\lambda_3+\lambda_4)\)
⇒ \(\lambda_3\lambda_4=9\) ⇒ \(\lambda_3=\lambda_4=3\)
\(\operatorname{rank}(A-3I)=3\) ⇒ GM \(=1\lt\) AM \(=2\)
\(J=\begin{bmatrix}0&0&0&0\\0&1&0&0\\0&0&3&1\\0&0&0&3\end{bmatrix}\)
\(12,\ 2,\ 0,\ 2,\ 0\)