Re: [問題] 請問一個排列組合的問題
※ 引述《KengiBon (誠徵籃球球友)》之銘言：
: ※ 引述《KengiBon (誠徵籃球球友)》之銘言：
: : 題目:
: : 有m個有編號的座位 選取k個座位
: : 且k個座位中至少要有n個連續的座位
: : 請問所有可能選取的情形有幾種?
如果數字不大直接列比較快
以下以m=12, k=7, n=4作例子:
(4,3) 若抽出為4個連續，3個連續
因為沒被選到有12-7=5，數字間有5+1個空格，故有2!/1!1!*C(6,2)種排列方法
(4,3) 2*C(6,2)=30
(4,2,1) 3!*C(6,3)=120
(4,1,1,1) 4*C(6,4)=60
(5,2) 2*C(6,2)=30
(5,1,1) 3*C(6,3)=60
(6,1) 2*C(6,2)=30
(7) 1*C(6,1)=6
總共有336種方法
或者以全部方法減掉沒有n個連續的來做，不加贅述。
----------------------------------------------------------------
公式解:
首先將選上的k個排好，產生k+1個空格，將沒選上的m-k個放入這些空格內
故不要求N個連續的話，總共有 H(k+1,m-k)方法
剛好x個連續有(k-x+1)組
k+1個空格若有x-1個連續為0則將使數列有x個數字連續，故還能變化的只剩k+1-(x-1)
=k-x+2空格
(1)首尾兩組
為了使剛好有x個連續，故緊接第一組後的空格及在最後一組前面的空格必須大於>=1
因此: y1+y2+....+yk-x+2=m-k 其中某一格必須大於一
(y1-1)+y2+....+yk-x+2=m-k-1 故有H(k-x+2,m-k-1)種方法
總共為 2*H(k-x+2,m-k-1)
(2)非首尾兩組 總共有k-x+1-2=k-x-1組
因非首尾兩組，故緊鄰連續X數字連續的前後兩格都必須>=1
因此: y1+y2+....+yk-x+2=m-k 其中兩格要大於一
(y1-1)+(y2-1)+.....+yk-x+2=m-k-2 故有H(k-x+2,m-k-2)種方法
總共為 (k-x-1)*H(k-x+2,m-k-2)
但當x=k時，只會有一組，因此為C(m-k+1,1)
故整個公式為
C(m-k+1,1)+Σ[2*H(k-x+2,m-k-1)+(k-x-1)*H(K-x+2,m-k-2)]
=C(m-k+1,1)+Σ[2*C(m-x,m-k-1)+(k-x-1)*C(m-x-1,m-k-2)], x=n~k-1
以下以m=12, k=7, n=4作例子:
x=4, 2*C(8,4)+2C(7,3)=210
x=5, 2*C(7,4)+1C(6,3)=90
x=6, 2*C(6,4)+0C(5,3)=30
x=7, C(6,1)=6
總共=336
以上公式僅適用於2n>k的時候... 不然x=n時會重複算
我覺得這種題目，真的直接列比較快
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.140.244.183
討論串 (同標題文章)