391P Homework

Problem. Let $  A,B,C$ be sets. $  f:A\to B$ is a surjection and $  g:A\to C$ is a function such that if $  f(a_1)=f(a_2)$, then $  g(a_1)=g(a_2)$. Prove that there exists a unique function $  h:B\to C$ such that $  h\circ f = g$.

用返自己對 function ge 認識去做，但做做下硬係覺得怪怪地=.=。

以下為某中學授課員的網誌：
http://johnmayhk.wordpress.com/2010/06/17/double-counting-example/
我們來看看 a(iii) 這道題目，介紹一些新的 technique。(熟悉的人可無視~)

如同網誌所說，利用``容斥原理" (inclusion-exclusion principle)，易得到分子的數目。現在額外地說說 generating function，這裏不需要 pure 課程裏額外的知識。相信有讀 241 的同學可能已接觸過一些 generating function，例如 moment generating function。在組合數學裏有類似的計算技巧。

例如 $  (1+x+x^2+x^3+\cdots+x^8)(x^2+x^3+\cdots+x^8$) 裏，$  x^8$ 的系數, 7, 是有 ``計數" 的意義的。假設這裏有 8 個蘋果及 8 個橙，從中抽 8 個水果且其中最少有 2 個橙 (蘋果數目可 0)，那麼有多少種「抽水」組合？那就是剛剛所提到的 7，即 $  x^8$ 的系數。

回到 a(iii) 的問題，看看 $  (e^x-1)^3 = e^{3x}-3e^{2x}+3e^x-1$ 裏 $  x^n/n!$ 的系數是甚麼？剛巧也是 $  3^n-3\times 2^n+3$，原因是 \[\left(x+\frac{x^2}{2!}+\cdots\right)\left(x+\frac{x^2}{2!}+\cdots\right)\left(x+\frac{x^2}{2!}+\cdots\right)\\=\sum_{n=3}^\infty\left( \sum_{\scriptstyle x_1+x_2+x_3=n\atop \scriptstyle x_1,x_2,x_3\ge 1}\frac{n!}{x_1!x_2!x_3!}\right)\frac{x^n}{n!}.\]
由此可見，$  x^n/n!$ 的系數就是把 $  \displaystyle \binom{n-1}{2}$ (這個數字與我們的運算無關) 個組合的排列加起來所得的結果！另外我們已證明\[  \sum_{\scriptstyle x_1+x_2+x_3=n\atop \scriptstyle x_1,x_2,x_3\ge 1}\frac{1}{x_1!x_2!x_3!}=\frac{3^n-3\times 2^n+3}{n!}.
\] 類似手法可證得更 General 的結果 (例如 $  (e^x-1)^k =\dots $)。

ps. 大劑，點解 wordpress 有 pingback 呢樣野。