Re: [中學] 排列組合-不同物選取至少n個連續之方法數
※ 引述《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}
---------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.104.90.32
※ 編輯: JohnMash 來自: 112.104.128.239 (06/07 19:14)
討論串 (同標題文章)