Consider the following problem: You have the integers S_{n} =

{1,2,⋅⋅⋅,n }

and k is an integer
no larger than n. How many ways are there to fill k slots with these integers starting from left
to right if whenever an integer from S_{n} has been used, it cannot be re used in any succeeding
slot?

◜----k of the◞s◟e slots-◝
--,---,---,--,⋅⋅⋅,---

This number is known as permutations of n things taken k at a time and is denoted by
P

(n,k)

. It is easy to figure it out. There are n choices for the first slot. For each choice for the
fist slot, there remain n − 1 choices for the second slot. Thus there are n

(n − 1)

ways to fill
the first two slots. Now there remain n − 2 ways to fill the third. Thus there are
n

(n − 1)

(n − 2)

ways to fill the first three slots. Continuing this way, you see there
are

P (n,k) = n (n− 1)(n− 2)⋅⋅⋅(n− k+ 1)

ways to do this.

Now define for k a positive integer,

k! ≡ k (k − 1)(k − 2)⋅⋅⋅1,0! ≡ 1.

This is called k factorial. Thus P

(k,k)

= k! and you should verify that

P (n,k) =---n!--
(n− k)!

Now consider the number of ways of selecting a set of k different numbers from S_{n}. For each
set of k numbers there are P

(k,k)

= k! ways of listing these numbers in order. Therefore,
denoting by

( n )
k

the number of ways of selecting a set of k numbers from S_{n}, it must be
the case that

( )
n ---n!--
k k! = P (n,k) = (n − k)!

Therefore,

( n ) n!
k = --------.
k!(n − k)!

How many ways are there to select no numbers from S_{n}? Obviously one way. Note the above
formula gives the right answer in this case as well as in all other cases due to the definition
which says 0! = 1.

Now consider the problem of writing a formula for

(x+ y)

^{n} where n is a positive integer.
Imagine writing it like this:

n times
◜---------◞◟--------◝
(x + y)(x + y)⋅⋅⋅(x + y)

Then you know the result will be sums of terms of the form a_{k}x^{k}y^{n−k}. What is
a_{k}? In other words, how many ways can you pick x from k of the factors above
and y from the other n − k. There are n factors so the number of ways to do it
is

( n )
k .

Therefore, a_{k} is the above formula and so this proves the following important theorem known
as the binomial theorem.

Theorem 2.6.1The following formula holds for any n a positive integer.