3.可以請助教推導一下Em和Lm嘛, Em是n個條件洽符合m個的方法數,還蠻好想的,但是我不太確定自己的證明方式對不對,因為照著課本排容原理的證明方式,感覺就只是把值帶進去驗證等式而已,所以希望助教說明或證明一下,像Lm公式就不是很好想,請助教列一下推導過程,感恩
7.請問一下1-89題目是要我們證明一定可以找到n個連續組合數對嘛？
8.請問一下1-92最後一句話2^kb mod (2^b-1)為什麼等於1？如何從過程得知？
9.請問一下助教 範例6可以這樣寫嘛？
訂閱：
張貼留言 (Atom)
5 則留言:
1. 以長度為4的cycle為例, 算cycle的個數就相當於是在m個點中取4個點作環狀排列, 然後因為順時針逆時針是視為一樣的, 所以要乘上1/2, 那麼總數就是c(m,4)3!/2, 最後再把cycle長度為3,4,...,m的結果全部加起來就是答案, 所以總數就是
[ c(m,3)*2! + c(m,4)*3! + ... + c(m,m)*(m-1)! ] / 2
2. 只要找到適當的函數就沒問題了, 沒有絕對的解法, 這點老師上課時應該也有提醒過, 不過像這種要對應到整個實數軸的函數, 大部分同學都不太會找, 所以才會覺得不直觀, 主要還是因為大家對於函數都不太熟悉
3. 這裡我是覺得推導的過程反而不是那麼重要, 因為證明的過程只是把歸納的結果用公式寫下來而已, 寫起來比較繁瑣, 用m=3的case去想, 了解那個公式在想法上是怎麼來的即可, 重點是要會用
4. k=1會有問題, 像是任給一個連通的tree就不會有cycle
5. 這題算是比較難的, 找同胚的確用肉眼看並不容易判斷, 不過一般會考出來的圖, 通常拉一拉扯一扯不至於太難判斷, 或是用你說的那個不等式也是我們常用的方法
6. 是的, 謝謝你幫忙勘誤
7. 沒錯
8. 提示: 這和老師上課在證明 "若2^n-1是質數, 則n是質數(p1-74範例5)" 所用到的分解有關
非常感謝助教
助教不好意思再請問一下 我的第二個問題 範例四 為何f3 要取e^x+a 遇到這種題目是否就是用1/x, tan,e 這三種函數去想辦法證明？ 如果是那請問要如何選用？
還有第九小題新增的 感謝
2. 想法上是因為比 a 大的實數都要被對到, 又因為e^x可將所有的實數都mapping到一個正實數, 且值域就是所有的正實數(i.e., 1-1且onto), 所以想法就是定義 e^x+a 來將每一個實數都mapping到一個比 a 大的實數, 且這個函數為1-1且onto
要證兩個無限集的cardinality相等, 選函數的方法不是從資料庫裡把每一個你會的都拿來慢慢套, 最主要的還是要先想清楚的定義域和對應域是甚麼, 以及找出來的對應函數是否滿足one-to-one且onto的性質, 一次對不出來就找幾個函數合成
9. 範例6其實是一個很經典的定理噢, 叫做Cantor's theorem, 它的證明也很經典, 概念上其實和老師在上課時教過的對角線論證法差不多
你的證法在 A 為有限的時候沒有問題, 但這個定理最主要想闡述的重點其實是, 當 A 為infinite set時, A的power set的cardinality也一定會嚴格大於 A 的cardinality, 此時就不能像這樣用數學歸納法來討論了
感謝助教詳解
張貼留言