First up we have counting techniques, which is a relatively straightforward concept but sometimes the questions can be annoying (as with so many other areas of maths...). The main types of counting techniques you need to know for 3CD are permutations and combinations.
Permutations are basically about how many ways a group of objects can be arranged. For example, if you get three characters, say, Azizi, Bentley and Cynder, and put them in a line, in how many ways can they be arranged? You'll find that the answer is six:
ABC
ACB
BAC
BCA
CAB
CBA
It's easy to work that out when you've got so few people. But what if you have 100 people? How many ways can they be arranged? (Not that you'd ever need to know the answer to this question, but still.) This is where the concept of the factorial comes in.
Let's go back to our 3-character example. Instead of thinking about who's going to go where etc., let's slow right down and think of an empty space with 3 spots waiting to be filled with the three characters:
_ _ _
Now let's choose who's going to fit into the first slot. There's 3 options, since nobody's been picked yet.
3_ _
When we move over to the second slot, since one person has been taken, there's only 2 options left.
3 2 _
Finally, that leaves only one person to fill the last slot.
3 2 1
For each character that goes in the first slot, there are 2 different permutations, as there are 2 different characters who can fit in the second slot (the last slot is then a given since there's only 1 character left by that point). Since there are 3 characters who can go in the first slot, this gives us 3 characters x 2 permutations each = 6 total permutations.
Sorry if that wasn't a good explanation. Here's a tree diagram that might help:
There's a logical pattern that holds true no matter how many people you have to arrange. Let's say you have n people to arrange. Therefore there will be n possibilities for the first slot, (n - 1) for the second, (n - 2) for the third and so on. This gives you n(n - 1)(n - 2) x ... x 1 as the total number of permutations.
Thankfully, you don't have to write it all out in full, thanks to the handy dandy factorial symbol (which is just an exclamation mark: !)
Hence, the number of ways you can arrange 3 people is 3! (3 x 2 x 1)
The number of ways you can arrange 4 people is 4! (4 x 3 x 2 x 1)
and the number of ways you can arrange n people is n!
That's easy, isn't it?
Now on to combination!
Combinations is basically the number of different subsets you can get from one big set.
I'm going to use my year 10/11 maths teacher's example for this one, because it's so awesome. I'll just change the characters' names though since I don't remember what the original names were.
Darius, Ember, Flame, Gaul and Hunter all like earthworms, so they all decide to set up an Earthworm Appreciation Society. At first, they decide to create a subcommittee, with a president, vice-president and secretary, appointed in that order. This is where you draw on your permutations knowledge, as first you've got 5 options for president, then 4 for vice-president, then 3 for secretary, resulting in 5 x 4 x 3 = 60 ways in which the subcommittee members can be elected.
Later on, instead of having different ranks within the subcommittee, the Earthworm Appreciation Society members decide that they're going to make all 3 subcommittee members of equal rank (which leaves you wondering what happens to the other two... well, I guess all animals are equal, but some are more equal than others). How many ways can the subcommittee be selected?
No, the answer is not 60. Why? Because, this time, everyone's of equal rank, so Darius-Ember-Flame is the same subcommittee as Ember-Darius-Flame.
How do we get around this problem? you must be asking. Well, first consider how many ways each subset can be arranged. Each subset consists of 3 characters. From the previous thingo on permutations, we know that they can be arranged in 3! = 3 x 2 x 1 = 6 different ways. Hence the Darius/Ember/Flame subset appears 6 times:
DEF
DFE
EDF
EFD
FDE
FED
and each other subset would, likewise, appear 6 times. Hence, to get the number of possible subcommittees, you need to divide 60 by 6 in order to avoid counting subsets 6 times each. This leaves us with 10 possible subcommittees:
DEF
DFG
DGH
DEG
DEH
DFH
EFG
EFH
EGH
FGH
There's also a general rule for this too. Let's first take a look at why it works.
When working out the total number of permutations (remember, permutations is where order matters) for n objects in r [number of] slots, it's a case of multiplying n x (n - 1) x (n - 2) etc. all the way until you've filled up all r slots. An easy way to express this is n!/(n-r)!
I'm not sure how to explain this without being super confusing, but I'll try. n! is the product of all of the numbers from n all the way to 1. The thing is, you only need the product of r of these numbers, because you only need r slots. The remaining number of numbers that you have remaining (i.e. the numbers between 1 and n that don't need to be used) can be expressed by (n - r).
To find the product of just the numbers that you need, n!/(n-r)! works because n! is essentially n x (n - 1) x (n - 2) x ... x (n - r) x ... x 1 and (n - r)! is (n - r) x (n - r - 1) x ... x 1. Hence when you divide n! by (n - r)! you'll find that all of the terms from (n - r) and beyond cancel each other out, just leaving you with the product of the top r numbers. Nifty, right?
Now, as I stated before, working out the total number of permutations isn't enough- you have to then divide by the number of permutations within each subset of r objects, which is r!. This leaves us with a final equation of (drumroll):
The thingo on the left is the notation for combinations (well, one kind of notation anyway. You might see other notation involving P for permutations or C for combinations, with the two numbers on top left and bottom right). The number on the top is the total number of stuff you have to choose from, while the number on the bottom is the number of stuff you want in the subsets. Make sure that the brackets are roundish, otherwise it'll look like a matrix.
That's pretty much all the main basic stuff on permutations and combinations. Because I can be bothered, however, here's some pointers on how to tackle the problem solving varieties of these questions.
Problem Solving: Permutations and Combinations
The problems that you will encounter when it comes to permutations and stuff generally involve some restriction, such as that someone must be on the end of the line, or two people must stand together, or something. I'll show you some basic techniques for solving these, but some are a bit trickier. Just do as many as you can to develop that problem-solving brain of yours!
Oh yeah and, apart from reading the examples in the textbook to get a feel for the types of questions they might ask, I'm making up these questions on my own, which is why they're so weird.
Question 1
Eliona, Sharon, Karyn, Maria and Sarah are lining up for their flu jabs. In how many ways can they line up if:
a) Sarah must go first?
b) Sarah must go first and Karyn must go fourth?
c) Maria is behind Sharon? (Sarah doesn't necessarily have to be first this time)
Question 2
a) Out of 8 humans and 6 Vulcans, a crew consisting of 4 humans and 4 Vulcans is required. How many possible crews are there?
b) One of the humans is Captain James T. Kirk. How many of the crews contain Captain Kirk?
Question 3
Hienuri Kayleuetski is on a chat room with her friends, Diani, Ashleigh and Fiona, who are all using Ashleigh's computer together. To distinguish themselves, they refer to each other as "meep," "moop" and "murp" and encourage Kayleuetski to guess who is who. Kayleuetski's first guess is that Diani is "meep," Ashleigh is "moop" and Fiona is "murp," but is then informed that all of her guesses were wrong. How many possible combinations remain?
Question 4
Neisure has 10 uni books to arrange on her shelf, 4 Psychology, 3 Education and 3 Magic (she lives in an alternate universe where magic is possible!!). How many ways can she arrange them if:
a) they don't have to be arranged in any particular order?
b) books of the same subject are to be kept together?
c) the 3 Magic books must all be together on either end of the shelf, but the other 7 books can be arranged in any order?
Question 5
A TV talk show host wants to invite 3 characters to his upcoming show. His list of potential candidates consists of Alakazam, Blissey, Charizard, Loudred, Miltank, Seviper and Zangoose. How many possibilities are there if:
a) there are no restrictions?
b) he decides not to invite both Seviper and Zangoose (since they hate each other)?
c) he decides not to invite either Seviper or Zangoose, fearing that inviting either would just incite more rivalry?
d) he decides to invite both Seviper and Zangoose just to add some excitement to the show?
Answers
1a) Since Sarah must go first, that only leaves us with 4 characters in 4 possible positions. Hence the number of possible permutations is 4! = 24 ways in which they can line up.
1b) Since two positions are fixed, that only leaves us with 3 characters in 3 possible positions, leaving us with 3! = 6 ways in which they can line up.
1c) To do a problem like this, I generally split it up into different categories and then add them together: if Sharon is first, second, third or fourth (she can't be fifth since Maria has to be behind her). Then I draw boxes for each position and then write numbers in each box corresponding to how many options I have (see my explanation for permutations).
If Sharon is first, Maria will definitely be after her. And since Sharon's position is fixed, that leaves us with 4 characters in 4 possible positions, with 4! = 24 ways.
If Sharon is second, only 3 characters can be in front of her (Sarah, Karyn or Eliona). The other three can be arranged in any order.
[3][1][3][2][1] = 3 x 1 x 3 x 2 x 1 = 18
If Sharon is third, only 3 characters can be first (Sarah, Karyn or Eliona) and 2 characters can be second (those three minus whoever goes first). The other two can be arranged in any order.
[3][2][1][2][1] = 3 x 2 x 1 x 2 x 1 = 12
If Sharon is fourth, Maria must be last, and the other three can be arranged in any order, giving 3! = 6.
Hence the total number of ways in which they can be arranged is 24 + 18 + 12 + 6 = 30 + 30 = 60.
2a) Use the Combinations technique to "choose" 4 humans and to "choose" 4 Vulcans, then multiply the two together.
For humans: nCr(8, 4) (that's the notation used on many calculators) = 70
For Vulcans: nCr(6, 4) = 15
Hence total number of possible crews = 1050
The reason why this works is, for every subset of humans chosen, there are 15 Vulcan subsets that they could be partnered up with. Hence you need to multiply the 70 different groups of humans with the 15 different groups of Vulcans that they could be partnered up with.
2b) Since one of the humans has been "chosen," that leaves us with only 7 humans left to choose from and 3 slots left to fill. Hence, the number of human teams is nCr(7, 3) = 35 and the number of Vulcan teams remains the same (15) which gives us 35 x 15 = 525 different crews all containing Captain Kirk.
3. Yes, I actually did get given a similar problem in real life once, except I skimmed over the part where my friends said "all wrong" and then thought "there's 3! permutations, and I've already guessed one, leaving me with 5 more to go!" No, this is not the case. (I was told to "learn to math" at this point.) And yes, this was a bit of a trick question.
Since Diani is definitely not "meep," this leaves us with two other possibilities: Ashleigh or Fiona.
If Ashleigh is "meep," this leaves us with Fiona and Diani. Fiona can't remain "murp," hence there is only one other option for her: "moop." Diani then takes the last available slot.
If Fiona is "meep," this leaves us with Ashleigh and Diani. Ashleigh can't remain "moop," hence there is only one other option for her: "murp." Diani then takes the last available slot.
Hence there are only 2 possible permutations remaining.
4a) The answer's just 10! = 3 628 800.
4b) To do this, I prefer to think of all of the books of the same subject as just being one book, and then adjusting the number of "slots" accordingly. Therefore I would think of it as 3 books needing to be arranged in 3 different slots, which gives us 3! = 6 ways in which the subjects can be arranged.
After that, you have to multiply by the number of ways books of the same subject can be arranged amongst themselves. The four Psychology books can be arranged in 4! = 24 ways, and the Magic and Education books can be arranged in 3! = 6 ways each.
Then you need to multiply the lot together, to give 6 x 24 x 6 x 6 = 5 184 possibilities.
4c) As in 4b), just think of all three Magic books as simply being one book. This "book" must be at either end, leaving us with 7 slots in which the 7 other books can be arranged. The Magic books themselves can be arranged in 3! = 6 different ways. This leaves us with (7!)(3!)(2) ways in which the books can be arranged (the x2 is because the Magic books can be at either end). Total number of possibilities is 60 480.
5a) nCr(7, 3) = 35 different ways
5b) First see how many possibilities there are if Seviper is definitely coming and Zangoose is definitely not coming. Since Seviper takes up one slot, and Zangoose can't come, that leaves us with 5 potential characters remaining and 2 slots, or nCr(5, 2) = 10 ways. Multiply this by 2 to get the other possibility (i.e. Zangoose comes and not Seviper), and you've got 20 different ways in which to select 3 candidates.
5c) Since neither Seviper nor Zangoose can come, we only have 5 characters to fit into the 3 slots. nCr(5, 3) = 10 possibilities.
5d) Seviper and Zangoose fill up one slot each, so that leaves 5 potential characters and only 1 slot, so only 5 different ways in which to select 3 candidates by this criteria.
