Not logged in [Login - Register]
 Sciencemadness Discussion Board » Fundamentals » Miscellaneous » Calculating Maximum possible combinations Select A Forum Fundamentals   » Chemistry in General   » Organic Chemistry   » Reagents and Apparatus Acquisition   » Beginnings   » Miscellaneous   » The Wiki Special topics   » Technochemistry   » Energetic Materials   » Biochemistry   » Radiochemistry   » Computational Models and Techniques   » Prepublication Non-chemistry   » Forum Matters   » Legal and Societal Issues   » Detritus   » Test Forum

Pages:  1
Author: Subject: Calculating Maximum possible combinations
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

Calculating Maximum possible combinations

"A combination of 4 elements out of 118 could give a maximum of 193,877,776 combinations, if you allow the repetition of an element, e.g. HeHeHeHe.

How would you calculate maximum Not allowing the repetition of an element in the group of four ?"

To try to answer that, i did a binary sequence to see what it looks like.

The possibilities for 1 element are 2^4 = 16.

The same element can only appear once in one of the four positions, and must appear, so the impossible combinations are 2^4 -4 -1 = 11.

As there are four elements in total, with the same rule, the impossible combinations should be 44, so the maximum possible combinations should be 193,877,732.

I feel there is a big thing i missed there.

If a maths genius could take a look please.

[Edited on 15-4-2018 by aga]

DraconicAcid
International Hazard

Posts: 2842
Registered: 1-2-2013
Location: The tiniest college campus ever....
Member Is Offline

Mood: Semi-victorious.

If you don't allow repetition, then you've got 118 choices for the first element, 117 for the second, etc.

118 * 117 * 116 * 115 = 184,172,040 combinations.

Please remember: "Filtrate" is not a verb.
Write up your lab reports the way your instructor wants them, not the way your ex-instructor wants them.
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

Ah yes.

Obvious now you've shown it so clearly.

Thank you.

JJay
International Hazard

Posts: 3320
Registered: 15-10-2015
Member Is Offline

Mood: resigned

 Quote: Originally posted by DraconicAcid If you don't allow repetition, then you've got 118 choices for the first element, 117 for the second, etc. 118 * 117 * 116 * 115 = 184,172,040 combinations.

The only problem with this logic is that your formula assumes that the order the elements are chosen is significant. If it is not significant, you would divide by 4 * 3 * 2 * 1 because you can choose 4 slots for the first element chosen, 3 slots for the second element chosen, and 2 slots for the third element chosen (with one for the last element). That works out to a mere 7,673,835 combinations.

I'm no longer involved in this forum.
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

I can't follow that at all.

If there is a sequence of 4 unique elements, the order makes no difference.

Still, i can't work it out, but your suggestion feels wrong.

JJay
International Hazard

Posts: 3320
Registered: 15-10-2015
Member Is Offline

Mood: resigned

Ok, so, let's say that the order is not significant. But the elements are still going to be in some kind of order.

So let's say you have four coconut shells, and you put them in no particular order on the floor of your villa. You choose your first element. You can put it anywhere you want, in any one of the four coconut shells:

Fe __ __ __
__ Fe __ __
__ __ Fe __
__ __ __ Fe

The iron is only in the first coconut shell 25% of the time, though. If the order matters, the iron is in the first coconut shell 100% of the time. Here, the order doesn't matter, but we need a way to relate the situation to one that we know and understand, and in this case, that's the situation where the order does matter. So we multiply by 118 / 4 because the order doesn't matter, there are 118 elements, and there are 4 possible places to put a chosen element that could affect the order.

There are now three empty coconut shells. 1/4 of the time, the second coconut shell is already filled. We're going to simplify things by only looking at the order of the three remaining empty shells in this context and ignoring exactly which coconut shells they are because otherwise, we'll have to mess around with a lot of fractions, and things are complex enough as it is. Since we're in a context where the first element has already been placed, we'll just remove its coconut shell from the picture entirely.

So we have three coconut shells. 117 elements can be placed in them in any of 3 ways:

Os __ __
__ Os __
__ __ Os

There are three places we could put each element that could affect the order. The order doesn't matter, though, so divide by 3.

And so on with 116 elements and 2 coconut shells:

Br __
__ Br

Last 115 elements, only one coconut shell:

Ar

