Page 9 - 4660

Combinations

Example 1.5. In how many ways it is possible to choose the trade-union group
organizer and his deputy from the group of seven students? ,

2
Solution. N = A = 7 · 6 = 42.
7
In calculating the number of arrangements of the various objects we have so far assumed that
the objects are sampled without replacement — i.e. once an object has been drawn from the set
it is put aside. As mentioned previously, however, we may instead replace each object before the
next is chosen. The number of arrangements of k objects from n with replacement may be
computed very easily since the first object can be chosen in n different ways, as can the second,
the third, etc. Therefore the number of arrangements is simply

k k
A = n . (1.6)
n
This may also be viewed as the number of arrangements of k objects from n where repetitions are
allowed, i.e. each object may be used as often as one likes.

3
¯ 3
Example 1.6. M = {1, 2}; n = 2, k = 3; A = 2 = 8. Indeed, there are such possible
2
arrangements: (2, 1, 1), (1; 2, 1), (1, 1, 2), (1, 2, 2), (2, 1, 2), (2; 2, 1), (1, 1, 1), (2, 2, 2). It is
only eight. ,

Combinations

Definition 1.3. An arrangement of objects in which the order of the selection
k
in not important is a combination and denoted by C .
n
It is read: combination of n digits taken k at a time. ✓

We now consider the number of combinations of various objects when their order is
immaterial. Assuming all the objects to be distinguishable, from (1.4) we see that the number of
arrangements of k objects chosen from n is A k = n!/(n − k)!. Now, since we are no longer
n
concerned with the order of the chosen objects, which can be internally arranged in k! different
ways, the number of combinations of k objects from n is

( )
n! k n
= C = for 0 ≤ k ≤ n, (1.7)
(n − k)!k! n k
k
where C is called the binomial coefficient since it also appears in the binomial expansion for
n
positive integer n, namely
n
∑
n
k k n−k
(a + b) = C a b . (1.8)
n
k=0
Thus, combinations are computed by the formula
A K n!
k
C = n = . (1.9)
n
P k k!(n − k)!
Remark 1.1. . In practice it is better to use the next formula:

n(n − 1) . . . (n − k + 1)
k
C = .
n
n!

9