Chapter 5
Counting

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter5/self_assessments.html - Chapter 5 self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter5/extra_examples.html - Extra examples with solutions.

Permutations and Combinations - http://easycalculation.com/statistics/permutation-combination.php

5.1 The Basics of Counting

Introduction

Suppose a password consists of 4 digits - how many unique passwords are possible?

How many cards must be dealt to guarantee at least 3 are the same suit?

 

Basic Counting Principles

Definition

Product rule For a procedure with two independent tasks, n1 ways to do task one AND n2 ways to do task two, there are n1 * n2 ways to do the procedure.   For each one n1 way, there are n2 ways to do the procedure.   Applies to counting things (e.g., a procedure or item) that can be broken down into independent parts (or steps): p1, p2, ..., pk    Rule: If an operation consists of k independent steps and the first step can be performed in n1 ways AND the second step can be performed in n2 ways (regardless of how the first step is performed) AND : the kth step can be performed in nk ways n1 * n2 * ... * nk ways of doing the entire thing.

Example

3 men	2 women
Curly Moe Larry	Alice Sally

Is picking a man independent of picking a woman?

How many different ways to pick one man/woman dance couple?

Step 1: Pick a man, n₁ = 3 ways

Step 2: AND pick a woman, n₂ = 2 ways

Curly & Alice	Moe & Alice	Larry & Alice
Curly & Sally	Moe & Sally	Larry & Sally

n = n₁ * n₂ = 3 * 2 = 6

Example

Suppose a password consists of 3 digits - 647, 884, etc.

Question 5.1    Is picking digit 1 (0..9) independent of picking digit 2 (0..9), etc.

 

How many different passwords are possible?

3 parts to password

Pick p₁ AND p₂ AND p₃

p₁ can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

n₁ = 10

p₂ can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

n₂ = 10

p₃  can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

n₃ = 10

n = n₁ * n₂ * n₃ = 10 * 10 * 10 = 10³ = 1,000

 

Example

Suppose a password consists of at least 3 digits followed by 2 letters - 647HR or 884ZY

Question 5.2    Is picking digits 1, 2 and 3 (0..9) independent of picking letters 4 and 5 (A..Z)?

How many different passwords are possible?

5 parts to password

p₁ AND p₂ AND p₃ AND p₄ AND p₅

p₁ can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

n₁ = 10

p₂ can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

n₂ = 10

p₃  can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

n₃ = 10

p₄ can be A, B, C, ..., Z

n₄ = 26

p₅ can be A, B, C, ..., Z

n₅ = 26

n = n₁ * n₂ * n₃ * n₄ * n₅ = 10 * 10 * 10 * 26 * 26 = 10³ * 26² = 676,000

Question 5.3 - How many different passwords are possible with

1. 5 digits?
    
2. 5 letters?
    
3. 2 digits and 2 letters?
    
4. 32 binary digits?

 

Using Set Theory for Product Rule: For each part pi there is a set Ai, where the set Ai contains all the different ways to perform or build part pi   There are |A1| * |A2| * ... * |An| ways for entire thing   Or using the Cartesian product of all the sets, and then taking the size of the resulting set, get the same number: |A1  X  A2  X ... X  An|

Example

Suppose a password consists of at least 3 digits followed by 2 letters - 647HR or 884ZY

How many different passwords are possible?

5 parts to password

p₁ AND p₂ AND p₃ AND p₄ AND p₅

p₁ consists of the set A₁ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

p₂ consists of the set A₂ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

p₃ consists of the set A₃ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

p₄ consists of the set A₄ = {A, B, C, ..., Z}

p₅ consists of the set A₅ = {A, B, C, ..., Z}

|A₁| * |A₂| * |A₃| * |A₄| * |A₅| = 10 * 10 * 10 * 26 * 26 = 10³ * 26² = 676,000

Remember that |A₁| is the cardinality of A₁

Question 5.4

Men	Women
Curly Moe Larry	Alice Sally

1. Men x Women
    
2. | Men x Women |
    
3. | Men | * | Women |
    

Question 5.5

1. {1,2} x {R,G,B}?
    
2. | {1,2} x {R,G,B} | ?
    
3. Give two of the tuples from the Cartesian product: {1,2} x {R,G,B} x {a,b}?
    
4. | {1,2} x {R,G,B} x {a,b} |?
    
5. | {1,2} | * |{R,G,B}| * |{a,b}|?

 

Question 5.6

Your favorite restaurant has a combination dinner menu.

Drink	Appetizer	Entree	Dessert
Tea	Fried calamari	Hamburger	Ice cream
Coffee	Sushi	Steak	Apple pie
Wine	Buffalo wings	Chicken	Brownie
Beer	Cheeze Wiz	Fried Fish
	Samosa	Burrito

Step 1: Pick a drink - how many choices?

Step 2: AND Pick an appetizer - how many choices?

Step 3: AND Pick an entree - how many choices?