So doing all the multiplications and divisions leaves 118/4 * 117/3 * 116/2 * 115/1 = 7,673,835

Edit: fixed grammatical error, made clarification

[Edited on 16-4-2018 by JJay]

I'm no longer involved in this forum.
Diachrynic
Hazard to Others

Posts: 126
Registered: 23-9-2017
Location: Germany
Member Is Offline

Mood: zenosyne

What JJay is saying that in the current example order does matter. If it didn't, you would need to divide by 12.

Lets look at simpler case for that:

Possible "elements": A, B, C, D

Now, choose two! Order does matter. No repetition. The following combinations are possible:

A, B
A, C
A, D
B, A
B, C
B, D
C, A
C, B
C, D
D, A
D, B
D, C

Twelve. Math checks out: 4 possible for the first, 3 for the second: 4*3 = 12

Now, choose two. Order does *not* matter. No repetition. The following combinations are possible, impossible ones marked in bold:

A, B
A, C
A, D
B, A (Already counted as A, B)
B, C
B, D
C, A (Already counted as A, C)
C, B (Already counted as B, C)
C, D
D, A (Already counted as A, D)
D, B (Already counted as B, D)
D, C (Already counted as C, D)

So, only these remain:

A, B
A, C
A, D
B, C
B, D
C, D

