Page 8 - 4660

Combinatorial Analysis

Example 1.2. In how many ways six different textbooks can be planted on one book
shelf? ,

Solution. N = P 6 = 6 · 5 · 4 · 3 · 2 · 1 = 720.

So far we have assumed that all n objects are different (or distinguishable). Let us now consider
n objects of which n 1 are identical and of type 1, n 2 are identical and of type 2, . . . , n m are identical
and of type m (clearly n = n 1 + n 2 + · · · + n m ). From (1.1) the number of permutations of these n
objects is again n! However, the number of distinguishable permutations is only

n!
P n (n 1 , n 2 , . . . , n m ) = (1.3)
n 1 !n 2 ! · · · n m !

since the i-th group of identical objects can be rearranged in n i ! ways without changing the
distinguishable permutation.

Example 1.3. A set of snooker balls consists of a white, a yellow, a green, a
brown, a blue, a pink, a black and 15 reds. How many distinguishable permutations
of the balls are there? ,

Solution. In total there are 22 balls, the 15 reds being indistinguishable. Thus from (1.3) the
number of distinguishable permutations is

22! 22!
= = 859541760.
(1!)(1!)(1!)(1!)(1!)(1!)(15!) 15!

Example 1.4. M = {1, 2, 2}; n = 3, n 1 = 1, n 2 = 2, k = 2; P 3 (1, 2) = 3! . Indeed there
1!2!
are such possible permutations: (1, 2, 2), (2, 1, 2), (2, 2, 1). It is only three. ,

Arrangements

Generalizing (1.1) slightly, let us suppose we choose only k (k < n) objects from n. Suppose that
we are given n distinct objects and wish to arrange k of these objects in a line. Since there are n
ways of choosing the 1-st object, and after this is done n − 1 ways of choosing the 2-nd object, …,
and finally n − k + 1 ways of choosing the r-th object, it follows by the fundamental principle of
counting that the number of different arrange — possible permutations of these k objects selected
from n is given by
n!
k
n(n − 1)(n − 2) · · · (n − k + 1) = ≡ A . (1.4)
n
(n − k)!
| {z }
k factors
Definition 1.2. A set consisting of k elements chosen from n giving elements
and put in the definite order is called an arrangement of n elements taken k and
k
denoted by A .
n
Arrangements can differ one from another either by elements or by their order. Arrangements
are computed by the formula

n!
k
A = n(n − 1) . . . (n − k + 1) = (1.5)
n
(n − k)!
where n! = 1 · 2 · . . . · (n − 1) · n.

8