Problem. Let A,B,C be sets. f:A→B is a surjection and g:A→C is a function such that if f(a1)=f(a2), then g(a1)=g(a2). Prove that there exists a unique function h:B→C such that h∘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+x2+x3+⋯+x8)(x2+x3+⋯+x8) 裏,x8 的系數, 7, 是有 ``計數" 的意義的。假設這裏有 8 個蘋果及 8 個橙,從中抽 8 個水果且其中最少有 2 個橙 (蘋果數目可 0),那麼有多少種「抽水」組合?那就是剛剛所提到的 7,即 x8 的系數。
回到 a(iii) 的問題,看看 (ex−1)3=e3x−3e2x+3ex−1 裏 xn/n! 的系數是甚麼?剛巧也是 3n−3×2n+3,原因是 (x+x22!+⋯)(x+x22!+⋯)(x+x22!+⋯)=∞∑n=3(∑x1+x2+x3=nx1,x2,x3≥1n!x1!x2!x3!)xnn!.
由此可見,xn/n! 的系數就是把 (n−12) (這個數字與我們的運算無關) 個組合的排列加起來所得的結果!另外我們已證明∑x1+x2+x3=nx1,x2,x3≥11x1!x2!x3!=3n−3×2n+3n!. 類似手法可證得更 General 的結果 (例如 (ex−1)k=…)。
ps. 大劑,點解 wordpress 有 pingback 呢樣野。
No comments:
Post a Comment