Combinations and Permutations

Question 1

combinations vs permutation?

Answer 1

combination is when the order doesn’t matter, permutation order matters

Question 2

Basic combination formula (method 1):

Answer 2

screen capture

Question 3

Box and fill method for combinations (method 2):

Answer 3

screen capture

Question 4

what is a handshake question and what is an example of one?

Answer 4

any counting question that asks us to determine the number of ways to connect any two members of a group while also meeting any restrictions that may exist
ex 1: in a room with 15 people, each person shakes hands with exactly four other people. how many handshakes occurred?

Question 5

handshake formula? (this works for all handshake problems)

Answer 5

for a handshake question involving n entities, where each entity is connected to k other entities, the total number of possible connections is (n* k)/2
ex: in a room with 20 people, each person shakes hands once with every other person - how many handshakes were there?
n=20 since there are 20 people, and k=19 since each single person will be connected (shake hands with) 19 OTHER people
(nk)/2 = (2019)/2 = 190

Question 6

more advanced handshake problem example

Answer 6

*screen capture

Question 7

property of equivalent combinations:

Answer 7

“n choose k” = “n choose (n-k)” —> use this when dealing with large combination numbers

Question 8

property of equivalent combinations algebraic problems..

Answer 8

screen capture

Question 9

another useful property of equivalent combinations

Answer 9

screen capture

Question 10

fundamental counting principle

Answer 10

if there are m ways to perform task 1 and n ways to perform task 2, and the tasks are independent, then there are m*n ways to perform both of the tasks together

Question 11

mutually exclusive and the use of the word “or”

Answer 11

events are mutually exclusive when they cannot occur together. if there x ways to accomplish event A and y ways to accomplish event B and if A and B are mutually exclusive, then there are x+y ways to accomplish A or B

Question 12

choosing “at least” some number of items..

Answer 12

typically involves adding options from scenarios

Question 13

combinations with restriction - some items MUST be chosen

Answer 13

look at screen capture example

Question 14

combinations with restriction - some items MUST NOT be chosen

Answer 14

look at screen capture example

Question 15

when some members of a set must be chosen and some others must not be chosen

Answer 15

look at screen capture example

Question 16

two events are collectively exhaustive if..?

Answer 16

together, the events represent all of the potential outcomes of a situation

Question 17

what is an example of things that are collectively exhaustive and mutually exclusive

Answer 17

a light switch being on and off - mutually exclusive since if the switch is on it cant be off, and collectively exhaustive since on and off represent all of the potential states of the lightbulb

Question 18

what are the mathematical implications of identifying a situation in which two outcomes are both collectively exhaustive and mutually exclusive

Answer 18

*look at screen capture for example
the total number of ways in which the two scenarios can occur = [the number of ways in which A can occur] + [the number of ways in which B can occur]

Question 19

additional example of collectively exhaustive and mutually exclusive problems:

Answer 19

screen capture

Question 20

how to use collectively exhaustive and mutually exclusive trick for problems where you have to choose “at least one”

Answer 20

*see screen capture
at least one means one or greater, with the alternative being none. this represent a set of outcomes that are mutually exclusive and collectively exhaustive.

Question 21

how to handle problems in which the outcomes are dependent on one another

Answer 21

each sequential choice will have lower numbers of n in “n choose k” because they will be removed from the pool - see the following screenshot

Question 22

how to find the number of people in a group when you are given the number of people to choose and the number of ways the group can be chosen

Answer 22

assigning a variable for the total number to choose from and using the box and fill method - see screen capture

Question 23

basic permutation formula:

Answer 23

“n P k” = n Permute k = n!/[(n-k)!]

Question 24

box and fill method for Permutations:

Answer 24

same as for combinations except you don’t divide by the factorial of the number you are choosing (k) it is instead the product of n(n-1)…*(n-k+1)

Question 25

Permutations when all items are identical:

Answer 25

only count number of distinguishable permutations
ex> how many ways are there to arrange the letters S, S, S, S, S?
1 way -> S, S, S, S, S

Question 26