Only 6. Math checks out: 12 possible combinations divided by the number of ways you can rearrange two distinct items (it's 2): 12/2 = 6

Now, in how many ways can you rearrange 4 distinct items?

A, B, C, D
A, B, D, C
A, C, B, D
A, D, B, C
A, C, D, B
A, D, C, B
B, A, C, D
B, A, D, C
B, C, A, D
B, D, A, C
B, C, D, A
B, D, C, A
C, A, B, D
...

There are 24 = 4*3*2*1 (4 possibilities for the first, 3 for the second, 2 for the third and one for the last).

[EDIT]: Beaten again.

[Edited on 15-4-2018 by Diachrynic]

Just killing time until the world ends. - Furude Rika, HNNKN
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

That's the same way i approached it, yet DraconicAcid's answer makes the most sense.

Random division makes no sense.

Unfortunately i have no coconuts at the moment.

j_sum1
Super Moderator

Posts: 4287
Registered: 4-10-2014
Location: Oz
Member Is Offline

Mood: Metastable, and that's good enough.

Difference between permutations and combinations.

Permutations: the order matters.
Example in a race of 10 runners there are prizes for first, second and third.
10 choices for first, 9 for second, 8 for third. 10x9x8 gives 720 possible orderings of the placegetters.

Combinations: the order does not matter.
Example I need to choose 3 employees out of 10 to sit on a committee.
I can begin with the 720 possibilities noted before but then I realise that it does not matter which chair they sit at. A, B, D is exactly the same as D, A, B for my purposes. So I consider how many ways I can sit three people in three chairs. 3x2x1=6.

My answer is therefore 720/6 which is 120.

j_sum1
Super Moderator

Posts: 4287
Registered: 4-10-2014
Location: Oz
Member Is Offline

Mood: Metastable, and that's good enough.

Ninja'd.

I should add the formulas.

Permutations: selecting r from a group of n, order matters
nPr = n!/r!

Combinations: selecting r from a group of n, order does not matter
nCr = n!/r!(n-r)!

These formulas are on most scientific calculators. Notation varies. Combinations are often called "n choose r". These are also the numbers on pascale's triangle.

aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

 Quote: Originally posted by j_sum1 .. My answer is therefore 720/6 which is 120.

... and if you apply the same logic to the opening question ?

JJay
International Hazard

Posts: 3320
Registered: 15-10-2015
Member Is Offline

Mood: resigned

This page defines permutations and combinations and gives formulas for calculating them: https://www.mathplanet.com/education/algebra-2/discrete-math... In fairness, I looked up the formula before doing this problem, or it would have taken a lot more concentration, and my explanation would have been more complicated.

I was rather talented at these sorts of problems as a child, and I've taken a lot of probability and statistics classes, but I think I must have skipped a math course on how to use first principles to derive probability distributions at some point, and I have no idea what a class like that would be called....

I'm no longer involved in this forum.
j_sum1
Super Moderator

Posts: 4287
Registered: 4-10-2014
Location: Oz
Member Is Offline

Mood: Metastable, and that's good enough.

Quote: Originally posted by aga
 Quote: Originally posted by j_sum1 .. My answer is therefore 720/6 which is 120.

... and if you apply the same logic to the opening question ?

118!/(114!x4!)
Which simplifies to (118*117*116*115)/(4*3*2*1)

aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

Very confused now.

DraconicAcid's solution is logical at 184,172,040

JJay, Diachrynic and jsum_1 also make some kind of sense at 7,673,835

The difference is huge (also from my first stab at it) so it feels like something is missing.

If the Order is unimportant, Where the element appears should not make a difference to the result.

Edit:

It would have taken a long time to guess what the origional questioner was thinking in any event.

[Edited on 15-4-2018 by aga]

JJay
International Hazard

Posts: 3320
Registered: 15-10-2015
Member Is Offline

Mood: resigned

 Quote: Originally posted by aga That's the same way i approached it, yet DraconicAcid's answer makes the most sense. Random division makes no sense. Unfortunately i have no coconuts at the moment.

Use beakers

In the situation where the order does matter, when you choose your first element, you can only put it in the first position. When the order doesn't matter, you can put the element into any one of four positions without affecting the combination. When the order does matter, three other positions can also happen in other "combinations" (actually permutations) and each other position is equally likely to arise when exhaustively enumerating all possible permutations as the first position. Therefore, when choosing the first element, there can be only 25% as many combinations controlled by your choice of element when the order does not matter as when it does. Right?

[Edited on 15-4-2018 by JJay]

I'm no longer involved in this forum.
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

Well, not really, not in this case.

The first beaker could be beaker number 3.

Any of them.

Edit:

Draconic's logic works well for this - Forget the positions.

Choose 1 from 118. OK. That one is chosen.
Now there are only 117 left to choose from.
etc.

[Edited on 15-4-2018 by aga]

JJay
International Hazard

Posts: 3320
Registered: 15-10-2015
Member Is Offline

Mood: resigned

We can put abstractions on the beakers, but they can't just magically change. Each has a physical order, the order it is filled, the order that is arbitrarily assigned, etc. When beakers are empty, the empty beakers have an order. If you look at (really, just think about) every possible permutation, beaker 3 is no more likely to contain a specific element than any other beaker. So when relating the permutation formula (which we can figure out intuitively) to the combination formula, when choosing element 3, we simply copy the part of the permutation formula relating to the choice, modifying it to fit the combination situation by dividing by the number of empty beakers when the choice is made.

Whether DraconicAcid is correct or whether everyone else is correct depends on whether the term "combination" was used in its strict mathematical sense or colloquially. I think DraconicAcid is obviously capable of doing these sorts of problems and generated a lot of academic discussion by positing the permutation formula as an answer, so I assume he was playing devil's advocate.

[Edited on 15-4-2018 by JJay]

I'm no longer involved in this forum.
woelen

Posts: 6612
Registered: 20-8-2005
Location: Netherlands
Member Is Offline

Mood: interested

If order is not important, then different patterns collapse to one pattern.

E.g. suppose you choose A, B, C, D
Next, time, you first choose B, then you choose A, then you choose C and then D, hence B, A, C, D.
But if order does not matter, then A,B,C,D is the same as B,A,C,D, but they are different choices!

That's what gives you the different numbers. The first number is 118*117*116*115, but it contains a lot of duplicates, e.g. A,B,C,D and B,A,C,D and D,C,A,B and C,D,B,A and so on. In total there are 4*3*2 such duplicates. For all combinations of 4 different elements you will find 24 different choices, all being equivalent. Hence, the total number of choices with different elements, in which order does not matter is 118*117*116*115/(4*3*2).

------------------------------------------------------------------------------

In general, if you take K out of N items and order does not matter, then the number of combinations is the binomial

(N)
(K),

which can be written as N!/(K!*(N-K)!)

If order does matter, then you have N!/(N-K)! possibilities.

The art of wondering makes life worth living...
Want to wonder? Look at http://www.oelen.net/science
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

Oh i see !

The repeating patterns just in different order eluded me entirely.

I knew something felt wrong about my first attempt, yet Draconic's logic seems flawless.

Amazing how some maths can seem 100% correct (in itself) yet be very wrong in reality.

I would like to experiment with 10 stones and 3 cups to verify.

Could take a while.

DraconicAcid
International Hazard

Posts: 2842
Registered: 1-2-2013
Location: The tiniest college campus ever....
Member Is Offline

Mood: Semi-victorious.

 Quote: Originally posted by JJay Whether DraconicAcid is correct or whether everyone else is correct depends on whether the term "combination" was used in its strict mathematical sense or colloquially. I think DraconicAcid is obviously capable of doing these sorts of problems and generated a lot of academic discussion by positing the permutation formula as an answer, so I assume he was playing devil's advocate.

I wasn't so much playing Devil's Advocate so much as forgetting which was combinations and which was permutations. I was focusing on the non-repetition and ignoring the question of whether order mattered. If order matters, then the number I gave is correct, and if it doesn't matter, then the smaller number is correct.

Just as long as nobody starts suggesting obscure free-radical redox steps in calculating the number of permutations, I'm good.

Please remember: "Filtrate" is not a verb.
Write up your lab reports the way your instructor wants them, not the way your ex-instructor wants them.
AJKOER
International Hazard

Posts: 2563
Registered: 7-5-2011
Member Is Offline

Mood: No Mood

In the context of chemistry, knowing that a possible combination (not permutation) is say C4H8N2O4 still leaves a lot of info out!

Like there could be no groups or methyl groups, or acetyl,...., and different bonding between elements and in some cases, the different ordering itself is material as it could correspond to possible isomers. Also the size of groups themselves could introduce steric effects (see, for example, comments at http://www.chem.ucla.edu/~harding/IGOC/S/steric_effect.html ).

Adding to the complexity, at the atomic level, atoms may be decomposing into isotopes (think uranium). So, not necessarily total atomic uniformity for certain select elements.

Lastly, in a chemical setting, probably should define a time dimension (or none) for a listed molecule as many compounds, especially radicals, are transient in nature.

[Edited on 19-5-2018 by AJKOER]
SWIM
National Hazard

Posts: 312
Registered: 3-9-2017
Member Is Offline

Mood: really starting to feel the Specioprin HCl now

Aga, you're making things too hard on yourself by studying maths.

Over here in America we just study one of them, and find it perfectly adequate.

The problem with quotes on the internet is that it's hard to determine their authenticity. -Abraham Lincoln.
aga
Forum Drunkard

Posts: 7028
Registered: 25-3-2014
Member Is Offline

'Math' implies 'Mathematic'.

To be studying 'Mathematic' doesn't make much sense in English.

There's a missing -s or -ally or -analysis or -principal or -method or something else to positively identify the meaning, hence 'Maths' as an abbreviation of 'Mathematics', retaining the identifier.

similarly :-
"I am studying Physic"
"I am studying Economic"
"I am studying Politic"
"I am studying Biometric" etc.

May as well accept that North American has diverged far enough now to be a distinct language with it's own rules and spelling.

woelen

Posts: 6612
Registered: 20-8-2005
Location: Netherlands
Member Is Offline

Mood: interested

A nice exercise for aga would be to find the formula for all possible isomers of alkanes CnH2n+2 .

As a function of n, see table below for the first few alkanes:

1 --> 1 (methane)
2 --> 1 (ethane)
3 --> 1 (propane)
4 --> 2 (n-butane, isobutane)
5 --> 3 (n-pentane, isopentane, neopentane)
6 --> 5 (. . .)
7 --> 9 (. . .)
8 --> 18
9 --> 35
10 --> 75

For larger n, the number of isomers rapidly grows with growing n. Finding a formula for the number of isomers as function of n, is not easy, be warned! You may assume that all isomers with 4 bonds on the C-atom and 1 bond on the H-atom are valid, so you do not have to take into account sterical hindrance, high bond strain or other physical effects, which may make some isomers unlikely to exist.

You will not find a solution in the form of a formula, but thinking about how you could solve this problem, you learn a lot about combinations and mathematical algorithms in general. It is possible to write a program, which computes the number of isomers, given a certain n. This program will be non-trivial, but it should not be extremely hard to write it.

[Edited on 22-5-18 by woelen]

The art of wondering makes life worth living...
Want to wonder? Look at http://www.oelen.net/science
zed
International Hazard

Posts: 1686
Registered: 6-9-2008
Location: Great State of Jefferson, City of Portland
Member Is Offline

Mood: Semi-repentant Sith Lord

My Math isn't great.

But, Coconuts?

I kind of understand Coconuts!