Number of choosing r non-consecutive numbers out of N natural numbers

[kshitij]

Homework Statement

What is the total number of ways of choosing 5 non consecutive numbers from the set of first 15 natural numbers?

Relevant Equations

Number of ways of choosing r out of n things is nCr

I have seen a solution for this question which was as follows,

first out of 15 elements, take away 5, thus there are 11 gaps created for the remaining 10 numbers (say N) as,
_N_N_N_N_N_N_N_N_N_N_
now, now we can insert back the 5 to comply with the non-consecutive stipulation
for which, number of ways=11C5 (answer)

But I can't understand how selection of 5 out of 11 gaps between 10 random numbers will ensure that the chosen numbers will be non-consecutive. If the question was finding the total number of ways for siting 5 boys between 10 girls such that no two boys sit together, then I could understand this solution but how does this method work here and how are these two situations similar?

 

[PeroK]

Homework Statement:: What is the total number of ways of choosing 5 non consecutive numbers from the set of first 15 natural numbers?
Relevant Equations:: Number of ways of choosing r out of n things is nCr

I have seen a solution for this question which was as follows,

first out of 15 elements, take away 5, thus there are 11 gaps created for the remaining 10 numbers (say N) as,
_N_N_N_N_N_N_N_N_N_N_
now, now we can insert back the 5 to comply with the non-consecutive stipulation
for which, number of ways=11C5 (answer)

But I can't understand how selection of 5 out of 11 gaps between 10 random numbers will ensure that the chosen numbers will be non-consecutive. If the question was finding the total number of ways for siting 5 boys between 10 girls such that no two boys sit together, then I could understand this solution but how does this method work here and how are these two situations similar?

Here's a way to look at it. Imagine we are choosing from the first 16 numbers, but are not allowed to choose number 16 (you'll see why we need this soon).

Every number we choose must have a gap after it. We have five sets of $XG$, where $X$ is some number we have chosen and $G$ is the gap after it (this is why we needed number 16 - to manage the case where we pick number 15).

That leaves us 6 remaining gaps. So, every solution is some arrangement of five $XG$'s and six $G$'s. And that is $\binom {11} 5$.

PS if you don't do the trick with number 16, you have two cases:

a) Where number 15 is not picked. We have five $XG$ and five $G$. I.e. $\binom {10} 5$.

b) Where number 15 is picked. We can exclude that and we have four $XG$ and six $G$. I.e. $\binom {10}{6}$.

And $$\binom{10}{5} + \binom{10}{6} = \binom{11}{5}$$

 

[PeroK]

PS I don't follow the logic in the original post.

 

[haruspex]

PS I don't follow the logic in the original post.

The wording is unclear, but the approach is to imagine 21 slots labelled ABAB...A. Identify five of the eleven As as representing the numbers to be chosen and throw away the rest of the As. This leaves 15 slots, which we now populate with 1, 2, 3...

 

[kshitij]

That leaves us 6 remaining gaps

Where did this 6 gaps came from?

 

[haruspex]

Where did this 6 gaps came from?

@PeroK has created a 16th position, which is always a gap. The five numbers to be chosen will each occupy a position and have an associated gap following. That leaves six other positions, all of which will be gaps.

 

[kshitij]

The wording is unclear, but the approach is to imagine 21 slots labelled ABAB...A. Identify five of the eleven As as representing the numbers to be chosen and throw away the rest of the As. This leaves 15 slots, which we now populate with 1, 2, 3...

Did you mean that first we choose random 5 elements, then to make sure that these are non-consecutive we add the numbers 1,2,3... between them which would turn out to be the differences in each element we chose, e.g., if the difference is 1 our selection could be (1,3,5,7,9);(2,4,6,8,10)... if the difference is 2 out selection will look like (1,4,7,10,13)...? Also how are we getting 11C5 from this process?

Edit: Maybe I should focus on understanding PeroK 's method first, maybe then I could understand the other solutions as well

 

[kshitij]

@PeroK has created a 16th position, which is always a gap. The five numbers to be chosen will each occupy a position and have an associated gap following. That leaves six other positions, all of which will be gaps.

