Section 5 Definitions

The Rule of Produce

If a procedure can be broken down into first and second stages, and if there are m possible outcomes for the first stage and if, for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in the designated order in m*n ways.

The Rule of Sum

If a first task can be performed in m ways, while a second task can be performed in n ways, and the two tasks cannot be performed simultaneously, then performing either task can be accomplished in m+n ways.

Permutation of a Finite Set X

Is a linear arrangement of the elements of X and represented either as ordered lists or tuples/sequences.

Theorem: There are ___ permutations of the set {1, 2, …, n}.

n!

Permutation of Size r

Given a collection of n distinct objects, a permutation of size r is a linear arrangement of r of the n objects, denoted as P(n,r).

Number of Permutations

Let n and r be integers with 0 <= r <= n. If there are n distinct objects, then the number of permutations of size r from these n objects is n! / (n-r)!

Linear Arrangements With Repetitions

Let n, r be integers with 1 <= r <= n and there are n1 indistinguishable objects of the first type, n2 of the second type, …, nr indistinguishable objects of type r, and n = sum of all ns. Then there are n! / (n1!*n2!*…*nr!) ways to linearly arrange these n objects.

Combination

Given n distinct objects, a combination is any set of r objects from the n objects (where the order is not significant).

Binomial Coefficient

For any non-negative integers n and r, the binomial coefficient (n r), is the number of different combinations of size r from a set of size n.

Theorem: For any integers n and r with 0 <= r <= n, (n r) = ____.

n! / [r! * (n-r)!]

If n and r are non-negative integers with 0 <= r <= n, then (n r) = ___

(n n-r)

Combinatorial Proof

Use the two methods to count the same collection of sets in two different ways — often this means thinking about two different ways to “generate” the sets.

Pascal’s Identity

For integers n, r with n >= r >= 1:

(n+1 r) = (n r) + (n r-1)

Binomial Theorem

If x and y are variables, then for any non-negative integer n:

(x+y)ⁿ = sum from k=0 to k=n of (n k) x^k * y^n-k

Multinomial Coefficient

If n >= 0 and n1, n2, …, nk are all non-negative integers with n1 + n2 + … + nk = n, the multinomial coefficient is:

(n n1,n2,…,nk) = n! / (n1!n2!…nk!)

This counts the number of ways to choose from n objects with each n1, n2, …, nk representing a class.

Multinomial Theorem

Suppose that x1, x2, …, xk are variables, n and k are positive integers and 0 <= n1, n2, …, nk <= n with n1 + n2 + … + nk = n. The coefficient of x1ⁿ¹x2ⁿ²…xk^nk in the expansion of (x1 + x2 + … + xk)ⁿ is n! / (n1!n2!…nk!).

Theorem: If A, B are subsets of U, then ____.

A = (A\B) ∪ (A ∩ B)

A\B and A ∩ B are disjoint

If A is finite, then |A| = |A\B| + |A ∩ B|

Theorem: If A and B are finite sets then ____.

|A ∪ B| = |A| + |B| - |A ∩ B|

Theorem: If A, B, and C are finite sets, then ____.

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|