Re: [高中] 排列組合

[Vulpix (Sebastian)]

※ 引述《HeterCompute (異質運算)》之銘言：
: ※ 引述《stanley413 (無與倫比)》之銘言：
: : 請教版上大大，這題排列組合該如何解題，謝謝版友不吝指教。
: : https://i.imgur.com/HU5fR9R.jpg
: 我是先從雙方1人 2人 3人觀察規律，得知：
: 1.勝方如果n敗，只考慮敗方安排方式就是7!*C(6+n)取n
: 2.雙方都有可能當勝方，所以計算結果*2，唯一的例外是如果雙方6勝6敗，
: 最後一場誰贏無所謂，比賽安排方式相同
: 3.勝方如果n敗，那假如固定敗方順序，勝方的安排方式有P7取n+1種
: 所以答案是：
: https://i.imgur.com/0cO2Xk8.png
: 算出來的結果就是53050042080

還可以用遞迴關係看。

用兩個變數，比較好寫出關係式。

a(m,n) = 甲隊 m 人對乙隊 n 人的方法數

首先是 a(1,1) = 1

來算一般的 a(1,n)，甲隊一人單挑乙隊 n 人的 handicap match。(n>1)

甲隊第一場直接輸掉的情形有 n 種，

如果成功擊敗第一人的話就還有 a(1,n-1) 種對戰組合。

所以 a(1,n) = n + n*a(1,n-1) = a(n,1)

因此，https://i.imgur.com/Vu52EGC.png

然後是更一般的 a(m,n)。(m,n>1)

一樣先看第一場，如果甲隊先輸一場，那就還有 a(m-1,n) 種對戰組合。

所以 a(m,n) = m*a(m-1,n) + n*a(m,n-1) = a(n,m)。


可能會有疑惑的地方是，乙隊的先鋒不是贏了嗎？

乙隊即使先鋒贏了，但我們還沒有指定先鋒是誰，

這個遞迴的意思是在輸掉的同時我們才知道乙隊先鋒的身份。

想像成蒙面柔道賽，決出勝負以後輸家要脫面具。


總之遞迴下去，最後的答案就是 a(7,7) = 53050042080

https://i.imgur.com/vXfMqBE.png

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 163.13.112.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1623757844.A.AC3.html
推 HeterCompute: To recurse, divine. 推遞迴解法
我覺得我把賽制搞得好奇怪。
※ 編輯: Vulpix (163.13.112.58 臺灣), 06/15/2021 23:19:30
推 LPH66       : 這個 a(1,n) 數列長這樣 http://oeis.org/A007526
推 sunev       : a(m,n) = m*a(m-1,n) + n*a(m,n-1) = a(n,1) ?
cap被抓到了。
※ 編輯: Vulpix (163.13.112.58 臺灣), 06/16/2021 01:28:51