So you mean that we started with 16 elements, out of which we chose 10 elements (which include both the gaps and the numbers (XG), so after this we are left with 6 remaining elements and then we considered all of these elements to be gaps (because we required only 5 numbers in our selection but there is no limit on the number of gaps) and so now we arrange 5XG and the remaining 6 elements which are all considered gaps(G) in 11C5 ways (because total such arrangements should be 11!/(5!*6!) {total arrangements for 11 elements out of which 5 are of one type and six are of other}) or did we choose 5 out of the 11 total gaps which we will put in between our 5 previously chosen numbers?

 

[kshitij]

PS I don't follow the logic in the original post.

If you are interested, This was the original solution I was talking about

And this was when I asked them the same question again,

 

[PeroK]

Where did this 6 gaps came from?

Let's look at a typical choice. We'll choose numbers $2, 4, 9, 13, 15$.

I want to change my notation slightly and use $R$ for the six remaining gaps. The encoded choice looks like:

$RXGXGRRRXGRRXGXG$

What we've done is put the X's where the chosen numbers are, put the mandatory gaps G after each chosen number, then filled in the remaining gaps with R.

Now, we might as well replace all the $XG$'s with $N$. So, the choice now looks like:

$2, 4, 9, 13, 15 \leftrightarrow RNNRRRNRRNN$

And we can see that every choice is, therefore, a combination of five N's and six R's. And vice versa. I.e. we have a one-to-one correspondence.

This idea of having an alternative encoding (that is easier to count) is very powerful.

 

[kshitij]

Let's look at a typical choice. We'll choose numbers $2, 4, 9, 13, 15$.

I want to change my notation slightly and use $R$ for the six remaining gaps. The encoded choice looks like:

$RXGXGRRRXGRRXGXG$

What we've done is put the X's where the chosen numbers are, put the mandatory gaps G after each chosen number, then filled in the remaining gaps with R.

Now, we might as well replace all the $XG$'s with $N$. So, the choice now looks like:

$2, 4, 9, 13, 15 \leftrightarrow RNNRRRNRRNN$

And we can see that every choice is, therefore, a combination of five N's and six R's. And vice versa. I.e. we have a one-to-one correspondence.

This idea of having an alternative encoding (that is easier to count) is very powerful.

Yes, that helps a lot. I think I am getting it now, thank you so much.

 

[PeroK]

If you are interested, This was the original solution I was talking about
View attachment 274500

And this was when I asked them the same question again,

I prefer my way!

 

[kshitij]

I prefer my way!

Me too

 

[haruspex]

Did you mean that first we choose random 5 elements, then to make sure that these are non-consecutive we add the numbers 1,2,3... between them

No.
As I wrote, we create 21 slots labelled alternately A and B: ABAB...A.
Now choose any five of the eleven As to be kept and throw away the other six.
We now have 15 slots, labelled in some pattern of A and B, no two As being adjacent.
Now put a 1 in the first slot, 2 in the second, etc. The five labelled A contain the five chosen non consecutive numbers.

 

[kshitij]

No.
As I wrote, we create 21 slots labelled alternately A and B: ABAB...A.
Now choose any five of the eleven As to be kept and throw away the other six.
We now have 15 slots, labelled in some pattern of A and B, no two As being adjacent.
Now put a 1 in the first slot, 2 in the second, etc. The five labelled A contain the five chosen non consecutive numbers.

How is the total number of ways for this process 11C5?
If we are choosing 15 slots out of 21 or if we are removing 6 slots out of 21 then the number ways=21C15=21C6

Edit: Sorry, I missed that we are choosing 5 A's out of the 11 A's so the total number of ways=11C5=11C6.

 

[kshitij]

we create 21 slots

But why take 21 slots in the first place? Is it because like in the original post we first took away 5 elements then we were left with 10 elements and 11 respective gaps between them? But then the 5 elements which took initially didn't even end up in our final selection so what was the thinking behind separating these 5 elements in the beginning?

 

[haruspex]

But why take 21 slots in the first place? Is it because like in the original post we first took away 5 elements then we were left with 10 elements and 11 respective gaps between them? But then the 5 elements which took initially didn't even end up in our final selection so what was the thinking behind separating these 5 elements in the beginning?

To justify the method one has to show a one-one correlation between valid selections of five numbers and selections of five A slots.
It is clear that each selection of five A slots does lead to a valid selection of five numbers. Can you see how to run it backwards from a valid selection of five numbers to a selection of five A slots out of the ten?

Why 21? Because the ten we are not going to choose (though we don't know which they are yet) create 11 places the chosen ones might fit.

 

[kshitij]

Why 21? Because the ten we are not going to choose (though we don't know which they are yet) create 11 places the chosen ones might fit.

That means these 21 elements comprise of the ones we won't even choose and yet we will end up with a set of 5 non-consecutive numbers from this set?

let me try to understand this step by step,

STEP 1: Take the 10 elements which will not end up in the final selection and label them as B.

STEP 2: label A as the gaps created by the set of B's, these A's will result in the final required non-consecutive selection.

STEP 3: The B's created 11 gaps and we need only 5 elements in our selection, so remove 6 A's. So the number of ways for this process is ¹¹C₅

STEP 4: Fill the final created arrangements of slots with the numbers 1,2,3... one by one which will give us the final required set of both the selected elements A and the non-selected elements B in an increasing order. The number of ways for doing this process is only 1 as we are filling the numbers in a fixed order 1,2,3...

Was that what you meant? Also what is the use of showing a bijective relation here?

 

[haruspex]

Was that what you meant? Also what is the use of showing a bijective relation here?

Yes, that's how it works.
For completeness, a bijection should be demonstrated; otherwise it could turn out that two different selections of five As lead to the same five digits. It is trivial, though.

 

[kshitij]

two different selections of five As lead to the same five digits

If we are putting the numbers 1,2,3... in a fixed order, then it could be either ascending or descending 15,14,13... is that why we could get two different selection of five A's?

 

[haruspex]

If we are putting the numbers 1,2,3... in a fixed order, then it could be either ascending or descending 15,14,13... is that why we could get two different selection of five A's?

No, with the method described it is not possible to have two different selections of As leading to the same selection of five digits, but one has to prove it is not possible in order to justify the method.