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
