Transcript Introduction to Combinatorics

Introduction to Combinatorics
Section 2.3
The Fundamental Principle of
Counting
• The total number of possible outcomes of a
series of decisions (i.e. making selections from
various categories) is found by multiplying the
number of choices for each decision (or
category).
• Example1: The Pick – 3 Lottery.
– How many possible Pick – 3 numbers are
there? (You can repeat digits).
– Each digit in the Pick – 3 ranges from 0 to 9,
thus there are 10 digits to choose from.
– Therefore, there 10 x 10 x 10 = 1000 Pick – 3
numbers.
Example 2: Arizona License plates
• How many possible Arizona license plates
are there given that the first 3 places on
the plate are letters (Caps only) and the
last 3 places are digits (0 thru 9)?
• Answer: Since there are 6 places on a AZ
plate we have 6 categories. 3 categories
are letters 3 are digits. Since there are 26
letters and 10 digits the answer is:
• 26 x 26 x 26 x 10 x 10 x 10 = 17,576,000.
Example 3: Number of rows in a
truth table.
• Each simple statement has 2 choices true or
false.
• Let’s say I have one simple statement, then that
statement is true or false, hence a truth table
with 2 rows.
• If I have two simple statements then each
statement can be true or false so the number of
rows would be 2 x 2 = 4
• If I have three simple statements then the
number of rows is 2 x 2 x 2 = 8
Factorials
• Factorials are a short-hand way of writing
out a string of multiplications.
• The symbol for factorial is the exclamation
point !
• Five factorial is 5! = 5 x 4 x 3 x 2 x 1 = 120
• If n is a positive integer, then n factorial is
defined as
n! = n x (n – 1) x (n – 2) … x 2 x 1.
• As a special case 0! = 1.
Examples of factorials
•
•
•
•
•
•
•
•
•
•
•
•
0! = 1
1! = 1
2! = 2 x 1 = 2
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5,040
8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320
9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880
10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3,628,800
Wow! They start out slow but get big very fast.
Factorial Arithmetic
Compute the following:
1. (7!)(3!) = (5040)(6) = 30,240 Note this is NOT
21! = 51,090,942,171,709,440,000. I believe
you would say this as 51 quintillion, 90
quadrillion, 924 trillion, 171 billion, 709 million,
440 thousand.
2. 11! 11  10  9  8  7  6  5  4  3  2  1
5!

5  4  3  2 1
Notice that you get some cancellation.
You are left with 11!  11  10  9  8  7  6  332,640
5!