Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

permutation





A particular ordering of a collection of objects. For example, if an athlete has won three medals, a bronze one (B), a silver one (S), and a gold one (G), there are six ways they can be permuted or lined up: BSG, BGS, SBG, SGB, GBS, and GSB. If six people want to sit on the same park bench, there are 720 ways in which they can organize themselves. In general, n things can be permuted in n × (n - 1) × (n - 2) × ... × 2 × 1 = n! ways (where "!" is the symbol for factorial). How about if there are n distinct objects but we want to permute them in groups of k (where k less-than or equal-to sign" n). How many ways can that be done? The first member of the group can be picked in n ways because there are n objects to pick from. The second member can be filled in (n - 1) ways since one of the n elements has already been taken. The third member can be filled in (n - 2) ways since 2 elements have already been used, and so. This pattern continues until there are k things have been chosen. This means that the last member can be filled in (n - k + 1) ways. Therefore a total of n (n - 1)(n - 2) ... (n - k + 1) different permutations of k objects, taken from a pool of n objects, exist. If we denote this number by P(n, k), we can write P(n, k) = n! / (n - k)!


Related entry

   • combinatorics