作者KengiBon (诚徵篮球球友)
看板Math
标题Re: [中学] 排列组合-不同物选取至少n个连续之方法数
时间Wed Jun 8 09:42:48 2011
※ 引述《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