Question about Combin function

D

Daka

The function combin(22,6) produces 74,613 combinations.
However, I have an excel program which eleminates the majority of the
combination because it allows not more than 2 numbers in each subset
to be repeated. This results in a total of 77 combinations that meet
the criteria.
Example:
1,2,3,4,5,6
1,2,7,8,9,10
1,2,11,12,13,14
1,2,15,16,17,18
1,2,19,20,21,22
1,3,7,11,15,19
1,3,8,12,16,20
How can the combin function be manipulated to show the result of 77?

For testing purposes =combin(23,7) produces 245,157 combinations but
when not more than 3 numbers are allowed to repeat the result is 253
combinations that meet the criteria.
Dk
 
S

Scott

The function combin(22,6) produces 74,613 combinations.
However, I have an excel program which eleminates the majority of the
combination because it allows not more than 2 numbers in each subset
to be repeated. This results in a total of 77 combinations that meet
the criteria.
Example:
1,2,3,4,5,6
1,2,7,8,9,10
1,2,11,12,13,14
1,2,15,16,17,18
1,2,19,20,21,22
1,3,7,11,15,19
1,3,8,12,16,20
How can the combin function be manipulated to show the result of 77?

For testing purposes =combin(23,7) produces 245,157 combinations but
when not more than 3 numbers are allowed to repeat the result is 253
combinations that meet the criteria.
Dk

Hi,

For your first question with 22 and 6 (no more than 2 #'s), the answer
is =COMBIN(22,3)/COMBIN(6,3).
For your second question with 23 and 7 (no more than 3 #'s), the
answer is =COMBIN(23,4)/COMBIN(7,4).

In general, for N total numbers of which you select S and allow no
more than D numbers to repeat, the answer would be =COMBIN(N,D+1)/
COMBIN(S,D+1).

Using the N=23, S=7, D=3 example: As D = 3, every set of 4 elements
can only appear 1 time, otherwise it will violate your constraints.
The first thing to determine is how many distinct sets of 4 (D+1) can
be generated from the 23 (N) numbers. For this example, that is
COMBIN(N,D+1) = COMBIN(23,3+1) = 8,855 sets. The second thing to
determine is how many distinct sets of 4 (D+1) get used up every time
you choose 7 (S) elements. For this example, that is COMBIN(S,D+1) =
COMBIN(7,3+1) = 35. Therefore you can have 8,855 / 35 = 253
combinations.

S
 
S

Scott

Hi,

For your first question with 22 and 6 (no more than 2 #'s), the answer
is =COMBIN(22,3)/COMBIN(6,3).
For your second question with 23 and 7 (no more than 3 #'s), the
answer is =COMBIN(23,4)/COMBIN(7,4).

In general, for N total numbers of which you select S and allow no
more than D numbers to repeat, the answer would be =COMBIN(N,D+1)/
COMBIN(S,D+1).

Using the N=23, S=7, D=3 example: As D = 3, every set of 4 elements
can only appear 1 time, otherwise it will violate your constraints.
The first thing to determine is how many distinct sets of 4 (D+1) can
be generated from the 23 (N) numbers.  For this example, that is
COMBIN(N,D+1) = COMBIN(23,3+1) = 8,855 sets.  The second thing to
determine is how many distinct sets of 4 (D+1) get used up every time
you choose 7 (S) elements.  For this example, that is COMBIN(S,D+1) =
COMBIN(7,3+1) = 35.  Therefore you can have 8,855 / 35 = 253
combinations.

S

Oops, sorry, I forgot to mention that this is a maximum. The actual
number of combinations the parameters permit when you attempt to
construct the set may be lower. I couldn't tell you off the top of my
head how many instances or under what conditions it is less than the
theoretical optimal number.

An example of where it is less is using N=5, S=4, D=2, COMBIN(5,3)/
COMBIN(4,3) = 2.5. When you attempt to construct the combinations,
you'll find there is only 1. (Any one of {1,2,3,4}, {1,2,3,5},
{1,2,4,5}, {1,3,4,5}, {1,2,3,4}, but you can't choose 2 of these as
you'll end up violating the constraints)

[In general, for N = k, S= k-1, and D=2, the actual number of sets is
going to be 1.]

You'll probably need someone with a bit more insight to help you
determine when you will be unable to achieve the theoretical maximum.

S
 
D

Daka

For your first question with 22 and 6 (no more than 2 #'s), the answer
is =COMBIN(22,3)/COMBIN(6,3).
For your second question with 23 and 7 (no more than 3 #'s), the
answer is =COMBIN(23,4)/COMBIN(7,4).
In general, for N total numbers of which you select S and allow no
more than D numbers to repeat, the answer would be =COMBIN(N,D+1)/
COMBIN(S,D+1).
Using the N=23, S=7, D=3 example: As D = 3, every set of 4 elements
can only appear 1 time, otherwise it will violate your constraints.
The first thing to determine is how many distinct sets of 4 (D+1) can
be generated from the 23 (N) numbers.  For this example, that is
COMBIN(N,D+1) = COMBIN(23,3+1) = 8,855 sets.  The second thing to
determine is how many distinct sets of 4 (D+1) get used up every time
you choose 7 (S) elements.  For this example, that is COMBIN(S,D+1) =
COMBIN(7,3+1) = 35.  Therefore you can have 8,855 / 35 = 253
combinations.

Oops, sorry, I forgot to mention that this is a maximum.  The actual
number of combinations the parameters permit when you attempt to
construct the set may be lower.  I couldn't tell you off the top of my
head how many instances or under what conditions it is less than the
theoretical optimal number.

An example of where it is less is using N=5, S=4, D=2, COMBIN(5,3)/
COMBIN(4,3) = 2.5.  When you attempt to construct the combinations,
you'll find there is only 1.  (Any one of {1,2,3,4}, {1,2,3,5},
{1,2,4,5}, {1,3,4,5}, {1,2,3,4}, but you can't choose 2 of these as
you'll end up violating the constraints)

[In general, for N = k, S= k-1, and D=2, the actual number of sets is
going to be 1.]

You'll probably need someone with a bit more insight to help you
determine when you will be unable to achieve the theoretical maximum.

S- Hide quoted text -

- Show quoted text -

Thank you for your help. Gives me something to work with.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top