[分析] 排列組合

看板Math作者 (QQQQQQQ)時間7年前 (2018/09/30 13:00), 編輯推噓0(0推 0噓 35→)
留言35則, 2人參與, 7年前最新討論串1/1
X1+x2+....+xn =r 其中1<=x1<x2<.....<xn <=r 求解的個數 目前想到是用排容 但是排容不太好作 有沒有其他方法可以轉換這個問題使它變得好寫呢？ ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.253.170 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1538283647.A.5E1.html
→
09/30 13:08, 7年前 , 1F
X2-X1 照這樣減下去，用差距算
09/30 13:08, 1F
→
09/30 14:40, 7年前 , 2F
這樣答案是C(r-1,n-1)跟取正整數的解一樣
09/30 14:40, 2F
→
09/30 14:40, 7年前 , 3F
感覺有點奇怪耶
09/30 14:40, 3F
→
09/30 14:40, 7年前 , 4F
變成x1+x2+....+xn=r這個條件不存在
09/30 14:40, 4F
→
09/30 14:40, 7年前 , 5F
有矛盾的感覺
09/30 14:40, 5F
→
09/30 17:46, 7年前 , 6F
嗯，我說的不太對，不過我剛剛想到的是遞迴
09/30 17:46, 6F
→
09/30 18:11, 7年前 , 7F
從Xn來看，它的最大可能值是r-n(n+1)/2
09/30 18:11, 7F
→
09/30 18:12, 7年前 , 8F
好像也不太對
09/30 18:12, 8F
→
09/30 18:15, 7年前 , 9F
還是對？反正最大可能值的時候就是前面都只跳1
09/30 18:15, 9F
→
09/30 18:16, 7年前 , 10F
所以總共只有一種可能，再來就是釋出1給前面幾個
09/30 18:16, 10F
→
09/30 18:17, 7年前 , 11F
也就是它們這n-2個間隔其中一個可以多跳1
09/30 18:17, 11F
→
09/30 18:19, 7年前 , 12F
再來就依此類推，最後全部加起來
09/30 18:19, 12F
→
09/30 18:34, 7年前 , 13F
只要找到Xn的最小值就可以知道上面這些加起來相當於
09/30 18:34, 13F
→
09/30 18:34, 7年前 , 14F
這n-1個東西加起來要等於多少
09/30 18:34, 14F
→
09/30 19:21, 7年前 , 15F
最大值應該是r-n(n-1)/2
09/30 19:21, 15F
→
09/30 19:29, 7年前 , 16F
好像不該說是Xn的最小值，而是某個餘額
09/30 19:29, 16F
→
09/30 19:36, 7年前 , 17F
不行，不通，當我胡言亂語吧
09/30 19:36, 17F
→
09/30 22:21, 7年前 , 18F
09/30 22:21, 18F
→
09/30 22:21, 7年前 , 19F
不知道這樣轉換有沒有什麼問題@@
09/30 22:21, 19F
→
09/30 22:49, 7年前 , 20F
這是我一開始以為的東西，但是你這樣加下去
09/30 22:49, 20F
→
09/30 22:49, 7年前 , 21F
中間的X_2~X_(n-1)都會不見
09/30 22:49, 21F
→
09/30 22:50, 7年前 , 22F
你這樣寫的最後一項應該叫y_(n-1)
09/30 22:50, 22F
→
09/30 22:58, 7年前 , 23F
當然y_n它們硬湊可以湊成Σx_i，但這樣我反而不會解
09/30 22:58, 23F
→
09/30 22:58, 7年前 , 24F
y組成的那式子了
09/30 22:58, 24F
→
09/30 23:17, 7年前 , 25F
還是說這題是生成函數？
09/30 23:17, 25F
→
10/01 00:27, 7年前 , 26F
這題應該不能用生成函數去解
10/01 00:27, 26F
→
10/01 00:27, 7年前 , 27F
生成函數用來解a<xi<b的問題 其中a.b都是常數
10/01 00:27, 27F
→
10/01 00:27, 7年前 , 28F
如果是變數的話沒辦法令生成函數
10/01 00:27, 28F
→
10/01 00:27, 7年前 , 29F
關鍵應該在於問題的轉換 但是想不到合適的轉換方法
10/01 00:27, 29F
→
10/01 00:27, 7年前 , 30F
這題是不知道104還105的台大資工考古 所以沒有限制
10/01 00:27, 30F
→
10/01 00:27, 7年前 , 31F
方法喔！！
10/01 00:27, 31F
→
10/01 00:41, 7年前 , 32F
我剛剛看Grad-ProbSol板有討論到，104資工數學
10/01 00:41, 32F
→
10/01 00:41, 7年前 , 33F
你可以去看看
10/01 00:41, 33F
→
10/01 00:41, 7年前 , 34F
Grad-ProbAsk才對
10/01 00:41, 34F
→
10/01 00:58, 7年前 , 35F
看到了 感謝 這題當年應該沒多少人對吧@@
10/01 00:58, 35F
‣ 更多 q79236 的文章
文章代碼(AID): #1Ri5X_NX (Math)