Unit 4

Question 1

The two most basic rules of counting are the blank and the blank.

Answer 1

sum rule
product rule

Question 2

The blank provides a way to count sequences

Answer 2

product rule

Question 3

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 Σ.

Answer 3

alphabet

Question 4

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.

Answer 4

6 bits

Question 5

The blank can be applied directly to determine the number of strings of a given length over a finite alphabet:

Answer 5

product rule

Question 6

the blank is applied when there are multiple choices but only one selection is made

Answer 6

sum rule

Question 7

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.

Answer 7

product rule

Question 8

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.

Answer 8

sum rule

Question 9

The product rule and sum rule are needed to determine the blank of possibilities.

Answer 9

final number

Question 10

The blank says that if there is a bijection from one set to another then the two sets have the same cardinality.

Answer 10

bijection rule

Question 11

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.

Answer 11

bijection

Question 12

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.

Answer 12

inverse

Question 13

The bijection rule
Let S and T be two finite sets. If there is a bijection from S to T, then blank.

Answer 13

|S| = |T|

Question 14

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.

Answer 14

f(x) = y

Question 15

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.

Answer 15

k-to-1 rule

Question 16

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

Answer 16

|A|/k.

Question 17

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).

Answer 17

Bijection

Question 18

According to the bijection rule, bijective sets have the same blank.

Answer 18

cardinality

Question 19

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.

Answer 19

“k-to-1 rule.”

Question 20

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.

Answer 20

generalized product rule

Question 21

The blank rule keeps you from having to exhaustively make lists of all possibilities when several items are being considered in several sets.

Answer 21

generalized product

Question 22

In the generalized product rule each successive choice blanks the number of possibilities for the next choice.

Answer 22

lowers

Question 23

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

Answer 23

multiply

Question 24

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).

Answer 24

r-permutation

Question 25

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:

Answer 25

permutation

Question 26

Blank: A sequence of r items chosen from n total items in which the order of the items matters

Answer 26

r-Permutation

Question 27

Blank: A sequence of n items in which the order of the items matters and every item in a set is included exactly once.

Answer 27

Permutation

Question 28

Blank (or r-combination): A sequence of r items chosen from n total items in which the order of the items does not matter.

Answer 28

r-Subset

Question 29

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

Answer 29

r-permutation

Question 30

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.

Answer 30

permutations

Question 31

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

Answer 31

n n – 1.

Question 32

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.

Answer 32

arrangements

Question 33

A subset of size r is called an blank.

Answer 33

r-subset

Question 34

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".

Answer 34

r-combination

Question 35

An equation is called an blank if the equation holds for all values for which the expressions in the equation are well defined.

Answer 35

identity

Question 36

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.

Answer 36

subsets or combinations permutations, sequences, or arrangements

Question 37

A subset of size blank is called an r-subset or r-combination.

Answer 37

r

Question 38

The k-to-1 rule and permutations rule are used to count subsets without order. To count subsets:

Answer 38

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

Question 39

The mathematical formula for combinations looks similar to permutations; however, in the denominator, the division is not just by "r!", but by blank.

Answer 39

r!(n-r)!

Question 40

The notation specifically for combinations, used in the branch of mathematics called blank, is read "n choose r".

Answer 40

combinatorics

Question 41

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.

Answer 41

"complement"

Question 42

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.

Answer 42

permutation calculation

Question 43

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.

Answer 43

combination calculation

Question 44

A blank is an ordering of a set of items in which some of the items may be identical to each other.

Answer 44

permutation with repetition

Question 45

If a string has any duplicates, simply divide by the factorial of number of times the duplicate blank.

Answer 45

repeats

Question 46

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.

Answer 46

complement

Question 47

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.

Answer 47

not

Question 48

To count by complement:

Answer 48

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.

Question 49

A blank is a collection that can have multiple instances of the same kind of item

Answer 49

multiset

Question 50

A set of identical items are called blank because it is impossible to distinguish one of the items from another

Answer 50

indistinguishable

Question 51

A set of different or distinct items are called blank because it is possible to distinguish one of the items from the others.

Answer 51

distinguishable

Question 52

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.

Answer 52

multiset

Question 53

Blank means each item/element/bit/character can be distinguished from another; each one is unique.

Answer 53

Distinguishable

Question 54

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.

Answer 54

Indistinguishable

Question 55

blank is an ordered set of n items.

Answer 55

n-tuple

Question 56

blank are sets, sequences, or series where order matters. Use ( ) to denote permutations.

Answer 56

Permutations

Question 57

blank are subsets where order does not matter. Use { } to denote combinations.

Answer 57

Combinations

Question 58

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.

Answer 58

Lexicographic order

Question 59

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}.

Answer 59

permutation

Question 60

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.

Answer 60

"n-tuple."

Question 61

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.

Answer 61

lexicographical order

Question 62

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.

Answer 62

GenLexPermutations(n)

Question 63

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.

Answer 63

NextPerm(P)

Question 64

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.

Answer 64

inclusion-exclusion

Question 65

Let A and B be two finite sets, then |A ∪ B| = |A| + |B| - |A ∩ B|

Answer 65

The inclusion-exclusion principle with two sets

Question 66

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|

Answer 66

Inclusion-exclusion with three sets

Question 67

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.

Answer 67

mutually disjoint

Question 68

When a collection of sets are disjoint—that is, mutually disjoint—counting the total number of elements is simple; just blank.

Answer 68

add the cardinalities

Question 69

The inclusion-exclusion principle is applied when two or more sets blank (are not disjoint).

Answer 69

intersect

Question 70

To count the total number of elements in two sets that intersect:

Answer 70

Sum the cardinalities of each set Subtract the cardinality of the intersection

Question 71

To count the total number of elements in three sets, of which two intersect:

Answer 71

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

Question 72

To find the cardinality of an intersection (union) use the blank of a set.

Answer 72

complement

Question 73

An blank is a theorem stating that two mathematical expressions are equal

Answer 73

identity

Question 74

An identity that involves expressions related to counting is called a blank.

Answer 74

combinatorial identity

Question 75

The coefficients in the expansion of (a + b)n for positive integer n are called blank.

Answer 75

binomial coefficients

Question 76

The blank says that the coefficient of akbn-k in (a + b)n is (n/k)

Answer 76

binomial theorem

Question 77

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.

Answer 77

Pascal's identity

Question 78

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.

Answer 78

patterns

Question 79

blank and blank both are created and proved based on coefficients of binomial expansions.

Answer 79

Pascal's triangle and Pascal's identity

Question 80

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.

Answer 80

Pascal's triangle

Question 81

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.

Answer 81

pigeonhole principle

Question 82

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).

Answer 82

The Pigeonhole Principle

Question 83

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.

Answer 83

Contrapositive of the generalized pigeonhole principle

Question 84

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).

Answer 84

pigeonhole principle

Question 85

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.

Answer 85

"contrapositive"