ics 6d exam 3

cardinality

how many elements are in a set, |A|

how do you recognize that a problem is talking about cardinality

when the problem says “how many elements” or “how many ways”

product rule

when u make a series of choices independently(AND choices), and multiply the number of options at each step

AND choices

options that are multiplied when your tasks are consecutive/dependent on each other to complete a set

how do you recognize that the problem is related to product rule

when it has ‘AND’ between choices(like choose a bun AND a meat) or requires you to make a sequence of independent decisions

sum rule

when you pick from mutually exclusive groups (OR choices) and have to add the group sizes to find the total number of combinations

OR choices

adding the sizes of mutually exclusive groups (OR choices) to find the total number of combinations

how to recognize that a problem is related to sum rule

when the problem uses ‘OR’ to differentiate between choices, or options are distinct categories that can’t overlap

bijection

a one-to-one pairing between two sets, where every element in A pairs with exactly one element in B (and vice versa)

what is the function rule for bijection (in notation)

f: A→B is a bijection if it has a well-defined inverse

how do you recognize a problem is related to bijection

when you can solve a difficult counting problem indirectly when matching its possible outcomes to a simpler set; knowing the size of set B, if you prove that A→ B is a bijection by finding a function that maps every element of A to B, the size of A is the size of B.

k-to-1 correspondence

k elements in the domain map to each single element in the range (multiple domain inputs to a single range output); size of your domain is always a multiple of the range so |range| = |domain|/k

r-Permutation P(n,r)

ordered sequence of r items chosen from n items(so r is a subset) where there are no repeats and the order matters. you can find it using the formula P(n, r) = n!/(n-1)! which basically says that you stop counting down once you have filled r slots and ignore the leftover (n-r) unchosen items

how do you know when to use r-Permutation P(n,r)

when you have problems the reality is affected by the order. there’s 3 types of problems: 1) the roles differ, like choosing person a as viece president and person b as president is not the same as person a as president and person b as vice president. 2) problems with ordered rankings like finishing first-second-third in a hackathon, if 3 teams compete changing the order changes the award they get. 3) lineups where the position matters like scheduling 3 artists to play at mesa and melodies, changing the order changes when they will play

why doesn’t this problem use r-Permutation P(n,r)? choosing a 3-person committee from a pool of 10 employees

because all employees have the same title (employee), no one has rankings (no first, second, or third place), and there’s no position based line up because they’re not standing in a physical line. permutations care about ORDER, {person a, person b, person c} is the same set as {person c, person b, person a}

permutation (full)

taking every single item in a set and putting them in a line, you’re filling out slots for every item you have unlike the P(n,r) formula where you’re picking a subset of r elements; the number of permutations of n elements = n!

when do you have to find a full permutation?

when the problem has keywords like arrange all, put in order, or are working with anagrams.

r-Combination C(n,r)

number of ways to pick r items from a pool of n items, an unordered selection of r items from n items(r is a subset). order doesn’t matter, can be calculated as C(n,r)= n!/(r!(n-r)!)

are there more permutations or combinations

combinations

how do you recognize that a problem is asking you to use r-Combination C(n,r), aka n choose r

when the problem is working with sets of people/items with no roles or orders, like committees, calculating probabilities/odds in games, lotteries, statistical sampling etc.

lattice path

total number of the shortest unique routes to get from a starting point to an ending point on a grad, moving only right or up (R,U) that is counted using combinations. the formula is paths from (0,0) to (m,n) = (m+n)/(m! * n!)

how do you know a problem is asking you to find a lattice path

if the problem is asking how to get from one point to another, only being able to travel 2 directions, etc.

how do you factor in forbidden paths when solving lattice path word problems

find the total paths. then, find paths from the start to the forbidden point as defined in the problem. then find paths from the forbidden point to the end. then multiply the bad segments together, the 2 numbers you just previously found. subtract the total number of bad paths from the valid paths to find safe paths.

what is the shortcut for finding lattice path

the combination format is C(total steps, up moves)=C(n,r)=shortcut: writing denominator first as factorial(ie. 2! = 2 × 1), and for numerator, start at n (in this case, 22) and write out terms counting down until you have the same number of numbers in denominator and numerator (ie 22 × 21) and then evaluate.

stars and bars

a combinatorial trick to distribute identical items into a specific number of groups. the dividers used to separate groups are called bars(ie to make groups of 3 you need 2 bars). since you’ll have the same number of stars(items) and bars(dividers) no matter how they’re arranged, you need to find where to place the bars out of the total slots available, solved by the equation C(n+k-1, k-1) where n is the total number of items(stars, k is the total number of groups, and k-1 is the number of dividers(bars) needed to create k groups. you then get a combination C(m,n) that you can solve

how do you know a problem is asking you to solve using stars and bars

if the problem is says “distributing identical items” or “non-negative integer solutions to a sum equation” (are the items the same(yes) and is it ok if someone gets 0 (yes))

how do you perform the tax trick(ie when stars and bars problems implement the “at least one” constraint?

you take the total amount of stars and give one to each group or variable, and then do stars and bars with the leftover remaining amount of stars.

derangement

special type of permutation where nothing ends up in its original, “correct” spot and every item must be mixed up or misplaced (kinda like secret santa, no one can ever get their own gift). it looks at combination orders where no element ends up in its assigned spot, like if you have 3 letters and 3 envelopes, each labeled 1,2,3, there’s 6 ways to combine them. the derangement is the outcomes where letter 1 isn’t with envelope 1, letter 2 isn’t with envelope 2, and letter 3 isn’t with envelope 3. the formula is D(n)=(n-1)x[D(n-1)+D(n-2)] where D(1)=0 and D(2)=1, or derangements = total permutations/2.718

how do you know a problem is asking you to work with derangements

when the problem says “no element in its correct position”

inclusion-exclusion

method of finding the total when 2 groups overlap, subtracting the overlap to avoid double counting. |AUB|= |A| + |B| - |A and B| like students who like math or science = |math| + |science| - |both|

how do you know that a problem is asking you to work with inclusion-exclusion

when the problem has two conditions that can both be true, overlapping sets