## Re: set problem

Expand Messages
• ... can you solve my problem?
Message 1 of 5 , Mar 1, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>
wrote:
> Let A={1,2,...,n}.Can you find the number of r-element subset of A
> that not included consecutive integers?
can you solve my problem?
• No. But, when r = 1, the number of required subsets equals n. When r = 2, the number of subsets equals [n!(n-1)!]/2 - (n-1). And so on. When r = n-1, the
Message 2 of 5 , Mar 3, 2004
• 0 Attachment
No. But, when r = 1, the number of required subsets equals n. When
r = 2, the number of subsets equals [n!(n-1)!]/2 - (n-1). And so
on. When r = n-1, the number of required subsets equals 0, except
in the cases of n=1, n=2 and n=3. The trick is to find the total
number of subsets containing consecutive numbers, and then do the
subtraction.

--- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>
wrote:
> --- In mathforfun@yahoogroups.com, "alpercay2001"
<alpercay2001@y...>
> wrote:
> > Let A={1,2,...,n}.Can you find the number of r-element subset of
A
> > that not included consecutive integers?
> can you solve my problem?
• We were asked to find the number of ways in which r integers can be selected from 1,2,..,n subject to the constraint that no two consecutive integers are
Message 3 of 5 , Mar 10, 2004
• 0 Attachment
We were asked to find the number of ways in which r integers can be
selected from 1,2,..,n subject to the constraint that no two
consecutive integers are selected.
The answer is C(n-r+1, r), the number of combinations of n-r+1
objects taken r at a time.

Lemma: The number of distinct solutions of x_1 + x_2 + ... + x_k = n,
where x_1, ..., x_k are positive integers, is C(n-1, k-1).
Proof:
Using a marker you can erase, write n X's separated by vertical bars,
like this: X|X|X|....|X, so there are n-1 vertical bars. Select k-1
of the vertical bars and erase the rest, a selection that can be
made in C(n-1, k-1) ways. The selected bars divide the Xs into k
groups, each group containing at least one X. Working from left to
right, let x_1 = the number of Xs in the first group, x_2 = the
number of Xs in the second group, etc. The total number of Xs is n,
so x_1 + x_2 + ... + x_k = n. Conversely, given a solution to the
equation, we can generate a selection of k-1 of the vertical bars; so
the number of solutions of the equation is C(n-1, k-1).

Now back to the original problem. Write down the integers 1 to n from
left to right and circle the r selected integers (with no two
consecutive integers selected)say the selected integers are i_1,
i_2, ..., i_r. We proceed to count the non-circled integers. Let
x_1 = the number of non-selected integers to the left of i_1 = i_1-1
x_2 = the number of non-selected integers between i_1 and i_2 = i_2-
i_1-1
x_3 = the number of non-selected integers between i_3 and i_2 = i_3-
i_2-1
...
x_r = the number of non-selected integers between i_r and i_(r-1) =
i_r-i_(r-1)-1
x_r+1 = the number of non-selected integers to the right of x_r = n-
x_r
so we have
x_1 >= 0, x_(r+1) >= 0, and x_i >= 1 for i = 2,3, ..., r. Since the
x's account for all the non-selected integers,
x_1 + x_2 + ... + x_(r+1) = n  r
We are almost in position to apply the lemma, except that x_1 and x_
(r+1) don't fit the conditions. So we substitute x_1 =
y_1-1 and x_(r+1) = y_(r+1) 1, with the result
y_1 + x_2 + .... + x_r + y_(r+1) = n  r + 2
All the x's and y's in this equation are positive, so the lemma now
applies, and the total possible number of solutions of the equation
is C(n-r+2-1, r+1-1) = C(n-r+1, r). Given a solution of the
equation, we can reverse the process and generate an acceptable
selection; so the total number of acceptable selections is C(n-r+1,
r).

--- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>
wrote:
> Let A={1,2,...,n}.Can you find the number of r-element subset of A
> that not included consecutive integers?
• Here is another proof. Let B(n,r) be the number of r-subsets of {1,2,...,n} containing no two consecutive integers. Then B(n,0)=1 and B(n,1)=n. Also B(n,r) = B
Message 4 of 5 , Mar 10, 2004
• 0 Attachment
Here is another proof.

Let B(n,r) be the number of r-subsets of {1,2,...,n} containing no
two consecutive integers. Then B(n,0)=1 and B(n,1)=n. Also B(n,r) = B
(n-2,r-1) + B(n-1,r), since every r-subset of {1,2,...,n} either
contains n, which says that n-1 is not in the subset and we have an
(r-1)-subset of {1,2,...,n-2}, or doesn't contain n, which says that
we have an r-subset of {1,2,...,n-1}. These conditions uniquely
determine B(n,r), and since C(n-r+1,r) also satisfies the recursion,
we must have that B(n,r)=C(n-r+1,r).

--- In mathforfun@yahoogroups.com, jwwarrenva <no_reply@y...> wrote:
> We were asked to find the number of ways in which r integers can be
> selected from 1,2,..,n subject to the constraint that no two
> consecutive integers are selected.
> The answer is C(n-r+1, r), the number of combinations of n-r+1
> objects taken r at a time.
>
> Lemma: The number of distinct solutions of x_1 + x_2 + ... + x_k =
n,
> where x_1, ..., x_k are positive integers, is C(n-1, k-1).
> Proof:
> Using a marker you can erase, write n X's separated by vertical
bars,
> like this: X|X|X|....|X, so there are n-1 vertical bars. Select k-
1
> of the vertical bars and erase the rest, a selection that can be
> made in C(n-1, k-1) ways. The selected bars divide the Xs into k
> groups, each group containing at least one X. Working from left to
> right, let x_1 = the number of Xs in the first group, x_2 = the
> number of Xs in the second group, etc. The total number of Xs is
n,
> so x_1 + x_2 + ... + x_k = n. Conversely, given a solution to the
> equation, we can generate a selection of k-1 of the vertical bars;
so
> the number of solutions of the equation is C(n-1, k-1).
>
> Now back to the original problem. Write down the integers 1 to n
from
> left to right and circle the r selected integers (with no two
> consecutive integers selected)say the selected integers are i_1,
> i_2, ..., i_r. We proceed to count the non-circled integers. Let
> x_1 = the number of non-selected integers to the left of i_1 = i_1-1
> x_2 = the number of non-selected integers between i_1 and i_2 = i_2-
> i_1-1
> x_3 = the number of non-selected integers between i_3 and i_2 = i_3-
> i_2-1
> ...
> x_r = the number of non-selected integers between i_r and i_(r-1) =
> i_r-i_(r-1)-1
> x_r+1 = the number of non-selected integers to the right of x_r = n-
> x_r
> so we have
> x_1 >= 0, x_(r+1) >= 0, and x_i >= 1 for i = 2,3, ..., r. Since
the
> x's account for all the non-selected integers,
> x_1 + x_2 + ... + x_(r+1) = n  r
> We are almost in position to apply the lemma, except that x_1 and x_
> (r+1) don't fit the conditions. So we substitute x_1 =
> y_1-1 and x_(r+1) = y_(r+1) 1, with the result
> y_1 + x_2 + .... + x_r + y_(r+1) = n  r + 2
> All the x's and y's in this equation are positive, so the lemma now
> applies, and the total possible number of solutions of the equation
> is C(n-r+2-1, r+1-1) = C(n-r+1, r). Given a solution of the
> equation, we can reverse the process and generate an acceptable
> selection; so the total number of acceptable selections is C(n-r+1,
> r).
>
> --- In mathforfun@yahoogroups.com, "alpercay2001"
<alpercay2001@y...>
> wrote:
> > Let A={1,2,...,n}.Can you find the number of r-element subset of
A
> > that not included consecutive integers?
Your message has been successfully submitted and would be delivered to recipients shortly.