Step 4: AND Pick a dessert - how many choices?

1. Generate two tuples (dinners) from the Cartesian product Drink x Appetizer x Entree x Dessert.
    
2. |Drink| * |Appetizer| * |Entree| * |Dessert|?
    
3. | Drink x Appetizer x Entree x Dessert | ?
    
4. How many different dinners are possible?

 

Question 5.7

1. Suppose a 5-bit string - how many unique values (e.g. 00000, 00001, ..., 11111) are possible?
    
2. Is selecting each bit independent of selecting the others?

 

Question 5.8

1. How many license plates can be made using 1 decimal digit?
    
2. How many license plates can be made using 2 digits?
    
3. How many license plates can be made using 2 digits followed by 4 letters?
    
4. How many license plates can be made using 4 digits followed by 2 letters?

 

Question 5.9

1. A multiple choice test has 2 questions and 4 answers for each question. How many possible ways to answer the test?
    

2. A multiple choice test has 10 questions and 4 answers for each question. How many possible ways to answer the test?
    

3. A test has 5 true/false and 6 multiple choice questions with 4 answers for each question. How many possible ways to answer the test?

    

Question 5.10

How many bit strings of length 8 begin and end with a 1?

There are 64 = 2⁶, 6-bit strings.

 

Example

 How many one-to-one functions are there from a set with 3 elements to a set with:

A = {1,2,3}

f: A → B

1. 2 elements?   B = {a,b}    0 because would not be a function.

                                            Each element in the domain A of f must have a defined mapping.

                        Example:      f(1) = a, f(2) = b, f(3) = ?

2. 4 elements?

   B = {a,b,c,d}

   4 ways:    f(1)=a, f(1)=b, f(1)=c or f(1)=d

   3 ways:    If f(1)=a then f(2)=b, f(2)=c or f(2)=d

   2 ways:    If f(1)=a and f(2)=b then f(3)=c or f(3)=d

   4*3*2 = 24
    

In general, for A with m elements and B with n elements, m≤n

f: A → B

n(n-1)(n-2)...(n-m+1) one-to-one functions.

4(4-1)(4-3+1) = 4*3*2 = 24

 

Example

 How many one-to-one functions are there from a set with 5 elements to a set with 5 elements?

5(5-1)(5-2)(5-3)(5-5+1) = 5*4*3*2*1 = 120

Pick 1   2     3      4      5

 How many one-to-one functions are there from a set with 3 elements to a set with 6 elements?

6(6-1)(6-3+1) = 6*5*4 = 120

Pick 1   2       3

 How many one-to-one functions are there from a set with 6 elements to a set with 10 elements?

10(10-1)(10-2)(10-3)(10-4)(10-6+1) = 10*9*8*7*6*5

Pick  1    2        3       4       5          6

 

Question 5.11

Suppose you convince all your class mates to send you $10.00 - one class has 30 students, another 50, and a third 20.

How much money do you receive, assuming no students are in more than one class with you?

$10*30*50*20 = $300,000?

$10*(30+50+20) = $1000?

$10*(29+49+19) = $970?

Is this a Product Rule problem?

 

Question 5.12

a. What is j after the following has been executed?

j := 0 for  i1 := 1 to 100 j := j+1

b. What is the value of the following?

c. What is k after the following has been executed?

k := 0 for  i1 := 1 to 3 for  i2 := 1 to 2 k := k+1

k i1 i2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 1 6 3 2

d. What is the summation notation for the above?

 

Question 5.13

What is k after each of the following has been executed?

a. k := 0 for  i1 := 1 to n1 for  i2 := 1 to n2 k := k+1

b. k := 0 for  i1 := 1 to n1 for  i2 := 1 to n2 for  i3 := 1 to n3 k := k+1

c. k := 0 for  i1 := 1 to n1 for  i2 := 1 to n2 : for  im := 1 to nm k := k+1

 

Definition

Sum rule If a task can be done in either one of n1 OR one of n2 ways, where none of the n1 ways is the same as any of the n2 ways, there are n1 + n2 ways to do the task.   Applies to counting one thing (e.g., a procedure or item) that cannot be broken down, it can be done n different ways: {w1, w2, ..., wm} where wi is the i ways.   The n different ways come from m different sets A1, A2, ... Am, with the following restrictions on Ai: A1  ∩  A2  ∩ ... ∩  Am = ∅ A1  U  A2  U ... U  Am = {w1, w2, ..., wm} Rule: Where A is the union of m distinct mutually disjoint subsets, A1, A2, ..., Am |A| = |A1| + |A2| + ... + |Am| ways to do the one thing or |A| = |A1  U  A2  U ... U  Am| Notice that x ∈ A1 U  A2  U ... U  Am can be read as x ∈ A1or A2 or... or Am

 

Question 5.14

Your favorite restaurant has a menu. You only want one item. How many different choices?

Drink OR Appetizer OR Entree OR Dessert

