Combinatoricis a branch of mathematics dealing with ideas and methods for counting and arranging. Combinatorics applies mathematical operations to count quantities that are much too large to be counted the conventional way.
Counting Techniques:
A. Tree Diagrams
B. Factorial (n!)
Example: Stephanie wants to go by bus, by train or by plane to either New York, Detroit, Chicago or Cleveland. How many different ways can this be done?
Solution
12 way of Selection
Fundamental or Multiplicative Counting Principle
If a task or process is made up of stages with separate choices, the total number of choices is:
m x n x p x….., where m is the number of choices for the first stage,
n is the number of choices for the second stage,
p is the number of choices for the third stage, and so on.
Mutually Exclusive:events than cannot happen at the same time. lf this occurs, you must apply the additive counting principle or rule of sum.
Additive Counting Principle or Rule of Sum
lf one mutually exclusive action can occur in m ways, a second in n ways, a third in p ways, and soon, then there are m + n + p +. . . . . ways in which one of these actions can occur.
1.2 – Factorial Notation
Factorial– the product of all positive integers less than or equal to
n!=n x (n-1) x (n-2) x (n-3) x…x 3 x 2 x 1
For example:
2!=2 x 1
3!=3 x 2 x 1
4!=4 x 3 x 2 x 1
1. How many ways can you deal only 4 queens?
4x3x2x1 = 4! = 24
2. How many ways can you deal 2 queens?
4×3 = 12
Example 1: Evaluate
a) 6!
=6x5x4x3x2x1
=720
b) 0 !
=0
c) 5!-2!
=(5x4x3x2x1)-(2×1)
=120-2
=118
1.3 – Permutations of Distinct Object
How many different ways are there of arranging the first eight letters of the alphabet?
8x7x6x5x4x3x2x1 = 8! = 40320
Permutation: – A listing of a set of distinct objects in a specific order.
– Notation: P(n,n) or nPn
Example 1: The school choir has rehearsed 5 songs for the upcoming assembly. ln how many different orders can the choir perform the songs?
Solution: P(5,5) = 5! = 120
Example 2: How many different ways can you arrange the letters in the word PENTAGON
Solution: P(7,7) = 7! = 5040
We can also use the formula for permutations whenever we want to arrange some of the elements in the set.
ln general, the number of permutations of “n” distinct objects taken “r” at a time is:
Example 3: Four names are drawn from the 20 members of a club for the offices of President; Vice-President, Treasurer and Secretary. How many different ways can this be done?
Example 4:
a) How many ways can You deal out 13 cards from a standard deck?
Solution: P(52,13) = \(\frac{52!}{39!}\)=3.95 x 1021
b) How many ways can you deal out 4 kings?
Solution: P(4,4) = 4! = 24
Example 5:Marcus has a briefcase with a three-digit combination lock. He can set the combination himself and his favorite digits are 0, 4,5,6,7. How many permutations are there if:
a) he can not repeat an digit?
Solution: P(5,3) = \(\frac{5!}{2!}\) = 60
b) he is allowed to repeat digit ?
Solution: 5x5x5 = 53= 125
1.4 – Permutations With Identical Elements
Example 1:ln how many ways can all the letters of the word “STATISTICS” be arranged?
Solution:
Total = 10
Total of S’s =3
Total of T’s = 3
Total of I’s = 2
\(\frac{10!}{ 3!3!2!}\) = 50400
Example 2:ln how many can 4 birch trees ,7 oak trees and 2 maple trees be arranged in a straight line if one does not distinguish between trees of the same kind?
Solution:
Total = 8
Total of Birch =4
Total of Oak = 2
Total of Male = 2
