Count combinations

[TwIsTeEeR]

From a set of integers from 1 to 49,
take 6 unique integers,
that if we sum them up, this sum is equal to 150.

Conditions:
1. The set numbers are integers from 1 to 49
2. subset size is 6
3. sum of the selected subset numbers is 150

My questions:
A. How many sets (combinations) of 6 unique numbers exist that their sum
is 150?
B. Do you know of a function that can calculate that quantity
of combinations, for different values of conditions (1), (2), & (3)?

Thank you,

 

[Myrna Larson]

In the past I've posted code to generate combinations. You can find it by searching Google for
posts from Myrna Larson, key words "combinations" "permutations". The message you want was
posted on July 25, 2000.

There are almost 14 million combinations of 49 items taken 6 at a time, so the code will take a
while to run (maybe hours?) There will be 214 columns of text. You'll need to split the data
from 1 column into 6 (data/text to columns) plus a 7th column for a SUM formula, so you'll need
1498 columns, which means 6 worksheets with data from ~36 columns on each.

Once you've generated the combinations, copied to multiple sheets, split into 6 numbers and done
the SUMs, you can use Data/AutoFilter to show the total you want. I hope Excel won't choke on
this amount of data. It will undoubtedly be VERY SLOW!

I presume this has something to do with the lottery? Whatever your scheme, it won't work <g>.

 

[TwIsTeEeR]

Hi Myrna,

My question has not to do with the lottery,
but I used the values of a lottery game to attract some attention.

I'm asking only of the quantity of such combinations on my first question.
* How many such combinations exist?

I imagine your function is of a brute force nature.
I'm not looking for somthing like that.
I'm looking for an equation.

On my second question.
* Does a genetrating function exist to satisfy different values?

Thank you,

 

[Greg Wilson]

As I understood Myrna, the nearly 14 million combinations
are the total possible for 6 elements from a list of 49.
(See the worksheet function Combin). This is not the
limited set that sum to 150.

You can obtain the number of combinations of 6 values that
sum to 150 using nested For/Next loops (i.e. brute force
as you put it). As you are aware, this would normally
take a very long time. However, in this case, since the
numbers 1 to 49 are in ascending order, you can include
code that aborts each loop once the sum exceeds 150 since
there would no longer be any point in continuing (because
the sum can only get bigger). This should drastically
reduce the time, I would think, but will still likely be
quite long.

The code to abort the inner loop is simple but a bit
tricky for the remainder. I'm pretty sure I've got it
figured out however. If your're interested, I could give
it a whirl. My guess is that the number will be in excess
of 100,000 !!!

Regards,
Greg

 

[TwIsTeR]

From a set of integers from 1 to 49,
take 6 unique integers,
that if we sum them up, this sum is equal to 150.

Conditions:
1. The set numbers are integers from 1 to 49
2. subset size is 6
3. sum of the selected subset numbers is 150

My questions:
A. How many sets (combinations) of 6 unique numbers exist that their sum
is 150?
B. Do you know of a function that can calculate that quantity
of combinations, for different values of conditions (1), (2), & (3)?

Thank you,

A mathematical answer came from:


The coefficient of s^6 t^150 in (1+st)(1+st^2)...(1+st^49).
Let P_0 = 1, and for j = 1 to 49 let
P_j = P_{j-1} (1+st^j) mod <s^7, t^151>
(i.e. multiply it out and remove any term involving s^i with
i >=7 or t^k with k >= 151). In Maple you can do it with

P[0]:= 1;

for j from 1 to 49 do
P[j]:= rem(rem(P[j-1]*(1+s*t^j),s7,s),t151,t)
od:
coeff(coeff(P[49],t,150),s,6);

165772

A somewhat more prosaic dynamic-programming solution is also possible,
and would have faster execution time, but would require more time to
program.

Robert Israel (e-mail address removed)
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2


Is it posible to create a VBA function to satisfy the second question,
using the above answer?

 