Drink A1	Appetizer A2	Entree A3	Dessert A4
Tea	Samosa	Burrito	Brownie
Coffee	Sushi	Steak
Wine

a.    A₁  ∩  A₂  ∩  A₃ ∩  A₄ = ?

b.    A₁  U  A₂  U  A₃  U  A₄ = ?

c.    |A₁  U  A₂  U  A₃  U  A₄| = ?

d.    |A₁| + |A₂| + ... + |A_n| = ?

 

Question 5.15

a.    How many license plates can be made using 1 digit (0-9)?

This is A₁.

b.    How many license plates can be made using 2 digits?

This is A₂.

c.    How many license plates can be made using 3 digits?

This is A₃.

A₁  ∩  A₂  ∩  A₃ = ?

|A₁| + |A₂| + |A₃| = ?

A₁  U  A₂  U  A₃ = ?

d.    How many license plates can be made using 1 OR 2 OR 3 digits?

e.    How many license plates can be made using 2 digits followed by 4 letters?

f.    How many license plates can be made using 4 digits followed by 2 letters?

g.    How many license plates can be made using 2 digits followed by 4 letters OR 4 digits followed by 2 letters?

 

Example

How many lower-case character strings of length 4 or less?

Length 4 = 26⁴ strings.

Length 3 = 26³ strings.

Length 2 = 26² strings.

Length 1 = 26¹ strings.

Length 0 = 26⁰ strings.

26⁴ + 26³ + 26² + 26¹ + 26⁰ strings of length 4 or less.

Question 5.16

What is k after the following has been executed?

k := 0 for  i1 := 1 to n1 k := k+1 for  i2 := 1 to n2 k := k+1

k := 0 for  i1 := 1 to n1 k := k+1 for  i2 := 1 to n2 k := k+1 : for  im := 1 to nm k := k+1

What is the summation notation for the above?

 

More Complex Counting Problems

Examples

How many strings of 3 digits do not contain the same digit twice?

10 ways to pick first digit.

9 ways to pick second digit.

8 ways to pick third digit.

10*9*8 by Product Rule

How many strings of 3 digits begin with an odd digit?

5 ways to pick first digit.

10 ways to pick second digit.

10 ways to pick third digit.

5*10*10 by Product Rule

How many strings of 3 digits have exactly two digits that are 4s?

3 ways to have two 4s.                   

44x, 4x4, and x44 are disjoint.

9 ways to have x other than 4.    

 9+9+9 by Sum Rule

 

Question 5.17

You have 10 complete pairs of shoes.

a.    Suppose you don't care if the left and right shoes match. How many pairs can you choose from?

First: pick a left shoe.

Second: pick a right shoe.

b.    Did you use the Sum rule?         Pick left shoe OR pick right shoe.

c.    Did you use Product rule?           Pick left shoe AND pick right shoe.

d.    Suppose you want different shoes on each foot.  How many pairs can you choose from?

 

Example

Internet addresses are 32 bits, usually listed as 4 groups of 8 bits: 149.160.16.3

Identify computers as members of a network.

Consist of:

netid : hostid

Class A

7-bit netid : 24-bit hostid

1111111 not allowed as netid

all 0's and all 1's not allowed as hostid.

How many Class A addresses are there?

2⁷-1 * 2²⁴ -2 = 2,130,706,178

Class A, B, C, D, E are disjoint.

Can have Class A OR B OR C OR D OR E address.

By Sum Rule:

Class A + Class B + Class C + Class D + Class E addresses

 

The Inclusion-Exclusion Principle

Definition

Inclusion-Exclusion Principle for Two Sets | A1 ∪ A2 | = | A1 | +  | A2 |  - | A1 ∩ A2 |

Example

Your favorite restaurant has a dinner menu. You only want one item. How many different items can you choose?

Appetizer OR Entree

Appetizer	Entree
Fried calamari	Hamburger
Sushi	Steak
Buffalo wings	Chicken
Cheeze Wiz	Fried Fish
Samosa	Burrito
Burrito

| Appetizer ∪ Entree  | =

| Appetizer |  + | Entree | - | Appetizer ∩ Entree | =

6 + 5 - 1 = 10

 

Definition

Inclusion-Exclusion Principle for Three Sets | A1 ∪ A2 ∪ A3 | = | A1 | +  | A2 | +  | A3 | - | A1 ∩ A2 | - | A1 ∩ A3 | - | A2 ∩ A3 |

Example

Your favorite restaurant has a dinner menu. You only want one item. How many different items can you choose?

Appetizer OR Entree OR Dessert

Appetizer	Entree	Dessert
Fried calamari	Hamburger	Ice cream
Sushi	Steak	Apple pie
Buffalo wings	Chicken	Brownie
Cheeze Wiz	Fried Fish	Pop Tart
Samosa	Burrito	Chicken
Burrito		Sushi

| Appetizer ∪ Entree ∪ Dessert | =

