(The number of permutations of n objects taken ? at a time.) Show that for each
ID: 3219571 • Letter: #
Question
(The number of permutations of n objects taken ? at a time.) Show that for each n elementof w, for each ? element of {0, ...., n}?for each set A, for each set B, if A has ? elements and B has n elements, then inj(A, B) has (n)_k elements. (This can be proved by induction on n. The case where K = 0 requires a special argument but is easy. In the inductive step, if K notequalsto 0?use the multiplication rule. The argument is similar to the proof of the exponentiation rule. If you get stuck, work through Example 14.9 and then) In combinatorics, a bijection from a set to itself is called a permutation of the elements of the set.Explanation / Answer
This exercise is equivalent to proving nCk = n!/k!(n-k)!
For, k= 0, nCk= nC0 = n!/0!*n! = 1. Intutively, we can select zero or no objects in only one way.
Let k = m be true, or nCm= n!/m!(n-m)!
INDUCTIVE STEP: To prove nCm+1 = n!/(m+1)!(n-m-1)!
Noting (m+1)! = m!(m+1), we can write
n!/m!(n-m)! = n!(m+1)/(m+1)!(n-m)!
= n!/(m+1)!*(m+1/(n-m)!)
Again, (n-m)! = (n -(m+1))!*(m+1)
Substituting in above, RHS = n!/(m+1)!*(m+1)/(n -(m+1))!*(m+1)
Cancelling out the (m+1) in numerator and denominator,
RHS = n!/(m+1)!(n-(m+1))! = n!/(m+1)!(n-m-1)!
which is simply n objects taken (m+1) at a time.
Hence induction step proved and consequently nCk = n!/k!(n-k)!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.