1.Determine the number of four-element subsets of S = {1,2 ,3,......,15}
contaun no consecutive integers.
2. (1+x^2+x^4)^5 , how many terms are there? (是不是只能展開看有幾項~?)
3. The nuver of partitions of {1,2,3,4,5} into three blocks is [5 3]^t = 25
The total number of functions f: {1,2,3,4,5} -> {1,2,3,4} with |f({1,2,3,4,5})| = 3
is ?
ans: 4 x 25 x6 (看不懂)
8 則留言:
1. 假設subset中的4個elements由小到大依序為x1,x2,x3,x4, 1≦x1＜x2＜x3＜x4≦15
令 y1=x1-1, y2=x2-x1, ..., y5=15-x4, 則 y1+y2+...+y5=14, 其中 y1,y5≧0, y2,y3,y4≧2, 再用generating function求解即可, 最後解出來 x^14 之係數為 495
2. 也不用真的展開, 從式子不難觀察出expansion裡面會有 1,x^2,x^4,...,x^20 這些terms, 所以總共有 11 個
3. 你打的東西我有點看不太懂, 不過我猜nuver是number, 然後符號[5 3]^t就是Stirling numbers of the second kind, 也就是 S(5,3), 但其實通常對於second kind我們習慣用的括號是{}, first kind才是[], 書上也是這樣訂的
這邊因為題目中定義的函數等同於是將 5 個elements放進 3 個相異箱子不允許空箱, 若是先把箱子視為相同, 則方法數就是S(5,3)=25, 乘以 4 是因為要從 4 個箱子中取出 3 個來放東西, 乘以 6 是因為那三個箱子是相異, 所以要做排列(3!), 也就是說 25*6 其實就是 onto(5,3)
請問助教
第一題想用遞迴解
要怎麼令才會對呢?
這和我們以往看到的計算不連續的"所有"subset是不一樣的, 因為這邊還限制了subset的大小, 若討論單一個元素取或不取恐怕無法討論出遞迴的形式, 所以我目前並沒有想到什麼有效的遞迴解法
1. 我記得老師有說
1≦x1＜x2＜x3＜x4≦15 不是應該是C(15,4)，遞增的算法~?
2. 如果括號內有負號還是要展開檢查會不會被消掉? 還是不用?
3. 97台大電機的題目，我原文照打上去@@
這樣講我懂了~原來是S(m,n)
謝謝助教
1.因為有限制不能是連續的,所以不能那樣寫
2.有負號應該要額外考慮,看有沒有消除
不懂，所以主要限制部分在於
y1,y5≧0, y2,y3,y4≧2嗎?
好難懂，x→y變數的想法是什麼?
y1+y2+...+y5=14的意義是什麼?
變成五個變數跟要取的4的~~"
有點轉不過來
如果你說用老師講的方法去求,那麼可能求出來是 1,2,3,4這樣不符合
助教用的方法則是把連續取出來的可能給排除了
你可以把問題想像成是在一個從 1 到 15 的數線上, x_i 是我們要在數線上擺標示的位置, 而如果我們想要把這種可以有幾種放標示的方法formulate成非負整數解個數, 也就是放東西的問題, 那麼我們應該要考慮的是每個標示x_i之間區間的加總要是15-1=14, 而其中兩兩標示之間的區間就是 y_i, x_i的加總是不固定的, 但區間就沒有這個問題, 這就是我們之所以要轉成 y_i 的想法
至於是要套組合公式還是用生成函數, 區別在於組合公式比較弱, 因為對於可以放幾個東西在箱子裡我們並不好控制, 相較之下生成函數就比較好用, 因為每個箱子要放幾個我們都可以調整
張貼留言