PERMUTATIONS AND COMBINATIONS

SAMPLING

Sampling without replacement
- Used to arrange distinct objects in some order.
- Permutations: each ordering of distinct objects is unique.
- Combinations: ordering of objects is irrelevant.
- Number of permutations is greater than number of combinations.
- Helps determine probability of "equally likely" outcomes .
- Appears in definition of discrete hypergeometric distribution.

Consider a population of three letters : {a, b, c} = 3 = n

Experiment: Draw two letters: (x, y) = 2 = r

Sampling without replacement: n · (n - 1) (n - 2) ... (n - (r - 1))

Can form six "sample sets": 6 = 3 · 2 = n (n - 1)

(a, b) (a, c) (b, c) (b, a) (c, a) (c, b)

2. Sampling with replacement

Can form nine "sample sets": 9 = 3 ² = n ^r

(a, a) (a, b) (a, c) (b, b) (b, c) (b, a) (c, c) (c, a) (c, b)

PERMUTATIONS

Each Ordering Is Unique

A permutation is a particular sequence of objects (or simple events) where the order of selection forms subsets or arrangements that are considered unique or distinctive .
For example, the three letters (abc) are considered unique and distinct from the other five possible arrangements of these letters:

(abc) ‰ (acb) ‰ (bac) ‰ (bca) ‰ (cab) ‰ (cba)
Therefore, given n distinct objects arrange r of them in a set.
Assume:
1. Each sample is "equally likely."
2. Each sample is taken "without replacement."
Permutation of n objects taken r at a time:
Remember that by definition 0! ‰ 1

Single toss of three coins

Eight distinct outcomes: n = 2 — 2 — 2 = 8

Permutation of n objects taken r at a time:

Also written as P(n, r), _n P _r , P _n,r , P _r ⁿ

Permutations of EIGHT objects taken ONE at a time:

Permutations Are Choosing "Without Replacement"
1. Permutations: P(r;n)
2. Permutations of eight objects taken two at a time:
3. Permutations of eight objects taken three at a time:
Permutations of Different Types of Objects

If n objects are comprised of k unique types such that:

n = n ₁ + n ₂ + ... + n _k

Then the number of different permutations of n objects taken n at a time is:

Example 1

Eight balls in an urn comprised of the following:

Example 2

Single toss of three coins

If we do not distinguish order of heads and tails in each of the eight total outcomes

COMBINATIONS ” ORDERING IS IRRELEVANT

A combination is a particular sequence of objects (or simple events) selected to form subsets or arrangements without regard to the order of objects in the arrangement. For example, the three letters (abc) are considered indistinguishable from these five other possible arrangements of these letters:

(abc) = (acb) = (bac) = (bca) = (cab) = (cba)

Therefore, given n distinct objects arrange r of them in a set.
Combination of n objects taken r at a time; (r ‰ n):
Assume:
- Each sample is "equally likely"
  1. Each sample taken "without replacement"

Note

The number of combinations is less than the number of permutations. The reader should also note that the combination formula may be written in two different ways as:

(1)

and

(2)

PERMUTATION OR COMBINATION?

Example 1

How many ways can a group of eight people be chosen to form a committee of five members ?

Assume a full five-member committee is formed . Each person is unique and selected "without replacement." Also, no distinction is made in terms of the order of selection of the "people." Hence, abcde = bcdea implies a combination.

Combination of 8 people (objects) taken 5 at a time:

Example 2

How many ways can a group of eight people be seated at a head table having only five chairs?

Assume all five chairs are filled. Each person is unique and selected "without replacement."

The order of seating is important and distinguishes the seating plan, e.g., the seating order abcde ‰ bcdea. This implies a permutation and not a combination.

So, permutation of 8 people (objects) taken 5 at a time:

P(5;8) = (8)(8 - 1) ... (8 -(5 - 1))

= 8 · 7 · 6 · 5 · 4 = 6720

Example 3

Q:

How many different ways can a group of five candidates be selected when (1) at least one award total will be presented, AND (2) each candidate can receive at most only one award?

Answers

A:

Assume at least one award is made.

Assume one person cannot receive two awards. (i.e., sampling "without replacement") All awards are equal; order of selection not important. Therefore, the problem is of combination not permutation in nature.

One out of 5 could be selected:

C(1;5) = 5

Two out of 5 could be selected:

C(2;5) = 10

Three out of 5 could be selected:

C(3;5) = 10

Four out of 5 could be selected:

C(4;5) = 5

Five out of 5 could be selected:

C(5;5) = 1

Total number of possible awards that could be presented:

C(1;5) + C(2;5) + C(3;5) + C(4;5) + C(5;5)

= 5 + 10 + 10 + 5 + 1 = 31

BINOMIAL EXPANSION

As we already have mentioned, permutations, combinations and factorials are used in the binomial distributions. Let us see how.

Combinations

Combinations are also called "binomial coefficients," which arise in the expression for a Binomial Expansion. To identify this expansion given n objects and arranging r of them in a set, we use the following notation:

Properties of Binomial Coefficients

Since: n - (n - r) = r then a symmetry exists:

that is, if r + k = n

then

can show:

Note	‰ 0 if b > a Since (-a)! Undefined

Binomial Expansion

Fundamentally, the binomial expansion is a power function and is based on the successive powers of the given function of the form

Examples of this expansion for n = 0 up to n = 5 are given below.

n = 0: (a + b) = 1
n = 1: (a + b) ¹ = a + b
n = 2: (a + b) ² = a ² + 2ab + b ²
n = 3: (a + b) ³ = a ³ + 3a ² b + 3ab ² + b ³
n = 4: (a + b) ⁴ = a ⁴ + 4a ³ b + 6a ² b ² + 4ab ³ + b ⁴
n = 5: (a + b) ⁵ = a ⁵ + 5a ⁴ b + 10a ³ b ² + 10a ² b ³ + 5ab ⁴ + b ⁵

We can also use the same rationale to use the expansion for other useful factors and expansions, such as in the following examples:

a ² - b ² = (a + b)(a - b)
a ² + b ² = (a + b)(a - b)
a ³ + b ³ = (a + b)(a ² - ab + b ² )
a ³ - b ³ = (a - b)(a ² + ab + b ² )

As a quick way to figure out the expansion, one may use the Pascal's Triangle for the (a + b) ⁿ array of coefficients of successive powers of (a + b) ⁿ .

The reader should try to fill the coefficients for n = 7 and 8. Some general guidelines to generate the coefficients are:

A power of n has (n + 1) terms.

If n is odd the number of terms is even.

If n is even the number of terms is odd.
The first and last numbers in each row are always 1.
The second number and the next -to-last number are equal to n.
The numerical values of the remaining inner terms can be determined by addition of the two numbers appearing directly above, e.g., for row n = 6, the third term is 15 which is the sum of the 10 and 5 appearing above its position in row n = 5. The fourth is 20 which is the sum of 10 and 10 appearing above its position in row n = 5. The fifth is 15 using the same rationale and so on.