Combination Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Ddanndt
Posts: 60
Joined: Fri Oct 02, 2009 4:18 pm UTC
Location: Paris

Combination Problem

Just wondering if there is a simple way of computing this problem: How many different 6 number combinations from numbers 1 to 40 can I make such that there are no consecutive numbers?

I found something but I cant calculate it's value

Spoiler:
$\Big\lgroup\sum_{l=0}^{30}\Big\lgroup \sum_{k=0}^{l} \Big\lgroup\sum_{j=0}^{k} \Big\lgroup\sum_{i=0}^{j}\Big\lgroup\sum_{1}^{i}x\Big\rgroup \Big\rgroup \Big\rgroup \Big\rgroup \Big\rgroup$
Last edited by Ddanndt on Tue Mar 22, 2011 3:40 pm UTC, edited 1 time in total.
God does not care about our mathematical difficulties — He integrates empirically.
—Albert Einstein

theorigamist
Posts: 129
Joined: Sat Nov 15, 2008 12:06 am UTC

Re: Combination Problem

To clarify: no consecutive numbers rules out 123456, but are you also ruling out 654321?

Ddanndt
Posts: 60
Joined: Fri Oct 02, 2009 4:18 pm UTC
Location: Paris

Re: Combination Problem

theorigamist wrote:To clarify: no consecutive numbers rules out 123456, but are you also ruling out 654321?

Yep cos i'm only looking for combinations and not permutations.
God does not care about our mathematical difficulties — He integrates empirically.
—Albert Einstein

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Combination Problem

Because of the word "combination", I interpret 1,2,3,4,5,6 to be the same as 6,5,4,3,2,1. That is, we're talking about subsets.

I interpret "no consecutive numbers" to mean that 1,3,5,7,9,10 is not OK but 1,3,5,7,9,11 is allowed (note that under my interpretation, that would be the "smallest" allowable subset under a certain reasonably natural ordering).

Is this what was meant?

E.g. if "6" and "40" in the original problem are replaced with "3" and "8", the allowable combinations are something like

Spoiler:
1,3,5
1,3,6
1,3,7
1,3,8
1,4,6
1,4,7
1,4,8
1,5,7
1,5,8
1,6,8
2,4,6
2,4,7
2,4,8
2,5,7
2,5,8
2,6,8
3,5,7
3,5,8
3,6,8
4,6,8

ETA: I believe there's a pretty simple closed-form answer in general. At first, I proved it by an inelegant counting argument, and then later I had an "aha" moment that made the argument simpler. (It helped that I had seen similar problems in the past.)

