Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

2

Permutations, Combinations, and the Binomial
Theorem

2
...
Of greater interest are the r-permutations and r-combinations, which are ordered and unordered selections,
respectively, of r elements from a given finite set
...
If you would like extra reading, please refer to Sections 5
...
4
in Rosen
...

• Use the Binomial Theorem to find the expansion of (a + b)n for specified a, b and n
...

• Provide a combinatorial proof to a well-chosen combinatorial identity
...
2

Overview and Definitions

A permutation π of A = {a1 , a2 ,
...
, aπn of the elements of
A
...
For example some permutations of the set A = {a, b, c, d} are
a, b, c, d or d, b, c, a or d, a, c, b
...
Generally, there
are n! permutations of an n-element set
...
, aπr of some r-subset of A
...
As an example,
for the set A = {a, b, c, d} some examples of 2-set permutations of elements of A are a, b or a, c
or b, c, and so on
...
Some examples of 3-set permutations of elements
of A are a, b, c or a, c, d or b, c, a, and so on
...

An r-combination of an n-set A is simply an r-subset {ai1 , ai2 ,
...
There are
C(n, r) of these
...
These are associated with a mnemonic called Pascal’s Triangle and a powerful
result called the Binomial Theorem, which makes it simple to compute powers of binomials
...
The sort of combinatorial proof that we work with
here consists of arguing that both sides of an equation of two integer expressions are equal to

the cardinality of the same set
...


2
...


A permutation of an n-set is an arrangement of its elements
...
, so the number
of possible permutations of an n-set is n(n − 1)(n − 2) · · · (2)(1) = n!
...
Of greater interest is the notion of an r-permutation of an n-set (r ≤ n)
...
The usual notation for the number of these,
if repetition is forbidden, is P (n, r), which is computed by taking the product of the first r
numbers counting down from n
...

=
(n − r)(n − r − 1)(n − r − 2) · · · (2)(1)
(n − r)!
This is sometimes called a falling factorial
...
Note that this can be obtained by the multiplication principle as well as
10 · 9 · 8 = 720
...
The number of 3-digit decimal numbers with
repetition (and possible leading zeros) allowed is simply 103 = 1000
...

(b) Here is a commonly-encountered sort of problem
...
The simplest
approach is to treat DEF as a single “letter”
...

3!
(c) Let A = {a, b, c} be a 3-set
...


2

Now for r-combinations: In how many ways can we choose an r-subset (no repetition) of
an n-set? Such a subset is called an r-combination
...

Note that we are partitioning the n-set into sets: one r-set and one n − r-set
...
For
3!
example there are C(3, 2) = 2!1! = 3 possible ways of choosing a 2-set from a set A = {a, b, c},
namely {a, b}, {b, c} and {a, c}
...
It follows
by the Product Rule that P (n, r) = r!C(n, r), but then
C(n, r) =

n!
1
P (n, r) =

...

The formula above is not a practical formula for hand computation, but we can find a
better one:
C(n, r) =

n!
n(n − 1) · · · (n − r + 1)(n − r)!
n(n − 1) · · · (n − r + 1)
=
=
;
r!(n − r)!
r!(n − r)!
r!

(1)

note that there are exactly r factors in numerator and denominator of the last fraction
...
We can rearrange the
formula for C(n, r) as follows:
C(n, r) =

n!
n!
n!
=
=
= C(n, n − r)
...
For example,
100!
, which is beyond the range of many
what is C(100, 98)? By definition, C(100, 98) =
98!2!
calculators
...
But by (2) and (1) together, we have
C(100, 98) = C(100, 2) =

(100)(99)
= 50 · 99 = 4, 950
...
How many committees of four can be formed if
(a) the department chairman is not eligible?
(b) exactly one of the committee members must be a woman?
(c) exactly one must be a woman, and Professors Smith and Jones (both men) refuse to
serve together
...
This can be done in C(18, 4) = 3060 ways
...

(c) All of the committees formed in (b) qualify except those in which Smith and Jones are
both members
...


2
...
But there is another way, equally simple
...
For
our purposes, combinatorial proof is a technique by which we can prove an algebraic identity
without using algebra, by finding a set whose cardinality is described by both sides of the
equation
...

Proof: We can partition an n-set into two subsets, with respective cardinalities r and n − r,
in two ways: we can first select an r-combination, leaving behind its complement, which has
cardinality n − r and this can be done in C(n, r) ways (the left hand side of the equation)
...
The
number of possible outcomes is the same either way
...
2
It’s a remarkable method
...
There are times when it is far easier to devise a combinatorial proof than an
algebraic proof, as we’ll see shortly
...


2
...
This is called a
r
binomial coefficient, and is pronounced “n choose r”
...

k

This is the Binomial Theorem
...

Proof: Expanding (x + y)n , we get (x + y)n = (x + y)(x + y) · · · (x + y), a product of n factors
...
Since the power of y is k, we need to choose the y from k
factors (there are n ways to so), and to choose x from the remaining n − k factors, so it
k
follows that the coefficient on xn−k y k is n
...


n k n−k
x y
...

Example 3: We start with some straightforward applications of the theorem
...


(x + y)5 =

(b)

(2x − y)5 = ((2x) + (−y))5
5
5
5
5
5
=
(2x)5 (−y)0 +
(2x)4 (−y)1 +
(2x)3 (−y)2 +
(2x)2 (−y)3 +
(2x)1 (−
0
1
2
3
4
= 32x5 − 30x4 y + 80x3 y 2 − 40x2 y 3 + 10xy 4 − y 5
...
The entire expansion of (2x−3y)6 can be computed
in similar fashion
...
For example, let n ∈ Z+ , and let
0 ≤ m ≤ n
...
To see this, simply note that, by the Binomial Theorem,
k

nk =
j=0

k
mk (n − m)k−j
...

k
k=0
Here are some additional examples of combinatorial proof
...

2

Here is a combinatorial solution
...

Proof: The expression on the left-hand side is the number of 2-subsets of a 2n-set
...
We now choose all
the possible 2-subsets, by counting all the choices: all the 2-subsets that have exactly 2 red
elements, all the 2-subsets that have exactly 2 blue elements, and all the 2-subsets that have
exactly one red element and one blue element
...
By the Sum Rule, the
1 1
number of 2-subsets of A is 2 n + n2
...
Suppose we want to prove the identity,
2n
3

=2

n
n
+ 2n

...

Proof: The expression on the left counts the number of 3-subsets of a 2n-set
...
There are n red 3-subsets, n blue 3-subsets,
3
3
n n
3-subsets with two red elements and one blue, and n n 3-subsets with two blue
2 1
2 1
elements and one red
...
The result follows
...

r−k

Proof: The left hand side has two factors: the first binomial coefficient is the number of ways
to choose an r-subset of an n-set; the second is the number of ways to choose a k-subset from
the r-set just chosen (which leaves the remaining r − k elements)
...
We could just as well
construct such a partition by first choosing the k-subset, then choosing the (r − k)-subset from
the (n − k)-subset left behind
...
The practical value of the triangle is questionable, but the value of the identity
that generates the coefficients therein, called Pascal’s Identity, is very useful
...

k−1
k

The identity can be easily proved using a combinatorial proof:
Proof: The left side of the identity is the number of k-subsets of an n-set
...
A given k-subset of A either contains a, or not
...
Together, they give all
the k-subsets of an n-set, regardless if the k-subset contains a or not
...

j−1

j=1

To see this, try substituting j − 1 in for j in the expression k−1 k xj
...
The last step in the sequence uses
Pascal’s identity
...

Recall the statement of the theorem: for all n ≥ 0, (x + y)n = n n xn−j y j
...

j
k
k

For the inductive step, let k ≥ 0, and assume that (x + y) =
j=1

(x + y)k+1 = (x + y)(x + y)k
= x(x + y)k + y(x + y)k
k

= x
j=0

k k−j j
x y +y
j
7

k

j=0

k k−j j
x y
j

k n−j j
x y
...


2
...

1
...
How many strings of length three over Σ = {a, e, i, o, u} have no repeated letter?
3
...
What is the number of 3-element subsets of {1, 2,
...
Joe’s Pizzeria offers two styles of crust and the following optional toppings: extra cheese,
pepperoni, sausage, mushrooms, green peppers, artichokes, onions, and anchovies
...
Is this true?
6
...
What is the coefficient on x3 y 3 in (2x − y)6 ?
8
...

n

9
...


10
...


Solutions to Exercises in Chapter 2: Permutations, Combinations, and the
Binomial Theorem
*********************************************************************
1
...
This problem can be
solved using the product rule alone, and so could have been included in the exercises for
Chapter 1
...
How many strings of length three over Σ = {a, e, i, o, u} have no repeated letter?
Solution: P (5, 3) = 60
...
How many strings over Σ = {a, e, i, o, u} have no repeated letter?
Solution: A string over Σ with no repeated letter can contain 0, 1, 2, 3, 4, or 5 symbols,
so the number of such strings is
5

P (5, k) = 1 + 5 + 20 + 60 + 120 + 120 = 326
...
What is the number of 3-element subsets of A = {1, 2,
...

5
...
Joe
claims that he offers over 500 different pizzas
...
There are two choices of crust, and 28 = 256 choices of topping
...

6
...
To find the
number with no adjacent paperbacks, we count the permutations of the hardbacks, the
ways to choose four nonadjacent locations for the paperbacks, and the permutations of
the paperbacks separately
...
By the Product Rule, the
grand total is 720 · 35 · 24 = 604, 800 ways to get the job done
...
What is the coefficient on x3 y 3 in (2x − y)6 ?
Solution: The coefficient on x3 y 3 is

6
3

· 23 · (−1)3 = −160
...
Use the Binomial Theorem to show that, for any n ∈ N, 3n can be expressed as a linear
combination of powers of 2, with the largest exponent being n
...
Use the Binomial Theorem to prove that
k=0
n
n

n

Proof: 2 = (1 + 1) =
k=0

n k n−k
1 1
=
k

10
...

k
n
k

2

= 2n
...

k
2n
2

+

2

n
2

+ 2n2
...
Let A be a 3nset containing, say, 2n red and n blue elements
...
The result follows
...
3 : 9, 11, 13, 17, 19, 21, 23, and 37, and in section 5
...

************************************************************************************
Self-Quiz on Permutations, Combinations, and the Binomial Theorem
1
...
In how many ways can five men and five women be arranged in a line for a photograph
so that men and women alternate?
3
...
Give a combinatorial proof that

3n
3

n
n
n
=3
+ 6n
+
3
2
1

3


...
In how many ways can we construct a license number consisting of one decimal digit
followed by three uppercase alphabetical characters followed by three decimal digits, if
no characters or digits can be repeated?
26!
Solution: The number of ways to do this is 10P (26, 3)P (9, 3) = 10 23! 9! = 10(26 · 25 ·
6!
24)(9 · 8 · 7) = 78624000
...
In how many ways can five men and five women be arranged in a line for a photograph
so that men and women alternate?
Solution: There are 5! = 120 ways to arrange the men, and 5! = 120 ways to arrange the women
...
The total, then, is 1202 · 2 = 28, 800
...
What is the coefficient on x2 y 5 in (x + y)7 ? In (x − 2y)7 ?
Solution: The coefficient on x2 y 5 in (x + y)7 is
(x − 2y)7 is 7 (−2)5 = −672
...
Give a combinatorial proof that

3n
3

= 3n + 6n

7
2

= 21
...


3n
is the number of 3−subsets
3
of A
...
Suppose that A contains n elements each of three
colors, say red, blue, and green
...
There are 3 n 2 n = 6n n ways to choose two elements of one color and
2
1
2
3
one element of a second color
...
The result follows
...
Then

Note: the assumption that A contains n elements each of three colors is only one way
of forcing A to be the disjoint union of three n-sets, which in turn was dictated by
the right-hand side of the identity to be proven
...
(Try it!)

11



---