[TwIsTeR]

From a set of integers from 1 to 49,
take 6 unique integers,
that if we sum them up, this sum is equal to 150.

Conditions:
1. The set numbers are integers from 1 to 49
2. subset size is 6
3. sum of the selected subset numbers is 150

My questions:
A. How many sets (combinations) of 6 unique numbers exist that their sum
is 150?
B. Do you know of a function that can calculate that quantity
of combinations, for different values of conditions (1), (2), & (3)?

Thank you,

The code below satisfies the first part of the question.
Is it possible to convert this code to a recursive function,
so that the term SetSize can be satisfied also?

Thanks,


Sub Test()


Dim minval As Integer
Dim maxval As Integer
Dim Target As Long
Dim sum As Long
Dim Cnt As Long
Dim SetSize As Integer
Dim RetVals As String



minval = 1
maxval = 49
SetSize = 6
Target = 150
sum = 0

For I = minval To (Target + 5) / 6 - 3
sum = sum + I
For J = I + 1 To (Target + 4 - sum) / 5 - 2
sum = sum + J
For K = J + 1 To (Target + 3 - sum) / 4 - 2
sum = sum + K
For L = K + 1 To (Target + 2 - sum) / 3 - 1
sum = sum + L
For M = L + 1 To (Target + 1 - sum) / 2 - 1
N = Target - sum - M
If (N <= maxval) Then
Cnt = Cnt + 1
End If
Next
sum = sum - L
Next
sum = sum - K
Next
sum = sum - J
Next
sum = sum - I
Next