|Appetizer|+|Entree|+|Dessert| - |Appetizer ∩ Entree|-|Appetizer ∩ Dessert|-|Entree ∩ Dessert| =

6+5+6 - 1-1-1 = 14

Example

How many uppercase strings of length 2?

|uppercase| * |uppercase| = 26² = 26*26

 

How many uppercase and digits strings of length 2?

|uppercase U digits| * |uppercase U digits| = (26+10)² = (26+10)*(26+10)

 

How many upper-case and digits strings of length 2 without repeats? 00, AA, ZZ, etc.

|uppercase U digits| * |uppercase U digits| - | repeats | = (26+10)*(26+10) - 36

 

Question 5.18

a.    A    How many passwords of 3 digits?

b.    A₁   How many 3 digit passwords start with 1?

1xx

How many of these end with a 2?

1x2

c.    A₂   How many 3 digit passwords end with 2?

xx2

How many of these start with a 1?

1x2

d.    How many 3 digit passwords start with 1 AND end with 2?

    1xx ∩xx2 = 1x2

    | A₁ ∩ A₂ |

e.    How many 3 digit passwords start with 1 OR end with 2?

    1xx U xx2

    | A₁ ∪ A₂ | = | A₁ | + | A₂ | - | A₁ ∩ A₂ |

 

Question 5.19

a.    How many passwords of 2 lowercase characters?

b.    How many passwords of 2 lowercase characters contain no 'a'?

3 ways for 'a'

   a-   -a   aa

26² - 25 - 25 - 1 have no 'a'

c.    How many passwords of 2 lowercase characters contain at least one 'a'?

26 + 26

 

Tree Diagrams

Useful when small number of possible choices that can be graphically displayed.

 

Example

Number of bit strings of length 3 with two consecutive 1's.
                                        

                                     /      \
                                  0          1
                                /  \        /   \
                             0     1      0     1
                           /  \   /  \   /  \   /  \
                         0    1 0   1 0   1 0   1

                                       0        1
                                       1        1
                                       1        0

Example

Number of bit strings of length 4 without two consecutive 1's.

 

Question 5.20     Draw tree of number of bit strings of length 3 with no consecutive 1's.

 

Example

Best 3 out of 5 games between Teams 1 and 2.

How many different ways can a team win in 3 games? In 4 games? In 5 games?

Where Multiplication Rule Does Not Easily Apply

Example

Three officers - president, treasurer and secretary - are to be chosen from 4 people, Ann, Bob, Cyd and Dan.

Ann cannot repeat as president.

The secretary must be either Cyd or Dan.

How many ways can the officers be chosen?

 

5.2 The Pigeonhole Principle

Introduction

Pigeonhole principle If there are more pigeons than pigeonholes, at least one pigeonhole has two or more pigeons.

 

  12 holes, 13 pigeons

 

Example

13 people are in a room, at least 2 were born the same month.

You catch 3 fish, at least 2 are the same gender.

The oldest American is Besse Cooper, currently 115 years old, born 26 August 1896. In a room with 116 Americans, at least 2 are the same age.

You have 3 shoes. At least 2 are for the same foot.

 

Question 5.21

1. Thirteen people show up for two teams to play basketball. How many are on the bench?
    
2. What is the minimum number of students in a class to ensure at least 2 were born the same month?
    
3. What is the minimum number of students in a class to ensure at least 3 were born the same month?
    
4. What is the minimum number of students in a class to ensure at least 4 were born the same month?

 

THEOREM 1

If k boxes contain k + 1 or more objects, then at least one box contains two or more objects.

p → q

Premise

k boxes

k+1 objects

Hypothesis

p is "k boxes contain k + 1 or more objects"

Consequence

q is "at least one box contains two or more objects"

Proof by Contradiction

Assume ¬q

"no box contains more than one object"

"no box contains more than one object"	¬q is assumed
(k+1) - k = 1	k+1 objects - k boxes = 1
	¬p because 1 object is not in a box ¬p is "k boxes do not contain k + 1 or more objects"
	Assuming ¬q leads to contradiction of hypothesis
∴p →q

 

COROLLARY 1

A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.

For sets A and B,

f: A → B is 1-to-1 if f never assigns more than one element of A to an element of B.

A one-to-one mapping.

Question 5.22            Draw an example of Corollary 1.

 

The Generalized Pigeonhole Principle

THEOREM 2

If N objects are placed into k boxes then there is at least one box containing at least ⌈N/k⌉ objects.

Example

Among 13 people, at least how many were born the same month?

 ⌈N/k⌉  = number (at least) objects

N = 13

k = 12

At least ⌈13/12⌉  = ⌈1 1/12⌉  = 2 born the same month.

Among 100 people, at least many were born the same month?

N = 100

k = 12

At least ⌈100/12⌉  = ⌈8 1/3⌉  = 9 born the same month.

Question 5.23.1     Among 49 people, at least how many were born the same month.

 

