# Thread: A mathematical algorithm question

1. ## A mathematical algorithm question

(I am not sure if this is the right section of the forum to post,I think it is)

Let's say there are 50 numbers starting from 1 to 50.They will be grouped like:

1 2 3 4
1 2 3 5
1 2 3 6
...
2 3 4 5
2 3 4 6
2 3 4 7
...

and end with:
47 48 49 50

I want to learn how many "1" number and "2" number(in the same combination) there are in the results.What would be the mathematical formula for calculating this? 2. Can you elaborate on what you mean by "1" number and "2" number? 3. Thanks for your answer.I mean how many 1 and 2 numbers are there in the results?

1 2 3 4 //There are 1 number and 2 number
...
1 4 5 6 //There is 1 number
...
3 6 7 8 //There are no 1 or 2 numbers

How many combinations are there which include 1 or 2 numbers? 4. Perhaps "algorithm" is a more fitting term than "formula" for this. And this would be a good exercise to pursue yourself.

To develop the algorithm, go through the exercise "by hand" with a pen and paper. What process do you go through mentally to determine how many 1's and/or 2's are in each line? Take it step by step, and you should start to see a pattern. This pattern is what you should use to start developing an algorithm. When you have a list of steps you've taken to get results, start turning it into code. 5. An easy way to look at this:

Assume 1 and 2 are part of the result, so there are 48 numbers left in the 'pool' to choose. How many different combinations are there for the remaining two numbers? That tells you how many combinations have both 1 and 2.

If you want to know how many have 1, or 2, or both, then it's a bit trickier but it follows the same principles. Figure out how many ways you could pick numbers such that:
* There is a 1 but not a 2
* There is a 2 but not a 1
* There is both a 1 and a 2

The simple way to do this is imagine that you put every possible number into a hat and draw however many numbers it takes to fill the blanks in your patterns. Just remember, if you have 10 numbers in a hat, there are 10 possibilities... and you're left with 9 numbers in the hat (and 9 possibilities) for your next draw. 6. I am interested in this one, have thought about it before, never came up with a formula though, am crap at maths. - Am trying to get onto cat's suggestion but can't make it add up to the answers below

For say a max range of 6 numbers

range = 6
line length = 4
ocurrences to match = 2 (being nums 1 & 2 here but that is moot..)

parameters:
combos of 4 from 6 = 15
combos of 2 from 6 = 15
combos of 2 from 4 = 6

In this example the number of lines containing 1 & 2 = 6

1234
1235
1236
1245
1246
1256
- next line fails - 1345

Another one, now max range is 7:

parameters:
range = 7
line length = 4
ocurrences to match = 2

combos of 4 from 7 = 35
combos of 2 from 7 = 21
combos of 2 from 4 = 6

In this example the number of lines containing 1 & 2 = 10

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
- next line fails - 1345

so can a general formula be written, relationship identified, given the answers in these examples
and the parameters used? 7. For 1 and 2 this should actually be easy. Every combination here is ordered, so if 1 and 2 both appear, they have to appear in the first two places. In other words, all the qualifying combinations start with "1 2", and there's only two places left to fill with any ordered selection from 3-50, i.e. select from 48 numbers. There are 47 combinations that start with 3, 46 that start with 4, 45 that start with 5, etc - eventually we get to 1 combination starting with 49. If we switch this around, this is 1 (for 49) + 2 (for 48) + ... + 46 (for 4) + 47 (for 3), i.e. the 47th triangle number. The Nth triangle number is N*(N+1)/2, so we have 47*48/2 = 1128. There's your answer.

The problem is much harder when you have other fixpoints than 1 and 2. If you look for, say, 3 and 40, you have to deal with combinations that look like "a b 3 40", "a 3 b 40", "a 3 40 b", "3 a b 40", "3 a 40 b" and "3 40 a b". You'd have to calculate the number of possible combinations for each of those individually and sum them up. Stricly speaking, 1 2 is a special case where all but the last of these patterns just yield 0 possibilities. 8. I have worked out a formula for it, this works for any valid set of paramters, Except for non fixed as per CornedBee post![/edit]

I not read the above post example properly yet but i think it might be a lot simpler formula than mine!

Anyway:
You can use it for ocurrences of 1st marker only, or 1st & 2nd, or 1st, 2nd, 3rd or
whatever.

i'll attempt to describe it like this:

let c = combo range to check, eg 1&2
let s = sub range, ie the 'line length' eg in the original posts this was 4
let R = total Range, eg in the original posts this was 50
let O = occurences, the actual result, eg how many times did 1&2 occur

formula is:

O = ((combos of c,s) * (combos of s,R)) / combos of c,R

here are some sample results:

checking for 1 & 2:

c s R O
2 3 3 1
2 3 4 2
2 3 5 3
2 3 6 4
2 3 7 5
2 3 8 6
2 3 9 7
2 3 10 8

2 4 4 1
2 4 5 3
2 4 6 6
2 4 7 10
2 4 8 15
2 4 9 21
2 4 10 28

2 5 5 1
2 5 6 4
2 5 7 10
2 5 8 20
2 5 9 35
2 5 10 56

checking for 1,2,3:
c s R O
3 5 5 1
3 5 6 3
3 5 7 6
3 5 8 10
3 5 9 15

checking for 1:
c s R O
1 3 5 6
1 3 6 10
1 3 7 15
1 3 8 21
1 3 9 28
1 3 10 36

[EDIT]
Checked the CornedBee idea like 47*48/2 ... but i cant get it to work where the subrange, ie line length is different than 4, is another bit needed for that? 9. For 1 and 2 this should actually be easy. Every combination here is ordered, so if 1 and 2 both appear, they have to appear in the first two places. In other words, all the qualifying combinations start with "1 2", and there's only two places left to fill with any ordered selection from 3-50
If you consider the numbers per line as placeholders then fixed position does not matter. If you treat your combo of 2 as being simply any pair then choosing say 1 and 40 has the same amount of appearences (sharing the same line of subrange) throughout the range as choosing 1 and 2. Using the formula i posted proves this, but it also makes sense anyway.

like

looking for pairs in a line where the total range is 6 and subrange is 4

complete set of combos for subrange of range is 15:
1234
1235
1236
1245
1246
1256
1345
1346
1356
1456
2345
2346
2356
2456
3456

If you take any pair of numbers they appear in the same amount of lines each, 6 Popular pages Recent additions 