The Gateway to Computer Science Excellence
+1 vote

in Combinatory by Junior (649 points) | 96 views
Not sure but is it A?
yes its A , please explain

1 Answer

+1 vote
Best answer

Take a smaller example of this form where among 5 days we need to select 2 non consecutive days.

Instead of choosing 2 days and trying to insert gaps b/w them lets do the opp. This is because in b/w 2 days we might be having more than 1 gap. Then there will be many possibilities to fill spaces b/w 2 days.

We do like, choose the remaining days i.e. 5-2=3. And we try to insert these 2 days in b/w the gaps formed by these 3 days. Note that we can insert only 1 day in each gap else filling a single gap with these 2 days will make them consecutive.

Another imp point to be noted is, we can fill gaps before the  1st day (out of the 3 days) as well as after the last day(out of the 3 days).


$_ D _ D _ D _$ these are the possible gaps to be filled by our 2 days.

We can fill these 4 gaps with 2 days in C(4,2) ways. How?

I will denote the day inserted as M.

1) $ \underline{M} D \underline{M} D  D $

2) $ \underline{M} D D\underline{M}  D $

3) $ \underline{M} D D  D \underline{M} $

4) $ D\underline{M} D \underline{M} D $

5)$ D\underline{M} D D \underline{M} $

6) $ D D \underline{M} D \underline{M} $

So how to generalize?

Given n no. of days and we need to choose r non-consecutive days, we take the rest of the days i.e. (n-r).

Now no. of gaps that can be filled is (n-r+1).

No. of ways to select r days from (n-r+1) is C(n-r+1,r).

In this sum, n=31 and r=5, so answer becomes C(31-5+1,5)=C(27,5).


by Boss (23.5k points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
105,414 users