I can give more detail later if needed. (This isn't homework, is it?)

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Combination Problem

skullturf wrote:ETA: I believe there's a pretty simple closed-form answer in general. At first, I proved it by an inelegant counting argument, and then later I had an "aha" moment that made the argument simpler. (It helped that I had seen similar problems in the past.)
Indeed there is. For choosing k non-consecutive numbers from the range 1..n, the answer is
Spoiler:
(n-k+1)-Choose-k = (n-k+1)! / ( (n-2k+1)! k! )
You could prove that by finding the recurrence relation.
Spoiler:
Let g(n,k) be the function we are looking for. When you choose k numbers, either you include n in them or you don't. If you do, the remaining k-1 must be chosen from 1...(n-2). If you don't, you must choose the k numbers from 1...(n-1). Therefore g(n,k) = g(n-2,k-1)+g(n-1,k). You also have the base cases g(2k-1,k)=1, and g(n,k)=0 for n<2k-1. It is easy to verify that the formula satisfies these, and that would be enough to prove is correct.
This doesn't really show why the formula is so simple however, only that it is correct.

A more insightful way is this:
Spoiler:
Think of the numbers you choose as being separators. By choosing (and removing) the k numbers you are splitting the range 0...(n+1) into k+1 non-empty intervals. Note that I added the numbers 0 and n+1 to the range so that there are non-empty intervals at the ends as well.
Now transform this by shortening all the k+1 intervals by 1, so that they are allowed to be empty. Instead of n+2 numbers (the range 0..n+1) we have (n+2)-(k+1) = n-k+1 numbers from which we choose k separators. This gives the formula (n-k+1)-choose-k as before.

This is a bit complicated, so it might be easier to describe an explicit choosing procedure with n=40, k=6.
Choose any 6 numbers in the range 0...34 (may be consecutive).
Arrange the 6 numbers in order.
Add 1 to the first (smallest) number, 2 to the second, ..., 6 to the last number. This transforms the 6 numbers to non-adjacent numbers in the range 1..40.

There is this one-to-one correspondence between choosing 6 non-consecutive numbers in the range 1-40 and choosing any 6 numbers in the range 0-34, and it is this that makes the formula so simple.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Combination Problem

That's basically what I did. My verbal description is different, but same idea.

First, I noticed that choosing 6 numbers from 1 to 40 is equivalent to choosing a "word" of length 40 where 6 of the symbols are 1, and the other 34 are 0. (1 in position j means j belongs to the set, 0 in position j means j doesn't belong to the set.)

Then, if our subset can't have any consecutive elements, that means our word can never have consecutive 1's.

My "aha" moment (which I didn't realize right away, but eventually did) was

Spoiler:
First, place the 34 zeros in a row. The 34 zeros can be thought of as "dividers" that delineate 35 "spaces" where a 1 may or may not be placed. (Number of spaces = 1 more than number of dividers.)

If we can't have consecutive 1's, then we can put at most one 1 in any space.

So, choose 6 of the 35 spaces to put the 1's!

Ddanndt
Posts: 60
Joined: Fri Oct 02, 2009 4:18 pm UTC
Location: Paris

Re: Combination Problem

Yep thanks a lot guys. Feel so stupid I didnt think of the separator/ empty space method . And it even becomes easy to solve for cases such as only 2 consecutive numbers, only 3 consecutive numbers etc...
God does not care about our mathematical difficulties — He integrates empirically.
—Albert Einstein

Minchandre
Posts: 524
Joined: Thu Nov 08, 2007 3:36 am UTC

Re: Combination Problem

Also note that your original sum is fairly easily calculable if you distribute and split the polynomial at each step.

Ddanndt
Posts: 60
Joined: Fri Oct 02, 2009 4:18 pm UTC
Location: Paris

Re: Combination Problem

In fact there was a small mistake in the formula which I corrected and I managed to solve

Spoiler:
$\Big\lgroup\sum_{l=0}^{30}\Big\lgroup \sum_{k=0}^{l} \Big\lgroup\sum_{j=0}^{k} \Big\lgroup\sum_{i=0}^{j}\Big\lgroup\sum_{1}^{i}x\Big\rgroup \Big\rgroup \Big\rgroup \Big\rgroup \Big\rgroup = {1\over 120} \sum_{l=0}^{30} ( l^5 + 10l^4 + 35l^3 + 50l^2 + 24l) = 1623160$
God does not care about our mathematical difficulties — He integrates empirically.
—Albert Einstein

pilo
Posts: 1
Joined: Wed Oct 31, 2012 7:08 am UTC

Re: Combination Problem

Hello guys, I am facing the same problem, but here I need to find a formula for choosing k numbers such that there is at least two gaps between the numbers.
Any help?

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Combination Problem

What do you mean when you say "there is at least two gaps between the numbers"? Can you perhaps rephrase in a different way?

I assume you mean some kind of variation on the original problem. In the original problem, we were choosing 6 numbers from 1 to 40, and we weren't allowed consecutive numbers. One way to say that would be to talk about the "gaps" between the numbers -- if the 6 numbers are 4, 9, 13, 17, 23, 29, then by "gaps" do you mean 9-4, 13-9, etc.?