Unit 4 Flashcards
The two most basic rules of counting are the blank and the blank.
sum rule
product rule
The blank provides a way to count sequences
product rule
If Σ is a set of characters (called an blank) then Σn is the set of all strings of length n whose characters come from the set Σ.
alphabet
For example, if Σ = {0, 1}, then Σ6 is the set of all binary strings with blank. The string 011101 is an example of an element in Σ6.
6 bits
The blank can be applied directly to determine the number of strings of a given length over a finite alphabet:
product rule
the blank is applied when there are multiple choices but only one selection is made
sum rule
The blank states that the cardinality of individual sequences (number of elements) can be multiplied to determine the total number of possible sequences that could be created from the individual sequences.
product rule
The blank requires a bit more thought than the product rule. When there is an either/or choice to be made, the number of possibilities are calculated by adding the cardinalities. However, if there is any overlap in choices, the number of common choices must be subtracted.
sum rule
The product rule and sum rule are needed to determine the blank of possibilities.
final number
The blank says that if there is a bijection from one set to another then the two sets have the same cardinality.
bijection rule
A function f from a set S to a set T is called a blank if and only if f has a well defined inverse.
bijection
The blank of a function f that maps set S to set T is a function g that maps T to S such that for every s ∈ S and every t ∈ T, f(s) = t, if and only if g(t) = s. If a function f has an inverse, it is denoted by f-1.
inverse
The bijection rule
Let S and T be two finite sets. If there is a bijection from S to T, then blank.
|S| = |T|
k-to-1 correspondence
Let X and Y be finite sets. The function f:X→Y is a k-to-1 correspondence if for every y ∈ Y, there are exactly k different x ∈ X such that blank.
f(x) = y
A 1-to-1 correspondence is another term for a bijection, so a bijection is a k-to-1 correspondence with k = 1. The blank uses a k-to-1 correspondence to count the number of elements in the range by counting the number of elements in the domain and dividing by k.
k-to-1 rule
k-to-1 rule
Suppose there is a k-to-1 correspondence from a finite set A to a finite set B. Then |B| = blankl
|A|/k.
Blank of sets can be used to count sets. For example, creating a one-to-one correspondence between a power set, P(x), and binary strings of length n, the cardinality of the binary strings equals the cardinality of P(x).
Bijection
According to the bijection rule, bijective sets have the same blank.
cardinality
The bijection rule is used to count sets when there is a 1-to-1 correspondence. If there is more than a 1-to-1 correspondence (k-to-1) use the blank. To count the number of elements in a k-to-1 correspondence in the range, count the number of elements in the domain and divide by k.
“k-to-1 rule.”
The blank says that in selecting an item from a set, if the number of choices at each step does not depend on previous choices made, then the number of items in the set is the product of the number of choices in each step.
generalized product rule
The blank rule keeps you from having to exhaustively make lists of all possibilities when several items are being considered in several sets.
generalized product
In the generalized product rule each successive choice blanks the number of possibilities for the next choice.
lowers
To calculate the number of possibilities using the generalized product rule, blank the number of items for each set or step by the number in the next step, etc. In the lesson introduction there was an example with horses in a race. The number of possible outcomes is 10 x 9 x 8 = 720
multiply
One of the most common applications of the generalized product rule is in counting permutations. An blank is a sequence of r items with no repetitions, all taken from the same set. Consider the set X = {John, Paul, George, Ringo}. The sequences (Paul, Ringo, John) and (John, George, Paul) are both examples of 3-permutations over X. In a sequence, order matters, so the sequence (Paul, Ringo, John) is different from the sequence (Ringo, Paul, John).
r-permutation
A blank (without the parameter r) is a sequence that contains each element of a finite set exactly once. For example, the set {a, b, c} has six permutations:
permutation
Blank: A sequence of r items chosen from n total items in which the order of the items matters
r-Permutation
Blank: A sequence of n items in which the order of the items matters and every item in a set is included exactly once.
Permutation
Blank (or r-combination): A sequence of r items chosen from n total items in which the order of the items does not matter.
r-Subset
An blank is a sequence of r items with no repetitions, all taken from the same set. For example, if there are 5 permutations (r items) from a set of 8 items, the formula is P(8,5) = 8 × 7 × 6 × 5 × 4 = 6720
r-permutation
The number of blank(arrangements) of a finite set of items n, grouped r at a time can be calculated using factorials and, at its core, is just the generalized product rule.
permutations
When counting the number of arrangements of a finite set, then the formula is very simply blank. If there is a specified order within elements of the set, combine the elements and think of it as one element. For example, if there are 6 elements in the set, and two elements must be next to each other in the sequence, then the formula is blank
n
n – 1.
Being able to count the number of blank of a finite set gives a programmer the ability to determine the number of ways a set of bits, a set of ID characters, or password characters can be arranged.
arrangements
A subset of size r is called an blank.
r-subset
An r-subset is sometimes referred to as an blank. The counting rules for sequences and subsets are commonly referred to as “permutations and combinations”. The term “combination” in the context of counting is another word for “subset”.
r-combination
An equation is called an blank if the equation holds for all values for which the expressions in the equation are well defined.
identity
Counting subsets has its own notation and terminology. The use of { } denotes blank or blank where order does not matter and ( ) denotes blank, blank, or blank where order does matter.
subsets or combinations
permutations, sequences, or arrangements
A subset of size blank is called an r-subset or r-combination.
r
The k-to-1 rule and permutations rule are used to count subsets without order. To count subsets:
Use the permutation formula to find the number of arrangements in a set
Divide by k!
Use the k-to-1 rule to find the total number of combinations
The mathematical formula for combinations looks similar to permutations; however, in the denominator, the division is not just by “r!”, but by blank.
r!(n-r)!
The notation specifically for combinations, used in the branch of mathematics called blank,
is read “n choose r”.
combinatorics
An identity is an equation in mathematics where both sides of the equation are always true for all values of the variables:
. This means that combinations of a set could be counted using the number r or by the blank n - r.
“complement”
Use the blank if the order in which the elements of the subset are selected is important. For example, select the top four students out of ten to earn the first place, second place, third place, and fourth place prizes.
permutation calculation
Use the blank if the order in which the elements of the subset are selected is not important. For example, select four students out of ten to earn a prize.
combination calculation
A blank is an ordering of a set of items in which some of the items may be identical to each other.
permutation with repetition
If a string has any duplicates, simply divide by the factorial of number of times the duplicate blank.
repeats
Counting by blank is a technique for counting the number of elements in a set S that have a property by counting the total number of elements in S and subtracting the number of elements in S that do not have the property.
complement
Counting using complements can save you a lot of time. For the purposes of this lesson, a complement set has the number of elements blank in the set you are looking for.
not
To count by complement:
Determine the number of items in your universal set
Subtract the cardinality of the complement from the cardinality of the universal set.
The result is the number of elements (cardinality) of the set you were trying to count.
A blank is a collection that can have multiple instances of the same kind of item
multiset
A set of identical items are called blank because it is impossible to distinguish one of the items from another
indistinguishable
A set of different or distinct items are called blank because it is possible to distinguish one of the items from the others.
distinguishable
A blank can have duplicate elements, as opposed to a regular set that has distinct elements. Multisets are very useful in applications where there are several varieties of items and at least one of those items can have multiple duplicates.
multiset
Blank means each item/element/bit/character can be distinguished from another; each one is unique.
Distinguishable
Blank means an item/element/bit/character in a set or string could repeat and you wouldn’t be able to tell them apart; they are identical duplicates.
Indistinguishable
blank is an ordered set of n items.
n-tuple
blank are sets, sequences, or series where order matters. Use ( ) to denote permutations.
Permutations
blank are subsets where order does not matter. Use { } to denote combinations.
Combinations
Blank is a way of ordering n-tuples in which two n-tuples are compared according to the first entry where they differ. Alphabetical order and alphanumeric order are familiar examples of lexicographic order. Words in a dictionary are ordered in lexicographic order.
Lexicographic order
A blank of the set {1, 2, …, n} is an ordered n-tuple in which each number in {1, 2, …, n} appears exactly once. For example (2, 5, 1, 4, 3) is a permutation of the set {1, 2, 3, 4, 5}.
permutation
An ordered set of n items can be referred to as an blank. For example, the set of (a, b ,c, d, e) is a 5-tuple.
“n-tuple.”
Formally, blank is a way of ordering n-tuples in which two n-tuples are compared according to the first entry where they differ. Informally, lexicographical order is just sets in alphabetical order or numerical order. For example, if you were asked to put a list of books in order by the author’s last name, you would need to have an agreement on how to handle “McAllister” vs “MacAllister” or “St. John” vs “Saint Johns.” Once everyone is in agreement then you have lexicographic order.
lexicographical order
blank generates all the permutations of a set size n and starts with the first permutation in lexicographic order and keeps generating the next permutation until the last permutation is reached.
GenLexPermutations(n)
Blank takes as input a permutation P and returns the smallest permutation that is larger than P—in other words, the “next” permutation in the lexicographic order.
NextPerm(P)
The principle of blank is a technique for determining the cardinality of the union of sets that uses the cardinality of each individual set as well as the cardinality of their intersections.
inclusion-exclusion
Let A and B be two finite sets, then |A ∪ B| = |A| + |B| - |A ∩ B|
The inclusion-exclusion principle with two sets
Let A, B and C be three finite sets, then
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|
Inclusion-exclusion with three sets
A collection of sets is blank if the intersection of any pair of sets in the collection is empty. If we apply the principle of inclusion-exclusion to determine the union of a collection of mutually disjoint sets, then all the terms with the intersections are zero.
mutually disjoint
When a collection of sets are disjoint—that is, mutually disjoint—counting the total number of elements is simple; just blank.
add the cardinalities
The inclusion-exclusion principle is applied when two or more sets blank (are not disjoint).
intersect
To count the total number of elements in two sets that intersect:
Sum the cardinalities of each set
Subtract the cardinality of the intersection
To count the total number of elements in three sets, of which two intersect:
Sum the cardinalities of all three sets
Calculate the cardinality of the intersection of all three sets
Calculate the cardinality of the three intersections of two sets at a time
Subtract the cardinality of all the intersection sets
To find the cardinality of an intersection (union) use the blank of a set.
complement
An blank is a theorem stating that two mathematical expressions are equal
identity
An identity that involves expressions related to counting is called a blank.
combinatorial identity
The coefficients in the expansion of (a + b)n for positive integer n are called blank.
binomial coefficients
The blank says that the coefficient of akbn-k in (a + b)n is (n/k)
binomial theorem
Blank says that the number of ways to select a set of k items from a set of n items is equal to the number of ways to select k - 1 from n - 1 plus the number of ways to select k from n - 1.
Pascal’s identity
The binomial coefficients have blank. In this example, pay attention to how the exponents increase/decrease on each term. Note that the value of r in the binomial coefficient is the same as the exponent on b of the binomial. For example, in the third term r is 2 and the exponent of b is 2.
patterns
blank and blank both are created and proved based on coefficients of binomial expansions.
Pascal’s triangle and Pascal’s identity
You can visualize blank as a pyramid-shaped map. Each row can be generated by adding the two terms directly above (see diagram in Participation Activity 4.19.5). Each number in Pascal’s triangle is a coefficient of a binomial expansion.
Pascal’s triangle
The blank says that if n+1 pigeons are placed in n boxes, then there must be at least one box with more than one pigeon.
pigeonhole principle
If a function f has a domain of size at least n+1 and a target of size at most n, where n is a positive integer, then there are two elements in the domain that map to the same element in the target (i.e., the function is not one-to-one).
The Pigeonhole Principle
Suppose that a function maps a set of n elements to a target set with k elements, where n and k are positive integers. In order to guarantee that there is an element y in the target to which f maps at least b items, then n must be at least k(b - 1) + 1.
Contrapositive of the generalized pigeonhole principle
The blank is essentially stating that if a function has a domain with more values than the range (the target), then there is always guaranteed to be at least two values in the domain which map to the same value in the range. The function is not one-to-one.
For example, a group of 20 students is guaranteed to have several students with the same birth month. There is no way each student could have a different birth month because there are 20 students (domain) and 12 months (values in the range).
pigeonhole principle
The blank of the principal is nicely demonstrated in 4.20.5 and again in 4.20.6. The purpose of these examples is to show you an application of why it is important to know how many items are in the domain in order to guarantee a mapping to the target.
“contrapositive”
