Counting

Question 1

AND

Answer 1

multiply

Question 2

OR

Answer 2

add

Question 3

FCP

Answer 3

Fundamental Counting Principle

Suppose we can divide a given task into stages
Suppose the 1st stage can be done in n1 ways, the second in n2ways, and so on
The total nb of ways to do the task:
N = n1 * n2 * n3 * etc.

Question 4

A small division of a company, with 25 employees will choose a three-person steering committee consisting of a facilitator, a union rep, and a secretary. How many different possible steering committees could be chosen?

Answer 4

F = 25
UR = 24
S = 23
N = 25 * 24 * 23 = 600*23 = 13,800

Question 5

The children Al, Betty, Chuck, Dahlia, Ed, Fran, and George will sit in seven adjacent chairs. Dahlia must be in the middle chair, and George must be next to Dahlia. In how many orders can they be arranged?

Answer 5

D = 1
G = 2
A = 5
B = 4
C = 3
E = 2
F = 1

N = 1254321 = 2206 = 240

Question 6

In a certain summer school program, there are five periods in the day. Each student takes English, Maths, History, Science, and Science Lab. In how many orders can a student schedule be arranged, given that Science Lab must immediately follow the Science class?

Answer 6

S = 4
SL = 1
E = 3
M = 2
H = 1

N = 41321 = 24

Question 7

n!

Answer 7

“n factorial” is the product of n and all the positive integers less than n

5! = 54321 = 120

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
10! > 1million (10^6)
13! > 1billion (10^9)
15! > 1trillion (10^12)

20! = 2019! = 201918! = 20191817! = …
any factorial n! is divisible by all the integers less than n and all the factorials less than n!
n different items can be arranged in n! unique orders

Question 8

Six children will sit in a row of six chairs, but Jackie and Marilyn cannot be seated next to each other. How many arrangements are possible?

Answer 8

n! = 6! = 720

nb of arrangements that don’t obey the restriction Q
(make a list) with 10 arrangements, the four empty seats could be filled by an arrangement of the remaining four children: 4! = 24
Q = 24*10 = 240

nb of arrangements that obey the restriction R
R = n! - Q = 720 - 240 = 480

Question 9

Six children will give presentations, one after the other, in some order. Luke’s presentation makes a reference to sth mentioned in Ruth’s, so Ruth’s presentation must come before Luke’s (not necessarily immediately before). How many orders are possible?

Answer 9

n! = 6! = 720

6 elements: symmetry
nb of orders obeying the restriction and not are equal
720/2 = 360

Question 10

A librarian has seven books to arrange: four different novels, and three identical copies of the same dictionary. In how many different orders could these seven books be put on the shelf?

Answer 10

7! = 5040 total arrangements
3! = 6 re-arrangements of the three identical dictionaries

N = 7! / 3! = 7654 = 4220 = 840

Question 11

total nb of arrangements for a set of n items with b identical items

Answer 11

N = n! / b!

Question 12

total nb of arrangements for a set of n items containing one group of b identical items, one group of c identical items, one group of d identical items

Answer 12

N = n! / b!c!d!

Question 13

A librarian has 5 identical copies of book A, two identical copies of book B, and a single copy of book C. In how many distinct orders can he arrange these 8 books on a shelf?

Answer 13

8! / 5!*2! = 168

Question 14

In a bag are 6 identical green marbles, 4 identical blue marbles, and 2 identical red marbles. If 3 marbles are picked at random from the twelve in the bag, how many distinct sets of three can be selected?

Answer 14

no formula
simply count
three of a kind: 3G, 3B
2+1: 2G,B; 2G,R; 2B,G; 2B,R; 2R;G; 2R,B
3 different: G,B,R

total = 9

Question 15

In geometry, the diagonal of a polygon is the segment from any vertex to any other non-adjacent vertex. For example, a diagonal from K could go to any vertex from A to I, but nut not to J or L. How many diagonals does a regular 12-sided figure (a regular dodecagon) have?

Answer 15

12 starting vertices
9 non-adjacent vertices for each one of them
129 / 2 = 96 = 54

Question 16

From a set of ten different items, Lisa is going to select three as a gift for someone. How many different sets of three items can she pick?

Answer 16

1098 / 32 = 103*4 = 120

Question 17

combination

Answer 17

a small group drawn from a large group

if we have a group of n different individuals, and we randomly select r of these individuals, then the nb of combination is denoted as
nCr (read “n choose r”)

nC1 = n
nC2 = n(n-1) / 2

if we select a group of r from a pool of n, we create a group of (n - r) left behind
starting from a pool of n, there must be one group of (n - r) for each combination of r
nCr = nC(n - r)
10C4 = 10C6

Question 18

10C4

Answer 18

10 items, select a set of 4, how many different sets of four could we pick?

using the FCP: N = 1098*7, but the order doesn’t matter so we divide by 4!

10C4 = 10987 / 4! = 103*7 = 210

Question 19

An amusement park has 12 different major rides. A coupon gives its holder access to any 3 of these rides for free. How many sets of three rides are possible?

Answer 19

12C3 = 121110 / 3! = 21110 = 220

Question 20

abstract combinations formula

Answer 20

nCr = n! / (r!)((n - r)!)

Question 21

A classical concert will consist of two overtures in the first half and one symphony in the second half. A symphony and two overtures determine a program. The conductor can choose the program from 10 overtures and from 6 symphonies. How many programs are possible?

Answer 21

overtures possibilities = 10C2 = 109 / 2 = 59 = 45
symphonies possibilities = 6
N = 6*45 = 270

Question 22

A librarian has a set of ten books, including four different books about Abraham Lincoln. The librarian wants to put the ten books on a shelf with the four Lincoln books next to each other, somewhere on the shelf. How many different arrangements of the ten books are possible?
(A) 10! / 4!
(B) 4! * 6!
(C) 4! * 7!
(D) 4! * 10!

Answer 22

the four Lincoln books must be together, think of them as one big book + six other books
nb of arrangements = 7!
and 4! arrangements for the Lincoln books
total arrangements = N = 4! * 7!
C

Question 23

Pick with no repeats

• order matters
• order doesn’t matter

A/ In a pool of 20 committee members, we need to pick three officers (chairperson, treasurer, secretary) for the leadership team. How many teams can be formed?

B/ a chef is making a soup and has 20 vegetables from which to choose. He is instructed to choose any three vegetables, cut them into small pieces and stir them into the large pot of soup. How many different soups could he make?

Answer 23

Order matters, pick with no repeats :
Permutation
Count the possibilities in each stage + FCP
ex A:
If we swap around the chairperson, treasurer and secretary of a team, we get a different leadership team, order matters
use the FCP
N = 201918

Order doesn't matter, pick with no repeats :
Combinations (FCP / repetitions)
ex B: 
Order doesn't matter, combination
20C3 = 20*19*18 / 3! 
20C3 = 1140

Question 24

At Hecate Capital, the HR Director needed to select 3 certified Safety Monitors for a Safety Committee. The HR Director believed there were only 6 such certified Safety Monitors at Hecate and calculated N1, the nb possible committees. That week, though, 2 more Hecate employees completed the training and became certified Safety Monitors. If the new nb of possible committees, drawing from all 8 Safety Monitors, is N2, what is the ratio of N2 to N1? 
(A) 3/2
(B) 4/3
(C) 5/3
(D) 14/5
(E) 16/9

Answer 24

N1 = 6C3
N2 = 8C3

8C3/6C3 = ?

N1 = 6*5*4 / 3! = 20
N2 = 8*7*6 / 3! = 56

56/20 = 14/5
(or use pascal’s triangle)

(D)