Example

What is the minimum number of people (N) to invite to a party to ensure 4 born the same month?

Solution:

 ⌈N/k⌉  = number (at least) objects

12 possible months (boxes).

4 at least in same box (month).

⌈N / 12⌉  = 4

By pigeonhole principle, need 3 people in each month, plus 1 in any month:

N = (4 - 1) * 12 + 1 = 37

⌈ 37 / 12⌉  = ⌈3 1/12⌉  = 4
 

Question 5.23.2      What is the minimum number of people (N) to invite to a party to ensure 4 have the same birthday?

 

Example

What is the minimum number of students (N) to ensure at least 10 receive the same of 5 grades (A, B, C, D or F)?

Solution:

5 possible grades (boxes).

10 in same box (grade).

⌈N / 5⌉  = 10

By pigeonhole principle, need 9 students in each of 5 grades, plus 1 student for 10 in any one grade:

N = (10-1) * 5 + 1 = 46

⌈46/5⌉  = ⌈9 1/5⌉  = 10
 

Question 5.23.3      What is the minimum number of students (N) to ensure at least 8 receive the same of 5 grades (A, B, C, D or F)?

 

Example

How many cards (N) must be dealt to guarantee at least 3 are the same suit?

Example:    2 clubs + 2 hearts + 2 diamonds + 3 spades = 9 cards

Solution:

 ⌈N/k⌉  = number (at least) objects

4 possible suits (boxes).

3 at least in same suit (box).

⌈N / 4⌉ ≥ 3

N = (3-1) * 4 + 1 = 9

⌈9/4⌉ = ⌈2 1/4⌉  ≥ 3

Question 5.24    How many cards (N) must be drawn to guarantee holding at least 3 of the same kind (13 kinds of Ace, King, etc.)?
 

Example

In US we will have 4*10⁹ citizens (N), how many area codes are needed for each to have a permanent phone number?

Solution:

10⁷ possible 7-digit numbers (boxes).

 ⌈4*10⁹/10⁷ ⌉ = 4*10² = 400 area codes

 

Example

Assuming we all have only one phone, at what US population (N) would we run out of 10-digit numbers?

Solution:

10¹⁰ possible 10-digit numbers (boxes).

At least 2 the same

⌈N/10¹⁰ ⌉  ≥ 2

N = (2-1)*10¹⁰ +1 = 10¹⁰ + 1

 

Example

How many cards must be dealt to guarantee at least 3 are hearts?

Solution:

Can't pigeonhole because only one box for hearts, no place for non-hearts.

Could deal all 39 (3*13) non-hearts first then 3 hearts, or 42 cards total.

5.3 Permutations and Combinations - Calculator

Introduction

You need to fly to 5 cities in any order, how many possible air tickets do you need to consider?

How many poker hands can be dealt from 52 cards?

 

Definition - Factorial

n! = n* (n-1)! when n > 0 0! = 1

Question 5.25      

0! = 1

1! = 0! * 1 = 1

2! = 1! * 2 = 2

3! = 2! * 3 = 1 * 2 * 3 = 6

4! = 3! * 4 = 1 * 2 * 3 * 4 = 24

5! / 3! = 1 * 2 * 3 * 4 * 5 / 1 * 2 * 3 = 20

What is:

5!

6! / 4!

 

Permutations

Example

You need to fly to 5 cities in any order, how many possible air tickets do you need to consider?

Solution

Pick 1 of 5 cities to visit first.	5
Pick 1 of 4 remaining to visit second.	* 4
Pick 1 of 3 remaining to visit third.	* 3
Pick 1 of 2 remaining to visit  fourth.	* 2
Pick 1 of 1 remaining to visit  last.	* 1
Total 5*4*3*2*1 = 5! =	120

Note that order: A, B, C, D, E is different than E, D, C, B, A. Not the same tickets.

 

Example

How many poker hands in a 52 card deck?

Solution

Deal 1 of 52 cards for first card.	52
Deal 1 of 51 remaining.	* 51
Deal 1 of 50 remaining.	* 50
Deal 1 of 49 remaining.	* 49
Deal 1 of 48 remaining.	* 48
Total 52*51*50*49*48=	311,875,200

Wrong! The order cards are dealt does not matter.

A, B, C, D, E is the same as E, D, C, B, A in poker!

We will see the solution later.

 

Example

Suppose a program has 10 procedures that could be executed in any order.

How many different execution orders are possible?   

10! = 3628800

Multithreading can execute procedures in an arbitrary order. Some errors only occur when a particular procedure order is executed.

What are the ramifications for testing?    

Here the order of execution does matter, 10! different program executions are possible.

 

Definition

r-permutation is an ordered arrangement of r elements of a set.

Example

S = {a, b, c}

(a, b)≠ (b,a), it is a different 2-permutation of S

 

How many different ways are there to order {a, b, c} as a 2-tuple?