RetVals = MsgBox("When " & vbTab & "MinN=" & minval & _
vbNewLine & " " & vbTab & "MaxN=" &
maxval & _
vbNewLine & " " & vbTab & "Set size=" &
SetSize & _
vbNewLine & " " & vbTab & "Sum=" & Target &
vbNewLine & _
"There are = " & Cnt & " Combinations to satisfy
the condition." & vbNewLine & " ", 64, "Combinations...")
Select Case RetVals
Case 1: 'OK
End Select

End Sub

 

[Greg Wilson]

Be advised that I don't get the same result using your
macro as I do mine. My macro is appended. I recommend
that you double check your macro although I won't say with
100% certainty that mine is the correct one.

In order to check mine, I inserted some 'demo code' into
the macro. This allowed me to monitor what was being
referenced by the For/Next loops. For the demo, the row
numbers represented the values being summed. My
conclusion was that the code works as advertised. Note
that all loops are aborted once the sum >= 150. This can
get confusing when more than one abort at the same time.

If you run the demo you should reduce all references to
150 to, say, 50 instead to save time. Also, you need to
enable the screen updating.

Public Declare Sub Sleep Lib "kernel32.dll" (ByVal
dwMilliseconds As Long)

Sub Combinations()
Dim a As Integer, b As Integer, c As Integer
Dim d As Integer, e As Integer, f As Integer
Dim Results As Long

'Application.ScreenUpdating = False
Results = 0
For a = 1 To 49
If a + b + c + d + e + f >= 150 Then Exit For
For b = a + 1 To 49
If a + b + c + d + e + f >= 150 Then
b = a + 2: c = b + 1: d = c + 1: e = d + 1: f = e + 1
Exit For
End If
For c = b + 1 To 49
If a + b + c + d + e + f >= 150 Then
c = b + 2: d = c + 1: e = d + 1: f = e + 1
Exit For
End If
For d = c + 1 To 49
If a + b + c + d + e + f >= 150 Then
d = c + 2: e = d + 1: f = e + 1
Exit For
End If
For e = d + 1 To 49
If a + b + c + d + e + f >= 150 Then
e = d + 2: f = e + 1
Exit For
End If
For f = e + 1 To 49

Cells(a, 1).Interior.ColorIndex = 6 'Demo code
Cells(b, 2).Interior.ColorIndex = 6 'Demo code
Cells(c, 3).Interior.ColorIndex = 6 'Demo code
Cells(d, 4).Interior.ColorIndex = 6 'Demo code
Cells(e, 5).Interior.ColorIndex = 6 'Demo code
Cells(f, 6).Interior.ColorIndex = 6 'Demo code
Range("H1") = a + b + c + d + e + f 'Demo code
Sleep 300 'Demo code
Range("A1:F49").Interior.ColorIndex = xlNone 'Demo code
If a + b + c + d + e + f = 150 Then
Results = Results + 1
Range("I1") = Results 'Demo code
f = e + 2
Exit For
End If
Next f
Next e
Next d
Next c
Next b
Next a
Application.ScreenUpdating = True
MsgBox "The number of combinations that sum to 150 are: "
& _
Results & " ", vbInformation, "Combinations"
End Sub

Regards,
Greg

 

[TwIsTeR]

There exists a better code.
It is in java that I'm not familiar with.

http://www.btinternet.com/~se16/js/partitions.htm with

Partitions with distinct terms of: 150
Exact number of terms: 6
Each term no more than: 49
and then look at the Java code
http://www.btinternet.com/~se16/js/PartitionChoice.java

 

[Myrna Larson]

Be my guest! You can't write Excel macros in Java. You'll have to do it with
a free-standing app. Good luck.

 

[Myrna Larson]

I didn't conclude that he wanted the most frequent total. I thought he
wanted to be able to vary all 3 parameters -- number range, size of set, and
desired total. But you may be correct.

I don't have an answer, just an observation...
With the range of numbers 1-10 (Instead of 1-49), and you take all
combinations of 6:
The smallest combination total is 21 (1,2,3,4,5,6), and occurs only once.
The Largest combination total 45 {5, 6, 7, 8, 9, 10}, and also occurs once.

The average of these two numbers (21+45)/2 is the number that occurs the
most often. The answer here is 33.
In a range of 10 numbers taken 6 at a time, a total of 33 occurs the most.

If the Range is 1-49, taken 6 at a time, the total that occurs the most
often is:
(21 + 279)/2

150

It appears the op is asking about the total count of the sum that occurs the
most often.

The brute force method generates many combinations. Instead, I looked at
the total of combinations from a smaller range of numbers.
First, Range 1-6, and made permutations of 6 (basically just one solution)
then Range 1-7, Range 1-8, etc
I did this quickly for the range 1-(6-20)
The number that occurs the most (when grouped as 6 numbers) generated the
following sequence.

{1, 1, 4, 8, 18, 32, 58, 94, 151, 227, 338, 480, 676, 920, 1242, 1636}

Apparently, this is a know integer sequence (A001977). The bad news is
that it does not give the generating function directly. It is listed as a
form of "Restricted partitions."

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001977

Maybe someone with more knowledge can shed some light on this. I have never
seen a result listed like this before, so this would be new to me. Harlan?
Tushar?

The program Mathematica has the function PartitionsP, which I am sure your
Maple program does also:

Information[PartitionsP]

"PartitionsP[n] gives the number p(n) of unrestricted partitions of the
integer n."
Attributes[PartitionsP] = {Listable, Protected}

Here are the first few terms...
Table[PartitionsP[n], {n, 0, 15}]

{1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176}

It looks like this function fits in somewhere, but I do not know enough
about it. I don't see any pattern.

Harlan? Tushar?
--
Dana DeLouis
Using Windows XP & Office XP
= = = = = = = = = = = = = = = = =

From a set of integers from 1 to 49,
take 6 unique integers,
that if we sum them up, this sum is equal to 150.

Conditions:
1. The set numbers are integers from 1 to 49
2. subset size is 6
3. sum of the selected subset numbers is 150

My questions:
A. How many sets (combinations) of 6 unique numbers exist that their sum
is 150?
B. Do you know of a function that can calculate that quantity
of combinations, for different values of conditions (1), (2), & (3)?

Thank you,