Math Is Fun Forum

Senko

Member

Registered: 2008-02-21

Posts: 2

Permutations and Combinations, que?

Hey guys, my 1st post , my head is a mess and I've had a lot of debates concerning the below question.

Original Question, "How many combinations of classes can you get in an arena team of 3 players?" - Now this reffers to World of Warcraft, there are 9 -nine- classes in the game, what we wanted to know is how many combinations of those 9 classes would be able to fit into a team of 3, without counting in the same class combo, example of same classe combo : Warrior, Mage, Priest --- Mage, Warrior, Priest, - obviously these are duplicate classes just in a different order, and therefor should NOT count in the result.

Now to make it all a whole lot more simple, we replaced the 9 classes with the numbers 1 to 9, so we could look at a table that looks something like this :
1.1.1
1.1.2
1.2.1 ( duplicate, should not count )

We started trying to find a formula for this and what the majority of people suggested was a ((9*8)*7)/6 OR 9! / 3! x (6!).

Okay, things went fine to start with, numbers were flying, but at some stage I got tired of the formulas and went to just writing this myself on pen and paper, or in this case, keyboard and word document, and counting the duplicates myself, now writing 9 classes into 3 team possibilities would've taken me all night, so I took my example as 4 CLASSES into 3 POSSIBLE SPACES. And this is my result:

1.1.1
1.1.2
1.1.3
1.1.4
1.2.1 XXX
1.2.2
1.2.3
1.2.4
1.3.1 XXX
1.3.2 XXX
1.3.3
1.3.4
1.4.1 XXX
1.4.2 XXX
1.4.3 XXX
1.4.4

2.1.1 XXX
2.1.2 XXX
2.1.3 XXX
2.1.4 XXX
2.2.1 XXX
2.2.2
2.2.3
2.2.4
2.3.1 XXX
2.3.2 XXX
2.3.3
2.3.4
2.4.1 XXX
2.4.2 XXX
2.4.3 XXX
2.4.4

3.1.1 XXX
3.1.2 XXX
3.1.3 XXX
3.1.4 XXX
3.2.1 XXX
3.2.2 XXX
3.2.3 XXX
3.2.4 XXX
3.3.1 XXX
3.3.2 XXX
3.3.3
3.3.4
3.4.1 XXX
3.4.2 XXX
3.4.3 XXX
3.4.4

4.1.1 XXX
4.1.2 XXX
4.1.3 XXX
4.1.4 XXX
4.2.1 XXX
4.2.2 XXX
4.2.3 XXX
4.2.4 XXX
4.3.1 XXX
4.3.2 XXX
4.3.3 XXX
4.3.4 XXX
4.4.1 XXX
4.4.2 XXX
4.4.3 XXX
4.4.4

The XXX represents that the number combination has already appeared earlier, and therefor does not count, according to the above, this gives us 20 non-duplicate combinations.
Wow, my head hurts, okay, let's continue, I spotted a little pattern that looks along the lines of:
4+3+2+1
3+2+1
2+1
1
So there it was, I took that pattern straight to 9, making it
9+8+7+6+5+4+3+2+1
8+7+6+5+4+3+2+1
7+6+5+4+3+2+1
And so forth...
This would give us a sum of 45+36+28+21+15+10+6+3+1 which is 165 combinations for 9 classes into a 3 man team.

Now I looked at that some more, I started working with the following, turning around the above into 1+3+6+10+15+21+28+36+45
Once I had done that, I took a piece of paper and worked on counting how many non duplicates existed if there were 1-4 classes again.
I got this result:
3 players, 1 class : 1 combo
3 players 2 classes : 4 combos
3 players 3 classes : 10 combos
3 players 4 classes : 20 combos
3 players 5 classes : 35 combos
3 players 6 classes : 56 combos
3 players 7 classes : 84 combos
3 playres 8 classes : 120 combos
3 players 9 classes : 165 combos

This can be related to the above numbers as:
1 Player = 1
2 Players 1+3=4
3 Players 1+3+6=10
4 Players 1+3+6+10=20 just as above, it adds the next number from the 1+3+6+10+15+21+28+36+45 row, ( which is obviously just the previous number number +1 )

Okay this is so confusing, Let's just give the 1-3 players a quick test, non duplicate numbers only:

1 Player combo ( 1 combo )
1.1.1

2 Player combo ( 4 combos )
1.1.1
1.1.2
1.2.2
2.2.2

3 Player combo ( 10 combos )
1.1.1
1.1.2
1.1.3
1.2.2
1.2.3
1.3.3
2.2.2
2.2.3
2.3.3
3.3.3

According to people who use the formula to calculate this, they get 84 (sometimes 504) possible combinations for 9 classes into 3 spots. 24 combinations for 4 classes into 3 spots, I'm just not getting these numbers, not on my pen and paper example anyway.

Well I give up now, it's 03:30am... Anyone feel like explaining / correcting what needs correcting in the above? All I want is the CORRECT answer for 9 numbers into 3 spots that are not DUPLICATED in ANY order, NO 1.1.2 and 2.1.1 or 1.2.1, this is the same combo!

Any feedback / assistance is greatly appriciated !.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Permutations and Combinations, que?

We started trying to find a formula for this and what the majority of people suggested was a ((9*8)*7)/6 OR 9! / 3! x (6!).

This is the formula for "9 choose 3".  In other words, it counts the number of ways of choosing if you have 9 objects and you choose three of them.  However, this isn't the case.  This would meant that you can't have repeats (two warriors).

Typically, you don't remember a formula for something like this.  Instead, you derive it.  For this problem, I'm sure there is an easier way to do it, but this is certainly the coolest way.  However, it's pretty much all going to be over anyone's head (even I still don't understand how the method is derived).  Anyways, here it goes:

We select 9 objects, and we consider any permutation (reordering) of 3 "things" to be equivalent.

So our equivalence group is S_3, the symmetric group of permutations of order 3.  This makes the characteristic equation:

Plugging in G(9, 9, 9), we get 165.
Plugging in G(8, 8, 8), we get 120

And so on.  So to solve this counting question, you simply use the polynomial:

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Senko

Member

Registered: 2008-02-21

Posts: 2

Re: Permutations and Combinations, que?

Took me 10 minutes to puzzle that stuff into my calculator but wow, I managed, this is awesome ! Thank you Ricky ! You're the best.