Often stated as "What are all the possible ways to take 3 things, 2 at a time?"

Solution

2 picks	Ways to pick
Pick 1 of 3 from {a,b,c}.	3
Pick 1 from remaining 2.	* 2
P(3,2) = 3*2 =	6

{(a,b), (a,c), (b,a), (b,c), (c,a), (c,b)}

 

THEOREM 1

P(n, r) = n(n-1)(n-2)...(n-r+1) If n is positive integer and 1 ≤ r ≤n

Example

P(10,4) = 10(10-1)(10-2)(10-4+1) = 10*9*8*7

4 picks	Ways to Pick
Pick 1 of 10.	10
Pick 1 of 9.	* (10-1)
Pick 1 of 8.	* (10-2)
Pick 1 of 7.	* (10-4+1)
P(10,4) = 10*9*8*7 =	5040

Possible ways of taking 10 things, 4 at a time.

 

COROLLARY 1

P(n, r) = n! / (n-r)! If n and r are integers and 0 ≤ r ≤n

Example

P(10,4) = 10! / (10-4)! = 10! / 6! = 10*9*8*7*6*5*4*3*2*1 / 6*5*4*3*2*1 = 10*9*8*7

Pick 1 of 10.	10
Pick 1 of 9.	*9
Pick 1 of 8.	*8
Pick 1 of 7.	*7
10*9*8*7 =	5040

Question 5.26.1     

a.    P(6, 3) =

b.    P(10, 2) =

P(n, r) = n! / (n-r)!

 

Question 5.26.2     

a.    Suppose there are 6 skiers in a race.

Does order of finish matter for winning gold, silver and bronze?

How many possible ways can gold, silver and bronze be won?

b.    Suppose you have 8 basketball players and you want to find the best team of 5.

How many possible teams are there, where two different teams may have the same players but in different positions?

P(n, r) = n! / (n-r)!

c.    Your favorite restaurant has a menu where you chose 4 different of any 17 items.

Does the order you pick items matter?

Is this a permutation problem?

Drink	Appetizer	Entree	Dessert
Tea	Fried calamari	Hamburger	Ice cream
Coffee	Sushi	Steak	Apple pie
Wine	Buffalo wings	Chicken	Brownie
Beer	Cheeze Wiz	Fried Fish
	Samosa	Burrito

Example

How many permutations of the letters ABCDEFGH contain the string ABC?

Solution

ABC is a single element

DEFABCGH, DEFGHABC are valid permutations

Actually only have 6 elements {ABC, D, E, F, G, H}

P(6,6) = 6! / (6-6)! = 6! / 1 = 720

d.    How many permutations of the letters ABCDEFGH contain AB and GH?

 

Combinations

Definition

r-combination is an unordered arrangement of r elements of a set.

THEOREM 1

C(n, r) = n! / r! (n-r)! If n is positive integer and 0 ≤ r ≤ n

Example

S = {a, b, c}

(a, b)≠ (b,a), it is a different 2-permutation of S

Example

S = {a, b, c}

{a, b}= {b, a}, are the same 2-combinations of S

How many 2-combinations (subsets of 2 elements) of S?

Solution

n=3, r=2

C(n, r) = n! / r!(n-r)!

C(3,2) = 3! / 2!(3-2)! = 6 / 2 = 3

 

Permutations P(3,2) = 3!/(3-2)!	Combinations C(3,2) = 3!/2!(3-2)!
(a,b), (b,c), (a,c), (b,a), (c,b), (c,a)	(a,b), (b,c), (a,c)

 

P(n, r) = n! / (n-r)!

C(n, r) = n! / r! (n-r)!

Question 5.27

1. P(5, 3) =
    
2. C(5, 3) =

  c.  Your favorite restaurant has a menu where you chose 4 different of any 17 items.

Does the order you pick items matter?

Is this a combination problem?

Drink	Appetizer	Entree	Dessert
Tea	Fried calamari	Hamburger	Ice cream
Coffee	Sushi	Steak	Apple pie
Wine	Buffalo wings	Chicken	Brownie
Beer	Cheeze Wiz	Fried Fish
	Samosa	Burrito

Example

n = 10, r = 4

C(10,4)	= 10! / 4!(10-4)!
	= 10! / 4!6!
	= 10*9*8*7*6*5*4*3*2*1 / 4!(6*5*4*3*2*1)
	= 10*9*8*7/4*3*2*1
	= 5040/24
	= 210

Recall permutations order matters:

P(10, 4) = 10! / (10-4)! = 10! / 6! = 10*9*8*7*6*5*4*3*2*1 / 6*5*4*3*2*1 = 10*9*8*7

Pick 1 of 10.	10
Pick 1 of 9.	*9
Pick 1 of 8.	*8
Pick 1 of 7.	*7
10*9*8*7 =	5040

but combinations order does not matter, no picks repeat in a different order.

Combinations eliminate the r! different ordered picks from permutations:

