Combinatorics
We will try to analysis the combinatorial questions logically steps by steps here. This is a way of analyzing question, not the way to answer the question. Using this analytical method it's very easy to give out the required formula.
Definition of set
S = {a1,a2,…an}, there are n elements. We can say |S| = n.
Now we analysis the combinatorial questions by putting the "possible choice" as the elements.
Example 1: Choose one from apple, orange and banana, in how many ways you can choose?
The possible choice (S) = {Apple, orange, banana}, |S| = 3
Therefore we have 3 choice.
In the case when we choose more than one
Example 2: There're 3 coins, $1, $2 and $5 respectively. In how many ways we can choose two of them?
Since combination is not yet introduced, we use counting here.
The possible choice (S) = {$1+$2, $1+$5, $2+$5}, |S| = 3.
This is the expression when we choose more than one.
Remember, we only choose one from the set only.
Adding principle
We say "we have |A|+|B| choices when we choose one from A OR choose one from B."
Mathematically, |A|+|B| = |A+B|. We can visualize this result easily.
For example, A = {apple, orange} and B = {banana}. Choosing one from A or B would gives {apple, orange and banana}. Which gives 3 choice = 2+1.
Example 3: In a restaurant providing Chinese and Japanese dish, there're 7 Chinese and 9 Japanese dishes available. In how many ways we can choose one from it?
We have |Chinese dish| = 7, |Japanese dish| = 9, so |Chinese dish OR Japanese dish| = 7+9 which is 16.
Multiplying principle
We say "we have |A|x|B| choices when we choose one from A AND choose one from B."
Consider A = {a1,a2,…ax}, B = {b1,b2,…by}, then one from A and one from B gives S = {a1+b1,…a1+by,a2+b1,…ax+by} which gives |A| x |B|.
Example 4: In the restaurant there're 7 Chinese dishes and 4 types of soup. In how many ways we can choose one dish and one soup?
Consider |Chinese dish| = 7, |soup| = 4, we have 7*4 = 28 choices.
Full arrangement
When we arrange n elements in order, there're n! choices.
Proof: You have n choices to put the first elements, (n-1) choice to put the second elements…totally giving you 1*2*3*…*(n-1)*n = n! choices.
Example 5: In how many ways we can arrange 5 letters, "A,B,C,D,E" in order?
We have 5! = 120 choices.
Repetitions
When we arrange n elements in order, with x of them is the same (identical), number of choices is given by n!/x!.
Example 6: In how many ways we can arrange 5 letters, "A,B,C,C,D" in order?
We have 5!/2! = 60 choices.
Example 7: A students claims that he get 1A, 2B and 2D in HKALE. How many different possible result he/she could get in the exam?
We have two repeated elements. The number of possibility is 5!/(2! * 2!) = 30.
Identical and different elements
Identical elements mean that the permutations are useless. For example, you can't arrange "element x, element x" in order because they are the same.
Different elements means that it makes difference when you permute them, like apple and banana.
Permutation
The standard form of combination nPr is "choose r elements from n and arrange them in order"
nPr = n! / (n-r)!, we can visualize this: oooooooooxxxxxxxxxxxxxx
There're n elements, "o" is the r chosen elements and "x" is the n-r remaining elements.
Step 1) we arrange all of them in order. : n!
Step 2) we know that the remaining elements are identical each other because we don't care their permutation. : 1/(n-r)!
Therefore we get nPr = n!/(n-r)!
Example 8: In how many ways we arrange 7 of 10 teachers to teach 7 classes? (test)
We have 10P7 = 604800 ways.
Combination
The standard form of combination nCr is "choose r elements from n". Since we don't need permutation, elements are identical each other. For example, choosing "apple and banana" is same as choosing "banana and apple".
nCr = n! / [r! (n-r)!]
Example 9: In how many ways we can choose 10 distinct balls from 12?
We have 10C12 = 66 ways. , we can visualize this: oooooooooxxxxxxxxxxxxxx
There're n elements, "o" is the r chosen elements and "x" is the n-r remaining elements.
Step 1) we arrange all of them in order. : n!
Step 2) we know that the remaining elements are identical each other because we don't care their permutation. : 1/(n-r)!
Step 3) we don't care the permutation of chosen elements as well. : 1/r!
Combining gives nCr = n! / [r! (n-r)!]
One important identities is that : nCr (r!) = nPr we have to permute the chosen elements.
Example 10: In how many ways we arrange 7 of 10 teachers to teach 7 classes? (test)
We can first choose 7 from 10, then permute them.
Number of ways = 10C7 * 7! = 604800.
Another identities is nCr = nC(n-r).
Mathematically they are the same and can be proved easily.
Visualizing the problem: Choosing r from n is equivalent to choosing (n-r) from n that is unwanted. So they are the same.
More complicated cases: elements and boxes
When we arrange teachers to classes, we can say "teachers" is the elements while "classes" is the boxes. In this case the classes are different each other, but sometimes they maybe the same.
Example 11:
a) In how many ways we put 10 marbles into 5 different boxes with 2 marbles in each box?
We choose 2 from 10 in the first box, 8 from 2 in the second one and so on…
Number of ways = 10C2 * 8C2 * 6C2 * 4C2 * 2C2 = 113400
Alternative: the elements in the boxes are identical. There are 5 boxes so 5 times of repetition of 2 elements. There are 10 elements in total.
Number of ways = 10! / (2!)5 = 113400
b) The above boxes are distributed to 5 people. In how many ways the marbles can be distributed to the people?
Note that we have 2 times of permutation here. The first one is marble to box, the second one of marble to people. Number of ways = 113400 * 120 = 13608000.
c) In how many ways we put 10 marbles into 5 identical box with 2 marbles in each box?
Consider the permutation between the 5 identical box, number of ways = 113400/5! = 945.
Example 12: There're 3 boys and 4 girls. They are going to be arranged in a row.
a) How many ways can be arrange them if two girls must at the two ends?
b) How many ways can be arrange them no men are standing together?
We have two ways to solve (a).
Method 1:
1) Select the two girls and put them at the two ends = 4C2 * 2! = 12
2) Permute the remaining people = 5! = 120
Overall choices = 12*120 = 1440
Method 2:
1) Arrange the boys to sit in the middle = 5P3 = 60
2) Permute the girls for the remaining seats = 4! = 24
Overall choice = 60 * 24 = 1440
(b)
1) We permute the girls = 4! = 24
2) Boys can only standing at the side or between the girls, that implies that they have 5 possible position (oGoGoGoGo), so we have 5P3 = 60 choices
Overall choice = 24*60 = 1440.
Problems:
State the number of choices for the following cases:
1) Choosing 5 girls and 4 boys from 10 boys and 10 girls.
2) Permuting the words APPLE and BANANA.
3) Choosing 3 girls and 5 boys from 8 boys and 8 girls and arrange them in a row for:
a) No restriction.
b) Two girls must be at the two ends.
c) A particular boy must be arranged between two girls (GBG)
4) There are 3 rows of seats. There are 4 seats per row. 6 people are sitting on some of the seats. For the number of arrangement if:
a) No restriction
b) A particular person must sit at the leftmost seat for any row.
c) One of the rows has to be fully seated.
5) There are 9 different marbles.
a) Putting them into 3 identical boxes with 3 each.
b) Putting them into 3 different boxes with 3 each.
c) Putting them into 3 identical boxes with no restriction on number of marbles of each box (no marbles for a certain box is permitted).*
d) Putting them into 3 identical boxes with no restriction on number of marbles of each box (no marbles for a certain box is NOT permitted).*
6) N people are arranged in a circle table. Show that the number of arrangements is (N-1)!.*
Questions with * would be harder.
No comments:
Post a Comment