- --- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>

wrote:> Let A={1,2,...,n}.Can you find the number of r-element subset of A

can you solve my problem?

> that not included consecutive integers?

- 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:

A

> > Let A={1,2,...,n}.Can you find the number of r-element subset of

> > 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 selected.

The answer is C(n-r+1, r), the number of combinations of n-r+1

objects taken r at a time.

To show this, we start with a

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

(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.

>

> To show this, we start with a

> 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?