how do you adjust the permutation formula for when there are identical items?

Answer 26

number of permutations = n!/[r1!….rj!]
where n = number of items to choose from
r1,..,rj= frequency of repeated items. so if there were two items that were repeated, the first repeated 3 times and second repeated 2 times r1=3, and r2=2

Question 27

Permutations for circular arrangements

Answer 27

K items can be arranged in a circle in (k-1)! ways

Question 28

permutation problems: arrangements with restrictions - the anchor method

Answer 28

first anchor restricted items into their place, since there are no permutations that can occur with those positions. then fill in the arrangements with permutation formulas after

Question 29

permutation problems: arrangements with restrictions - when some items MUST be together, link them together

Answer 29

• see screen capture example
  when x items MUST be together in an arrangement of y items, treat those x items as one unit. there are now y-x+1 items that can be arranged in (y-x+1)! ways. IN addition, the x items can be arranged in x! ways, generating a total of (x!)(y-x+1)! ways to arrange the y items

Question 30

what principle should be used to calculate the number of possible arrangements when some items CANNOT be next to each other?

Answer 30

the principle of collectively exhaustive and mutually exclusive: the total number of arrangements = the total number when A & B are next to each other + the total number when A & B are NOT next to each other – this method is easiest because it is very difficult to determine directly the arrangements when they cannot be next to each other, but easy to determine the total number of arrangements and the number of arrangements when they are next to each other

Question 31

creating codes

Answer 31

see screen capture

Question 32

the fundamental counting principle (independed events) for multi digit problems with restrictions

Answer 32

how many 3-digit integers have no digits in common? systematically analyze how many choices there are for each digit and multiply the results:
ex above: for the first digit, note that it can be anything from 1-9 (not zero) so there are 9 choices, the next digit can include 0 but must be reduced by one since we already chose a number and it cant be the same as the first digit, so it is also 9, the last digit is 8 since two numbers have already been chosen. so: 998

Question 33

multi digit problems with restrictions and choosing the digits in the order of which is the most restrictive:

Answer 33

• see screenshot
  sometimes choices in later digits will depend on choices made earlier, so it is important to fill in choices for digits according to their restrictiveness

Question 34

multi scenario digit questions:

Answer 34

*screen capture
these arise when you have multiple restrictions and begin handling each in order of restiveness but then get to a point where a choice depends on something that was chosen before. in this case we break out the difference scenarios and add the number of arrangements

Question 35

if three or more points can be connected by the same straight line, what does that imply about those three points?

Answer 35

they are collinear

Question 36

counting the number of triangles that can be made from a set of points when no three of the points are collinear (meaning no three points would be unable to comprise a triangle)

Answer 36

this is a combination problem, since if you forced it to be a permutation problem you would over count the number of triangles since you would say triangle (A, B, C) is distinct from triangle (A, C, B), when they are not distinct.
to figure out how many triangle can be made from a set of n points in a plane (in which no three of the points are collinear) you do “n Choose 3” since 3 points are required to construct a triangle. since there are no restrictions due to collinearity this is just the number of ways to choose 3 points from n points

Question 37

will connecting 3 collinear points with a line produce a triangle?

Answer 37

NO, its just a straight line

Question 38

how do you arrive at the number of ways to create triangles from n vertices when three or more of the points are collinear?

Answer 38

of possible triangles = (total number of ways to select three points from the full set of points) - ( # of ways to select 3 collinear points)

typically to find the # of ways to select 3 collinear points you simply count them.. see screenshot

Question 39

how to use combinations to come up with the # ways to select three collinear points when counting them is cumbersome

Answer 39

see screenshot

Question 40

2 dimensional pathway problem:

see screenshot for problem set up

Answer 40

a checkpoint is a point that a traveler MUST pass through to get from their starting point to their destination

*see screenshot for steps to calculate # of possible paths

Question 41

counting 2-dimensional paths when there are no checkpoints between start and end

*see screenshot to understand the form these problems take

Answer 41

see screenshot for explanation of how to solve

Question 42

counting 3-dimensional paths

*see screenshot for example