Newsgroups: sci.math
Subject: Re: spaced objects problem
Summary: 
Expires: 
References: <93056.003932SJC2@psuvm.psu.edu>
Sender: 
Followup-To: 
Distribution: 
Organization: Princeton University
Keywords: 

In article <93056.003932SJC2@psuvm.psu.edu> you write:
>
>  Does anyone know a solution to the following problem:
>If 20 objects are      up in a row, from which 6 objects
>must be chosen, but no two may be neighbors, how many choices
>are there?
>

	Well, let's take the general case.  We want to pick a subset S of
{1, 2, 3, ..., n} such that no two elements in S differ by 1, and such that
S contains k elements.  Call a(n,k) the number of ways to pick S.  Then I
get the recurrence relation

a(n, k) = Sum[a(n-1-j, k-1), {j, 1, n-2}]	when k > 1, n > 2k-2
        = Sum[a(j, k-1), {j, 1, n-2}]
a(n, k) = 0					when n <= 2k-2
a(n, 1) = n					when n >= 0

	The solution to this recurrence relation is

a(n, k) = Binomial[n-k+1, k]

It is easily verified by induction.  Solving the recurrence relation from
scratch is a little more work.  :-)

	And the solution to your question is a(20, 6) = 5005.

>
>            What if the stipulation is that there must be a
>minnnnnnnnnnn imum of two objects between each pair of the chosen ones?
>

	Hmm...  Now we want a subset S with the restriction any pair of
elements in S differ by at least d.  Then I get the recurrence relation

b(d, n, k) = Sum[b(d, n-d-1-j, k-1), {j, 1, n-d}]	when k > 1, n > d(k-1)
           = Sum[b(d, j, k-1), {j, 1, n-d}]
b(d, n, k) = 0						when n <= d(k-1)
b(d, n, 1) = n						when n >= 0

	The solution to this more general recurrence relation is

b(d, n, k) = Binomial[n-(d-1)(k-1), k]

if I haven't screwed up the algebra.  As a check, note that in fact

b(2, n, k) = Binomial[n-(2-1)(k-1), k] = Binomial[n-k+1, k] = a(n, k)

--------------------------------------------------------------------------------
David Wagner                                              dawagner@princeton.edu