A permutation of a set of distinct objects is an ordered arrangement of these objects.
An ordered arrangement of r elements of a set is called an r-permutation.
Example. Let S = {1, 2, 3}. The arrangement 3, 1, 2 is a permutation of S. The arrangement 3, 2 is a 2-permutation of S.
The number of r -permutations of a set with n elements is denoted by P(n, r).
Theorem 1. The number of r -permutations of a set with n distinct elements is
Proof: The first element of the permutation can be chosen in n ways, since there are n elements in the set. There are n – 1 ways to choose the second element of the permutation, since there are n – 1 elements left in the set after using the element picked for the first position. Similarly, there are n – 2 ways to choose the third element, and so on, until there are exactly n – r + 1 ways to choose the r th element. Consequently, by the product rule, there are 
r -permutations of the set. 
; 
Example. How many different ways are there to select 4 different players from 10 players on a team to play four tennis matches, where the matches are ordered?
Solution: The answer is given by the number of 4-permutations of a set with 10 elements. By Theorem 1, this is P (10, 4) = 10 × 9 × 8 × 7 = 5040.
Example. Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes. How many possible orders can the saleswoman use when visiting these cities?
Solution: The number of possible paths between the cities is the number of permutations of seven elements, since the first city is determined, but the remaining seven can be ordered arbitrarily. Consequently, there are 
Дата добавления: 2014-12-23; просмотров: 342 | Поможем написать вашу работу | Нарушение авторских прав |