aga
Forum Drunkard
Posts: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


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]
Madness is thinking i'm not drunk.


DraconicAcid
International Hazard
Posts: 2481
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: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


Ah yes.
Obvious now you've shown it so clearly.
Thank you.
Madness is thinking i'm not drunk.


JJay
International Hazard
Posts: 2904
Registered: 15102015
Location: Western Hemisphere
Member Is Offline
Mood: planning a seminovel acetonitrile synthesis


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.
This is my YouTube channel: Extreme Red Cabbage. I don't have much posted, but I try to do nice writeups once in a while.


aga
Forum Drunkard
Posts: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


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.
Madness is thinking i'm not drunk.


JJay
International Hazard
Posts: 2904
Registered: 15102015
Location: Western Hemisphere
Member Is Offline
Mood: planning a seminovel acetonitrile synthesis


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]
This is my YouTube channel: Extreme Red Cabbage. I don't have much posted, but I try to do nice writeups once in a while.


Diachrynic
Hazard to Others
Posts: 104
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: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


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.
Madness is thinking i'm not drunk.


j_sum1
Super Moderator
Posts: 3661
Registered: 4102014
Location: Oz
Member Is Offline
Mood: Maintaining a semblance of equilibrium


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: 3661
Registered: 4102014
Location: Oz
Member Is Offline
Mood: Maintaining a semblance of equilibrium


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: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


... and if you apply the same logic to the opening question ?
Madness is thinking i'm not drunk.


JJay
International Hazard
Posts: 2904
Registered: 15102015
Location: Western Hemisphere
Member Is Offline
Mood: planning a seminovel acetonitrile synthesis


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....
This is my YouTube channel: Extreme Red Cabbage. I don't have much posted, but I try to do nice writeups once in a while.


j_sum1
Super Moderator
Posts: 3661
Registered: 4102014
Location: Oz
Member Is Offline
Mood: Maintaining a semblance of equilibrium


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


aga
Forum Drunkard
Posts: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


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]
Madness is thinking i'm not drunk.


JJay
International Hazard
Posts: 2904
Registered: 15102015
Location: Western Hemisphere
Member Is Offline
Mood: planning a seminovel acetonitrile synthesis


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]
This is my YouTube channel: Extreme Red Cabbage. I don't have much posted, but I try to do nice writeups once in a while.


aga
Forum Drunkard
Posts: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


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]
Madness is thinking i'm not drunk.


JJay
International Hazard
Posts: 2904
Registered: 15102015
Location: Western Hemisphere
Member Is Offline
Mood: planning a seminovel acetonitrile synthesis


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]
This is my YouTube channel: Extreme Red Cabbage. I don't have much posted, but I try to do nice writeups once in a while.


woelen
Super Administrator
Posts: 6385
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: 6863
Registered: 2532014
Member Is Offline
Mood: Para/Dialetic


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.
Madness is thinking i'm not drunk.


DraconicAcid
International Hazard
Posts: 2481
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.