C(n, r) = P(n, r)/r!

C(10, 4) = P(10, 4)/4! = (10*9*8*7*6*5*4*3*2*1 /(6*5*4*3*2*1)) / 4! = 5040/24 = 210

4 things have 4! = 24 different permutations.

Example

S = {Bob, Alice, Cyd}

They have a 2-person motorcycle. 

How many different combinations can ride?

2-combinations (subsets of 2 elements) of S?

Solution

{Bob, Alice}   no Cyd
{Bob, Cyd }   no Alice
{Alice, Cyd}   no Bob

n=3, r=2

C(n, r) = n! / r!(n-r)!

C(3,2) = 3! / 2!(3-2)! = 3 *2*1 / 2*1 = 3

 

How many different permutations can ride, sitting in different positions?

Solution

{Bob, Alice}   no Cyd
{Alice, Bob}   no Cyd
{Bob, Cyd }   no Alice
{Cyd, Bob }   no Alice
{Alice, Cyd}   no Bob
{Cyd, Alice}   no Bob

2-permutations (subsets of 2 elements) of S?

P(n,r) = n!/(n-r)!

P(3,2) = 3!/(3-2)! = 3!/1 = 6

 

Example

S = {Bob, Alice, Cyd, Dan}

They have a motorcycle-sidecar with 3 seats. 

How many different combinations can ride?

3-combinations (subsets of 3 elements) of S?

Solution

{Bob, Alice, Cyd}    no Dan
{Bob, Alice, Dan}    no Cyd
{Bob, Cyd, Dan}     no Alice
{Alice, Cyd, Dan}    no Bob

n=4, r=3

C(n, r) = n! / r!(n-r)!

C(4,3) = 4! / 3!(4-3)! = 4 *3*2*1 / 3*2*1 = 4

Solution

How many different permutations can ride?

3-permutations (subsets of 3 elements) of S?

P(n,r) = n!/(n-r)!

P(4,3) = 4!/(4-3)! = 4!/1 = 24

Example

How many different poker hands of 5 cards can be dealt from a standard 52 card deck?

Note that the order the cards are dealt does not matter.

Solution

n = 52, r = 5

C(52, 5)	= 52! / 5!(52-5)!
	= 52! / 5!47!
	= (52*51*50*49*48) / 5!
	= 2,598,960

Question 5.28

a.    How many hands of five cards can be dealt from a Euchre deck of 24 cards?

Does order dealt matter?

b.    With 12 people, how many different basketball teams can be formed?

Note that the position played does not matter.

c.    With 12 people, how many different basketball teams can be formed?

Note that the position played does matter.

 

Example - Teams that contain both or neither

With 12 people, Alice and Ed insist on playing on the same team.

How many 5 person teams can be formed?

Teams with Alice and Ed

10 people to pick 3:    10! / 3!(10-3)! = 120

Teams without Alice and Ed

10 people to pick 5:    10! / 5!(10-5)! = 252

Teams are disjoint, Sum Rule:

Teams with Alice and Ed + Teams without Alice and Ed = 120 + 252 = 372

 

Example - Teams that do not contain both

With 12 people, Alice and Ed refuse to play on the same team.

How many 5 person teams can be formed?

Teams with Alice but not Ed

10 people to pick 4:    10! / 4!(10-4)! = 210

Teams with Ed but not Alice

10 people to pick 4:    10! / 4!(10-4)! = 210

Teams without Alice or Ed

10 people to pick 5:    10! / 5!(10-5)! = 252

Teams are disjoint, Sum Rule:

Teams with Alice but not Ed + with Ed but not Alice + without Alice or Ed =

210 + 210 + 252 = 672

 

Example - Teams with members of two types

With 12 people, 5 men and 7 women:

How many teams consist of 3 men and 2 women?

C(5, 3) ways to choose 3 out 5 men.            5! / 3!(5-3)! = 10

C(7, 2) ways to choose 2 out of 7 women.    7! / 2!(7-2)! = 21

Independent steps, picking men and women, Product rule.

C(5, 3) * C(7, 2) = 10 * 21 = 210
 

Question 5.29

With 12 people, 5 men and 7 women:

a.    How many 2 men and 3 women teams?

b.    How many 2 men and 3 women OR 3 men and 2 women teams?

 

Example

How many ways to get 5 of the same suit from a deck of 52 cards?

C(4, 1)        pick 1 of the 4 suits.                                Diamonds

C(13, 5)      pick 5 cards from 13 of same suit.            2, 3, 4, 5, Jack

C(4, 1) * C(13, 5) = 5148

 

Example

How many ways to get a full-house, 2 of the kind (e.g. 2 Kings) and 3 of a kind (e.g. 3 Aces) from a deck of 52 cards?

C(13, 1)      pick 1 of 13 kinds.                                Ace

C(4, 3)        pick 3 cards from the 4 suits.                Ace diamonds, hearts, spades

