Pages:
1
2 
aga
Forum Drunkard
Posts: 7028
Registered: 2532014
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 1542018 by aga]


DraconicAcid
International Hazard
Posts: 2842
Registered: 122013
Location: The tiniest college campus ever....
Member Is Offline
Mood: Semivictorious.


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 exinstructor wants them.


aga
Forum Drunkard
Posts: 7028
Registered: 2532014
Member Is Offline


Ah yes.
Obvious now you've shown it so clearly.
Thank you.


JJay
International Hazard
Posts: 3320
Registered: 15102015
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: 2532014
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: 15102015
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 1642018 by JJay]
I'm no longer involved in this forum.


Diachrynic
Hazard to Others
Posts: 126
Registered: 2392017
Location: Germany
Member Is Offline
Mood: zenosyne


Didn't know you made a thread about this, aga. Anyway.
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 1542018 by Diachrynic]
Just killing time until the world ends.  Furude Rika, HNNKN


aga
Forum Drunkard
Posts: 7028
Registered: 2532014
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: 4102014
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: 4102014
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!(nr)!
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: 2532014
Member Is Offline


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


JJay
International Hazard
Posts: 3320
Registered: 15102015
Member Is Offline
Mood: resigned


This page defines permutations and combinations and gives formulas for calculating them: https://www.mathplanet.com/education/algebra2/discretemath... 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: 4102014
Location: Oz
Member Is Offline
Mood: Metastable, and that's good enough.


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


aga
Forum Drunkard
Posts: 7028
Registered: 2532014
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 1542018 by aga]


JJay
International Hazard
Posts: 3320
Registered: 15102015
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 1542018 by JJay]
I'm no longer involved in this forum.


aga
Forum Drunkard
Posts: 7028
Registered: 2532014
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 1542018 by aga]


JJay
International Hazard
Posts: 3320
Registered: 15102015
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 1542018 by JJay]
I'm no longer involved in this forum.


woelen
Super Administrator
Posts: 6612
Registered: 2082005
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!*(NK)!)
If order does matter, then you have N!/(NK)! possibilities.


aga
Forum Drunkard
Posts: 7028
Registered: 2532014
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: 122013
Location: The tiniest college campus ever....
Member Is Offline
Mood: Semivictorious.


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
nonrepetition 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 freeradical 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 exinstructor wants them.


AJKOER
International Hazard
Posts: 2563
Registered: 752011
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 1952018 by AJKOER]


SWIM
National Hazard
Posts: 312
Registered: 392017
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: 2532014
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
Super Administrator
Posts: 6612
Registered: 2082005
Location: Netherlands
Member Is Offline
Mood: interested


A nice exercise for aga would be to find the formula for all possible isomers of alkanes C_{n}H_{2n+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 (nbutane, isobutane)
5 > 3 (npentane, 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 Catom and 1 bond on the Hatom 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
nontrivial, but it should not be extremely hard to write it.
[Edited on 22518 by woelen]


zed
International Hazard
Posts: 1686
Registered: 692008
Location: Great State of Jefferson, City of Portland
Member Is Offline
Mood: Semirepentant Sith Lord


My Math isn't great.
But, Coconuts?
I kind of understand Coconuts!
https://www.youtube.com/watch?v=Z47NljuPBFE


Pages:
1
2 
