Permutations, k-Permutations and Combinations

n

7

k

5

The number of permutations of n objects is

n! = 1 × 2 × 3 × ⋯ × (n-1) × n =

1 × 2 × 3 × 4 × 5 × 6 × 7 = 5040

The number of k-permutations of n objects is

P(n, k) =

n!

(n - k)!

= n × (n - 1) × (n - 2) × ⋯ × (n - k + 1) =

7 × 6 × 5 × 4 × 3 = 2520

The number of combinations of k objects chosen from n objects is

C(n, k) =

n!

k! (n - k)!

=

(7 × 6 × 5 × 4 × 3) /

(5 × 4 × 3 × 2 × 1) = 21

Number of Permutations

The number of ways to arrange

n

different objects in a row is

n!=1×2×3×⋯×

n

. The exclamation mark "!" is read as "factorial". Of course, the product is the same in reverse order:

n!=n×(n-1)×(n-2)×…3×2×1

. Each such arrangement is called a permutation. For consistency, it is assumed that

0!=1

.

Number of k-Permutations

If only

k

of the

n

objects are to be arranged in a row, the formula is

P(n,k)=

n!

(n-k)!

=n×(n-1)×…(n-k+1)

,

with

k

factors. If

k>n

,

P(n,k)=0

. Such an arrangement is called a partial permutation, or a

k

-permutation. Clearly

P(n,n)=n!

, because all

n

objects are being arranged; the formula reduces to

n!

because the denominator is

(n-n)!=0!=1

.

Number of Combinations

The number of ways to choose a subset of

k

objects from

n

objects is

C(n,k)=

n!

k!(n-k)!

.

Therefore,

C(n,k)=P(n,k)/k!

. Each choice of a subset is called a combination. Another notation for

C(n,k)

is



n

k



. Again, if

k>n

,

C(n,k)=0

. A special case is

C(n,n)=1

.