Processing math: 100%

Saturday, June 19, 2010

391P Homework

Problem. Let A,B,C be sets. f:AB is a surjection and g:AC is a function such that if f(a1)=f(a2), then g(a1)=g(a2). Prove that there exists a unique function h:BC such that hf=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) 的問題,看看 (ex1)3=e3x3e2x+3ex1xn/n! 的系數是甚麼?剛巧也是 3n3×2n+3,原因是 (x+x22!+)(x+x22!+)(x+x22!+)=n=3(x1+x2+x3=nx1,x2,x31n!x1!x2!x3!)xnn!.
由此可見,xn/n! 的系數就是把 (n12) (這個數字與我們的運算無關) 個組合的排列加起來所得的結果!另外我們已證明x1+x2+x3=nx1,x2,x311x1!x2!x3!=3n3×2n+3n!. 類似手法可證得更 General 的結果 (例如 (ex1)k=)。

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

No comments:

Post a Comment