C(12, 1)      pick 1 of remaining 12 kinds.                King

C(4, 2)        pick 2 cards from the 4 suits.                King diamonds, hearts

C(13,1) * C(4,3) * C(12,1) * C(4,2) = 3744

Example

How many ways to get a 4 of the kind (e.g. 4 Kings) from a deck of 52 cards?

C(13, 1)      pick 1 of 13 kinds.                                King

C(4, 4)        pick 4 cards from the 4 suits.                King diamonds, clubs, hearts, spades

C(12, 1)      pick 1 of remaining 12 kinds.                 Ace or other non-King

C(4, 1)        pick 1 card from the 4 suits.                  Ace diamonds

C(13,1) * C(4,4) * C(12,1) * C(4,1) = C(13,1) * C(4,4) * 12 * 4 =624

Example

How many ways to get 2 of the kind (e.g. 2 Kings) from a deck of 52 cards?

C(13, 1)      pick 1 of 13 kinds.                                King

C(4, 2)        pick 2 cards from the 4 suits.                King clubs and hearts

C(12, 3)      pick 3 from remaining 12 kinds.            2, 3, Jack

C(4, 1)        pick 1 card from the four suits.              2 clubs

C(4, 1)        pick 1 card from the four suits.              3 hearts

C(4, 1)        pick 1 card from the four suits.              Jack clubs

C(13,1) * C(4,2) * C(12,3) * C(4, 1) * C(4, 1) * C(4, 1) = 1098240

 

Question 5.30

How many ways to get 3 of the kind (e.g. 3 Kings) from a deck of 52 cards?

 

Example

A coin is flipped 3 times.

1. How many different outcomes total?    2³ = 8               
                                                                  HHH, HHT, HTH, THH, HTT, THT, TTH, TTT
    
2. Have exactly one head?                       C(3,1) = 3         
                                                                   HTT, THT, TTH
    
3. Have exactly two heads?                     C(3,2) = 3
                                                                   HHT, HTH, THH
    
4. Have at most 2 heads?                        C(3,0)+C(3,1)+C(3,2) = 7     
                                                                   HHT, HTH, THH, HTT, THT, TTH, TTT
    
5. Have 2 or more heads?                       C(3,2)+C(3,3) = 4
                                                                   HHH, HHT, HTH, THH
    

Example

Differences between combinations and permutations.

Order matters Permutations of ABC	Order does not matter Combinations of ABC
P(3,3)       3! / (3-3)! = 6 ABC ACB BAC BCA CAB CBA	C(3,3)       3! / 3!(3-3)! = 1 ABC
P(3,2)       3! / (3-2)! = 6 AB AC BA BC CA CB	C(3,2)       3! / 2!(3-2)! = 3 AB AC BC

 

Example

How many 3 digit numbers are there?

10³

How many 3 digit numbers contain a digit twice or more?

3 arrangements, each with 90 values having exactly 2 digits the same, total 270

9xx    x9x    xx9

1 arrangement, with 10 values having 3 digits the same, total 10

xxx

280 total

Another way counts the number having 2 or more digits, then subtract all with 3 matches.

3 arrangements, each with 100 values having exactly 2 or 3 digits the same, total 300

Each of the 3 arrangements included 10 values having 3 digits the same, total 30

300 - 30 = 270 having exactly 2 digits the same

300 - 20 = 280 having 2 or 3 digits the same.

How many do not have duplicates?

 

Example

How many license plates of 3 letters followed by 3 digits?

26³*10³

How many license plates of 3 letters followed by 3 digits contain exactly two matching digits?

Number where digits occur only once: 10 ways to pick first digit, 9 ways to pick second, 8 ways to pick third

10*9*8 = 720

Number where all digits the same: 10 digits so 10 ways, 000, 111, etc.

Total without two matching digits: 270 = 1000 - 720 - 10

26³*270

 

5.4 Binomial Coefficients

The Binomial Theorem

Example 1 - Find the expansion of (x+y)³ using combinatorics, x and y could be any term.

(x+y)³ = (x+y)(x+y)(x+y) = xxx + xxy + xyx + yxx + xyy + yxy + yyx + yyy

xxx	1 way for 0 y's
xxy, xyx, yxx	3 ways for 1 y's
xyy, yxy, yyx	3 ways for 2 y
yyy	1 way for 3 y

x³ + 3x²y + 3xy² + y³ = xxx + xxy + xyx + yxx + xyy + yxy + yyx + yyy

 

THEOREM 1

Binomial Theorem

Example - Find the expansion of (x+y)³ using Binomial Theorem

= x³ + 3x²y + 3xy² + y³

 

Example - Find the coefficient of xy² in (x+y)³ using Binomial Theorem

 

Example - Find the expansion of (4x+2y)³ using Binomial Theorem

Example - Find the coefficient of xy² in (4x+2y)³ using Binomial Theorem

Since

Can find individual term coefficients, as for xy², by setting j=2: