Counting Flashcards
AND
multiply
OR
add
FCP
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.
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?
F = 25 UR = 24 S = 23 N = 25 * 24 * 23 = 600*23 = 13,800
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?
D = 1 G = 2 A = 5 B = 4 C = 3 E = 2 F = 1
N = 1254321 = 2206 = 240
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?
S = 4 SL = 1 E = 3 M = 2 H = 1
N = 41321 = 24
n!
“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
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?
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
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?
n! = 6! = 720
6 elements: symmetry
nb of orders obeying the restriction and not are equal
720/2 = 360
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?
7! = 5040 total arrangements 3! = 6 re-arrangements of the three identical dictionaries
N = 7! / 3! = 7654 = 4220 = 840
total nb of arrangements for a set of n items with b identical items
N = n! / b!
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
N = n! / b!c!d!
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?
8! / 5!*2! = 168
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?
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
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?
12 starting vertices
9 non-adjacent vertices for each one of them
129 / 2 = 96 = 54
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?
1098 / 32 = 103*4 = 120
combination
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
10C4
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
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?
12C3 = 121110 / 3! = 21110 = 220
abstract combinations formula
nCr = n! / (r!)((n - r)!)
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?
overtures possibilities = 10C2 = 109 / 2 = 59 = 45
symphonies possibilities = 6
N = 6*45 = 270
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!
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
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?
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
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
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)
