To use or not to use complement?
How many ways are there to choose 6 integers from 1 to 50 so that none of them are the same and none of them are consecutive to each other?
For example, (1,2,5,7,10,13) is not allowed because 1 and 2 are consecutive.
(1,3,5,7,9,11) and (1,5,3,7,11,9) counts as one way.
The answer is 8145060.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
I believe that the first method (as yet) does not have the correct interpretation / formulation. The " n Choose r" formula only works when you pick exactly "r fixed objects from n". It gets trickier to explain what what happens if the items that you pick get to change.
For example, because we are restricted to "choose the number in an increasing order", if the first number that we pick is 50, then there is no further way to proceed. Thus, there is more work that needs to be done in order to set up the bijection properly.
We will solve the generalization of the problem i.e. How many ways are there to choose r integers from 1 to n so that none of them are the same and none of them are consecutive to each other?
First Method
We will choose the numbers in an increasing order. If we have chosen a we will not choose any number from a − 1 to 1 .so after choosing a number we must not choose the next number and thus choosing r numbers we must leave r − 1 numbers as choosing the last number we will have no restriction for the next. so we leaving r − 1 numbers, we have n − ( r − 1 ) or n − r + 1 numbers remaining.
r numbers can chosen from n − r + 1 numbers in ( r n − r + 1 ) ways. Here n = 5 0 and r = 6 and we are done.
Second Method
Second Method is using Stars and Bars Problem
Mark the positions of the r chosen numbers and leave blank spaces before, between, and after them for the n − r non-chosen numbers.
Remaining slots n − r numbers will go in r + 1 slots and atleast one of them must be in the r − 1 slots in the middle.
After placing a number in each of these slots n − r − ( r − 1 ) numbers are to placed in r + 1 slots.
Required number of ways = ( ( r + 1 ) − 1 ( n − 2 r + 1 ) + ( r + 1 ) − 1 ) = ( r n − r + 1 )