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