n个数中取r个数,这r个数两两之间的差要大于等于k,一共有几种取法

Question

n个数中取r个数,这r个数两两之间的差要大于等于k,一共有几种取法

Answer 1

n个数是连续整数吧,这样不算难~通过适当的变量替换,可以化为一类基本的求不定方程解组数的问题.结论是C(n+k+r-kr-1,r),其中C(n,k)表示n选k的组合数.
重述一下题目：
设这n个数是0~n-1.r个数从小到大排列为x(1),x(2)…x(r).
要求：x(i)为非负整数,x(i)-x(i-1)≥k,x(r)≤n-1.
做变量替换：y(1)=x(1); y(i)=x(i)-x(i-1)-k (2≤i≤r); y(r+1)=n-1-x(r).
则y(1)+…+y(r)+y(r+1)=n+k-kr-1,y(i)为非负整数.
另一方面,对于任意一组满足上上述要求的y(1)…y(r+1),
令x(i)=y(1)+…+y(r)+(i-1)k (1≤i≤r),x(i)合乎题意.
于是问题归结为求方程y(1)+…+y(r+1)=n+k-kr-1非负整数解的组数,这是一个基本问题.
令z(i)=y(i)+1,可以化为求方程z(1)+…+z(r+1)=n+k+r-kr正整数解的组数.
由“挡板法”可知答案为C(n+k+r-kr-1,r).