关于无K—间隔的组合数

从排列在一条直线上的n个元素中选取m个元素,以f_k(n,m)表示任意两个被选元素的间隔均不为k之方式数。如果这n个元素排列在园周上,则相应的组合数以g_k(m,m)表示。关于这两类组合数,I.Kaplansky于1943年首先研究了k=0时的计数问题,J. Konvalina于1981年应用递归方法得到了k=1时的计数表达式。对于一般的自然数k,这一问题似乎更加复杂。

On the Number of Combinat ions Without k-Separat ions

Let f_k(n, m) denote the number of ways of selecting m objects from n objects arrayed in a line with no two selected having k-spparations (i.e., having exactly k-objects between them) .If the objects are arranged in a circle, the corresponding number is denoted by g_k(n, m) . Kaplansky first published a derivation by recurrence relation for k - 0. Recently, Konvalina derived the enumerative formulae for k =1 by using the similar method . For a general k, this problem is somehow more difficult and complicated.