Number of combinations

Printable View

June 5th 2012, 02:06 AM
billobillo

Number of combinations

If I have numbers from 1 to N and I want to select K out of them.
In how many ways I can select these K numbers such that they contain at least two consecutive numbers.
For example if N=7 and K=3, I want to select combinations such as {1,2,3) , {2,3,7} , {3,5,6} but not {1,3,5} or {2,4,7} .....

And another question,what about the number of combinations when specifying the minimum distance D between numbers,for example instead of selecting consecutive numbers (D=1), I want to specify the minimum distance allowed between numbers, i.e if D=2, only combinations such as {1,3,5} or {1,5,7} .... are allowed or if D=3 only {1,4,7} is allowed.
I there a way to create a general formula that takes N,K and D and give me the number of combinations allowed?
June 5th 2012, 06:52 AM
Plato

Re: Number of combinations

Quote:

Originally Posted by billobillo

If I have numbers from 1 to N and I want to select K out of them.
In how many ways I can select these K numbers such that they contain at least two consecutive numbers.
For example if N=7 and K=3, I want to select combinations such as {1,2,3) , {2,3,7} , {3,5,6} but not {1,3,5} or {2,4,7} ....

First note that if $K \leqslant \left\lceil {\frac{N}{2}} \right\rceil$ , that is the ceiling function, there are $\binom{N-K+1}{K}$ of pick a subset of $K$ numbers with no consecutive numbers. So subtract from the total.

If $K > \left\lceil {\frac{N}{2}} \right\rceil$ then any subset of $K$ numbers with must contain consecutive numbers.

I do not understand the second part at all.
June 5th 2012, 11:50 PM
billobillo

Re: Number of combinations

Quote:

Originally Posted by Plato

First note that if $K \leqslant \left\lceil {\frac{N}{2}} \right\rceil$ , that is the ceiling function, there are $\binom{N-K+1}{K}$ of pick a subset of $K$ numbers with no consecutive numbers. So subtract from the total.

If $K > \left\lceil {\frac{N}{2}} \right\rceil$ then any subset of $K$ numbers with must contain consecutive numbers.

I do not understand the second part at all.

Thank you for the reply, I guess you are the genius of this forum :), in first part the difference between any 2 of the K numbers should be >= "1"; you answer is correct.
In the second part , I need to choose a number other than "1" i.e. if D="2" , then the difference between any 2 of the K numbers should be >= "2"
For example : If D=2, I need set like {1,3,5} where 3-1>=2 and 5-3>=2 and 5-1>=2 OR set like {2,4,7} ......
Or If D=3 I need number of sets like {1,4,7} where 4-1>=3 and 7-4>=3 and 7-1>=3.
Is there a way to create a general formula that takes N,K and D and give me the number of combinations allowed?
Regards.