2010-10-20

生成函數的問題

1.Determine the number of positive integer solutions of x1 + x2 + x3 + x4 + x5 = 45 where xi must be exactly divided by 3 for i = 1,2,3,4,5

Ans : A(x) = (x^3 + x^6 + x^9 + ..... ) ^ 5,為何不是 (1 + x^3 + x^6 + x^9 + ..... ) ^ 5,0不是被所有數整除嗎?

2.Suppose we need to count the strings of length 7 over the alphabet A = {c,d,e,n,q,s,u} that ends with either s or c and contains both q and u in sequence. Please count the total number of strings

這題是P4-41範例1用指數生成函數解,A(x) = (e^x - 1)^2 (e^x)^5,這樣的解法有辦法確定s或c在字尾嗎?

3.Find the number of n-digit words generated from the alphabet {0,1,2,3,4} in each of which the total number of 0's and 1's is even

這題解答是寫說0和1的總和為偶數,可是英文題意看起來好像是0為偶數個且1為偶數個的狀況,是我英文有問題嗎?若題目改成是0或1為偶數的話,英文會是怎麼寫呢?

5 則留言:

線代離散助教(wynne) 提到...

1. 根據題意, 他是希望你把 45 拆成 5 個正整數相加, 然而如果是某個 xi 取 x^0, 那就代表我們允許這個 xi 為 0, 這樣的話會少於 5 個正整數

2. 這邊列出來的指數生成函數是還沒有把 s,c 考慮進去, 書上是一直寫到最後一行的 2*39962 那裡才把這兩個也一併考慮進去

3. 他寫 "the total number of 0's and 1's is even" 指的不是0為偶數個且1為偶數個, 而是 "0 與 1 的個數的和為偶數"

如果他想表達的是 "0為偶數個且1為偶數個", 他應該會寫成像是 "the number of 0's and the number of 1's are both even" 或是 "the number of both 0's and 1's is even"; 如果他想表達的是 "0為偶數個或1為偶數個", 句子大概會長的想這樣: "the number of 0's or the number of 1's ..."

胖胖呆 提到...

第2題他真正在做排列的是X︿6/6!那一個式子 所以做完已經把6個數排好了 最後那一個*2才是討論最後一個位址的S C狀況


是這樣解釋嗎???

線代離散助教(wynne) 提到...

是的

Sean 提到...

感謝助教的解答~~我大概了解了

Jungle 提到...

請問第2題"contains both q and u in sequence", 意思是在這序列中吧, 不是這兩個字元要連續?