Re: [中學] 排列組合-不同物選取至少n個連續之方法數
※ 引述《JohnMash (Paul)》之銘言：
: ※ 引述《KengiBon (誠徵籃球球友)》之銘言：
: : 題目:
: : 有m個有編號的座位 選取k個座位
: : 且k個座位中至少要有n個連續的座位
: : 請問所有可能選取的情形有幾種?
: First, take n fixed
: Assume the answer N(m,k)
: (i) there exists at least continuous n chairs already been chosen
: in the first m-1 chairs and the mth NOT been chosen.
: The number of Case (i) is N(m-1,k)
: (2) there are NO continuous n chairs been chosen in the first m-1
: chairs,
: but the (m-1)th,(m-2)th,...,(m-n+1)th chairs been chosen
: and the (m-n)th chair NOT been chosen,
: and in the first (m-n-1) chairs there are NO n continuous
: chairs been chosen.
: The number of Case (ii) is 2^{m-n-1}-N(m-n-1,k-n)
: ---------------------------------------------------------------------
: Hence,
: N(m,k)=N(m-1,k)+2^{m-n-1}-N(m-n-1,k-n)
: assume, k-n=q, q>=0
: N(1,k)=N(2,k)=....=N(k-1,k)=0
: ----------------------------------------------------
: N(k,k)=1
: ------------------------------------------------
: when n+1<=k<=m<=2n then -1<=m-n-1<=n-1
: then N(m-n-1,k-n)=0
: Hence, N(m,k)=N(m-1,k)+2^{m-n-1}
: N(m,k)=1+2^{m-n-1}+2^{m-n-2}+....+2^{k-n}
: ---------------------------------------------------------
感謝你的解答^^
但好像有點問題，這裡有一些範例和答案
m=5,k=3,n=2 為9種
m=6,k=3,n=2 為16種
m=5,k=4,n=2 為5種
m=6,k=4,n=2 為15種
m=7,k=4,n=2 為34種
m=6,k=5,n=2 為6種
昨天詢問之下 已經找到2種解答符合上面範例了
1. C(m,k)-H(k+1,m-2k+1)
2. C(m-n,k-n)+(m-n)*C(m-n-1,k-n)
若m>2n，則還需再減掉{1+[m-(n+1)-(n-1)]}*[m-(n+1)-(n-1)]/2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.167.203
討論串 (同標題文章)