Combinatorics problem! (Probably easy)

Find the number of ways in which we can select three integers from the set of integers, { 1 , 2 , 3 , 4 , 5 , 6 , 7 , . . . . . . . . . . . . . . . . , 47 , 48 , 49 } \{1,2,3,4,5,6,7,................,47,48,49\} such that no two are consecutive

B o n u s Bonus : Prove this for selecting r r integers from first n n natural numbers such that no two are consecutive.


The answer is 16215.

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.

2 solutions

Let n 1 , n 2 , n 3 n_{1}, n_{2}, n_{3} be a given combination of 3 3 integers chosen, and without loss of generality suppose n 1 < n 2 < n 3 . n_{1} \lt n_{2} \lt n_{3}.

Now let a a be the number of integers in S = 1 , 2 , 3 , . . . . , 49 S = {1,2,3,....,49} less than n 1 , n_{1}, b b the number of integers in S S between n 1 n_{1} and n 2 , n_{2}, c c the number of integers in S S between n 2 n_{2} and n 3 , n_{3}, and d d the number of integers in S S greater than n 3 . n_{3}.

Then a + b + c + d = 46 a + b + c + d = 46 such that a , d 0 a,d \ge 0 and b , c 1 , b,c \ge 1, (in order to ensure that n 1 , n 2 , n 3 n_{1}, n_{2}, n_{3} are not consecutive).

Now let b = b 1 b' = b - 1 and c = c 1. c' = c - 1. We then have the equation a + b + c + d = 44 a + b' + c' + d = 44 with a , b , c , d 0 , a,b,c,d \ge 0, which is a 'stars and bars' calculation with solution ( 47 3 ) = 16215 . \dbinom{47}{3} = \boxed{16215}.

In similar fashion, the general formula is found to be ( n r + 1 r ) . \dbinom{n - r + 1}{r}.

Nice.Once you get the general case,then it easy to solve the question.

Saarthak Marathe - 5 years, 8 months ago

Excellent and elegant!

Miraj Shah - 5 years, 3 months ago
Madhav Gupta
Oct 4, 2015

let us have n numbers and we need to choose r out of them so let us have r markers for the numbers we choose and n-r markers for the numbers we don't choose. so those n-r markers are arranged in one way and they have n-r+1 spaces in between them for us to insert those markers of numbers we want to choose so total ways in which we can choose r spaces out of n-r+1 spaces = ( n r + 1 r ) . \dbinom{n-r+1}{r}. after the combination has happened i will lift up the whole pattern and lay it on the line of numbers...

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...