294
Sets, Combinatorics, and Probability
In Exercises 101–104, use algorithm permutation generator to generate the next permutation after the given
permutation in the set of all permutations of the numbers {1, … , 7}.
101. 7431652
102. 4365127
103. 3675421
104. 2756431
105. In generating all combinations of five items from the set {1, … , 9}, find the next five values in the list
after 24579.
106. In generating all combinations of four items from the set {1, … , 6}, find the next five values in the list
after 1234.
107. Describe an algorithm to generate all permutations of the integers {1, … , n} in reverse lexicographical
order.
108. Describe an algorithm to generate all permutations of r elements from the set {1, … , n}.
S e c t i o n 4 . 5 binomial theorem
The expression for squaring a binomial is a familiar one:
(a + b)
2
= a
2
+ 2ab + b
2
This is a particular case of raising a binomial to a nonnegative integer power n.
The formula for (a + b)
n
involves combinations of n objects. Before we prove this
formula, we’ll look at a historically interesting array of numbers that suggests a
fact we will need in the proof.
Pascal’s triangle
Pascal’s triangle is named for the seventeenth-century French mathematician
Blaise Pascal (for whom the programming language Pascal was also named), although it was apparently known several centuries earlier. Row n of the triangle
(n ≥ 0) consists of all the values C(n, r) for 0 ≤ r ≤ n. Thus the triangle looks like
this:
C(0, 0)
C(1, 0) C(1, 1)
C(2, 0) C(2, 1) C(2, 2)
C(3, 0) C(3, 1) C(3, 2) C(3, 3)
C(4, 0) C(4, 1) C(4, 2) C(4, 3) C(4, 4)
C(5, 0) C(5, 1) C(5, 2) C(5, 3) C(5, 4) C(5, 5)
C(n, 0) C(n, 1)
...
C(n, n 1) C(n, n)
Row
0
1
2
3
4
5
n