Combinatorics

• Rules of sum and product

Rules of sum and product

We can sometimes express a set of items that we wish to count as a union of disjoint sets or as a Cartesian product of sets (which is the set of all ordered pairs such that the first element of the pair is an element of A and the second is an element of B).

Rule of sum

The rule of sum says that the number of ways to choose one element from one of two disjoint sets is the sum of the cardinalities of the sets. That is, if A and B are two finite sets with no members in common, then | A U B | = |A| + |B|.

For example, each position on a car's license plate is a letter or a digit. The number of possibilities for each position is therefore 26 + 10 = 36, since there are 26 choices if it is a letter and 10 choices if it is a digit.

Rule of product

The rule of product says that the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element. That is, if A and B are two finite sets, then | A x B | = |A| * |B|.

For example, if an ice cream parlor offers 28 flavors of ice cream and 4 toppings, the number of possible sundaes with one scoop of ice cream and one of topping is 28 * 4 = 112.

Strings

string and k-string

A string over a finite set S is a sequence of elements of S. For example, there are 8 binary strings of length 3: 000, 001, 010, ..., 111

A string of length k is called a k-string.

substring and k-substring

A substring s' of a string s is an ordered sequence of consecutive elements of s. A k-substring of a string is a substring of length k. We can view a k-string over a set S as an element of the Cartesian product $S^k$ of k-tuples; thus, there are $|S|^k$ strings of length k. For example the number of binary k-strings is $2^k$. Intuitively, to construct a k-string over an n-set, we have n ways to pick the first element; for each of these choices, we have n ways to pick the second element; and so forth k times. This construction leads to the k-fold product n * n * ... * n = $n^k$ as the number of k-strings.

Factorial Properties

• Factorials are multiplications of positive numbers.
• O! := 1
• Since n! = n * n - 1 * n - 2 * … * 1
• n! = (n-1)! * n
• (n+1)! = n! * (n+1)
• (n+k)! = n! * (n+1) * … * (n+k)
• (n-k)! = $\frac{n!}{(n-k+1)(n-k+2) \cdots (n-k+k)}$
• If n > k: => $\frac{n!}{k!}$ the only numbers remaining after the division are the ones between (k, n]

Permutations

A permutation of a finite set S is an ordered sequence of all elements of S, with each element appearing exactly once.

For example, if S = {a, b, c}, then S has 6 permutations: abc, acb, bac, bca, cab, cba.

There are n! permutations of a set of n elements, since we can choose the first element of the sequence in n ways, the second in n-1 ways, the third in n-2 ways, and so on:

• Pn = n * (n-1) * (n-2) * … * 1 = n!

A k-permutation of S is a n ordered sequence of k-elements of S, with no element appearing more than once in the sequence. The number of k-permutations (also called variations) of an n-set is:

• $V(n, k) = \frac{n!}{(n - k)!}$

since we have n ways to choose the first element, n-1 ways to choose the second element, and so on, until we have selected k elements, the last being a selection from the remaining n-k+1 elements.

Combinations

A k-combination of an n-set S is simply a k-subset of S. For example, the 4-set {a,b,c,d} has six 2-combinations: ab, ac, ad, bc, bd, cd.

We can construct a k-combination of an n-set by choosing k distinct elements from the n-set. The order in which we select the elements does not matter. We can express the number of k-combination of a n-set in terms of the number of k-permutations of an n-set. Every k-combination has exactly k! permutations of its elements, each of which is a distinct k-permutation of the n-set. Thus, the number of k-combinations of an n-set is the number of k-permutations divided by k!:

• Definition of Combinations: In combinatorics, a combination is defined as the selection of a subset of items from a larger set, where the order of selection doesn't matter.

$\binom{n}{k} = \frac{{n!}}{{k! \cdot (n - k)!}}$

Notes:

• From the formula, the number of ways to choose 0 elements from an n-set is 1 (0!=1)
• $\binom{n}{k}$ reads n chooses k denotes the nubmer of k-combinations of an-set.
• $\binom{n}{k}=\binom{n}{n-k}$
• Combinations are symmetrical, we can pick p many elements in as many ways as we can omit n-p many elements.
• The symmetry property arises because, for any valid combination, you can create a corresponding complementary combination. For example, if you have chosen a subset of “k” items, you can also consider the complement of that subset, which consists of the remaining “n - k” items that were not chosen. These two subsets, the chosen subset, and its complement, together form the entire set of “n” items.
• ⇒ If p > n/2 > n - p you can use symmetry to avoid calculating large factorials.

Binomial coefficients

$\binom{n}{k}$ are also known as binomial coefficients, due to their appearance in the binomial expansion:

$$(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$

A special case of the expansion occurs when a = b = 1: $$ \sum_{k=0}^{n} \binom{n}{k} = 2^n $$

This formula corresponds to counting the $2^n$ binary n-strings by the number of 1s they contain. $\binom{n}{k}$ binary n-strings contains exactly k 1s, since we have $\binom{n}{k}$ ways to choose k out of the n positions in which to place the 1s.

Binomial bound

For 1 <= k <= n we have the lower bound: $\binom{n}{k}$ >= $\binom{n}{k}^k$

Combinations With Separate Sample Spaces

• You multiply the result of each space.
• example 3 options for entry dish, 2 for the main course, and 5 for beverages, resulting in 3 * 2 * 5 possible meals.
• Note This is relevant since the likelihood of two independent events occurring simultaneously equals the product of their individual probabilities.
• example: lottery:
  • First you have to guess the power ball (1 number out of 26) ⇒ P(PB) 1/26
  • Then you have to get the correct 5 numbers ⇒ P(CC) = 1/comb where comb = 69!/(5!*(64!)) = 11M
  • P(win) > 1/26 * 1/ 11M
  • Buying more tickets has a very low return, with two tickets the prob of winning is < 2/(26*11M)

With repetitions

Permutations with repetitions

• $n^n$

Combinations with repetitions

Pick and choose when order doesn't matter.

• C = V/P = $\frac{(n+p-1)!}{p!(n-1)!}$
• Note: C_rep(n, p) = C(n+p-1,p)

Variations with repetitions

Pick and choose when order matters.

• $\bar{V}(p,n) = n^p$
• The variations are the number of ways we can pick and arrange some elements of a given set.
• In the formula, p is the positions we need to fill, and n is the total number of elements.

example: $\bar{V}(2,3) = 3^2$