作者JohnMash (Paul)
看板Math
标题Re: [中学] 排列组合-不同物选取至少n个连续之方法数
时间Tue Jun 7 17:36:27 2011
※ 引述《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)