Permutations

Consider the integer set S = {1, 2, ... , n}. A permutation of S is an ordered arrangement of its elements, a list without repetitions. The number of permutations of S can be computed as follows. The number of distinct possibilities for the first item is n. The number of possibilities for the second item is n-1, namely all the integers in S except the first element in the list. Similarly, the number of distinct possibilities for the m-th item is n - m + 1. This pattern continues until all the elements in S are listed. Summarizing, we find that the total number of permutations of S is n factorial, n! = n (n-1) ... 1 .

Example: We wish to compute the number of permutations of S = {1, 2, 3}. Since the set S contains three elements, it has 3! = 6 permutations. They can be listed as 123, 132, 213, 231, 312, 321.

k-Permutations

Suppose that we list only k elements out of the set S = {1, 2, ... , n}, where . We wish to count the number of distinct k-permutations of S. Following our previous argument, we can choose one of n elements to be the first item listed, one of n-1 elements for the second item, and so on. The procedure terminates when k items have been listed. The number of possible sequences is

Example: A recently formed music group has four original songs they can play. They are asked to perform two songs at a music festival. We wish to compute the number of song arrangements the group can offer in concert. Abstractly, this is equivalent to computing the number of 2-permutations of four songs. Thus, the number of distinct arrangements is 4!/2! = 12.

Example - Sampling without Replacement, with Ordering: An urn contains n balls numbered one through n. A ball is picked from the urn, and its number is recorded on an ordered list. The ball is not replaced in the urn. This procedure is repeated until k balls are selected from the urn, where . We wish to compute the number of possible sequences that results from this experiment. The number of possibilities is equivalent to the number of k-permutations of n elements, which is given by n!/(n-k)!.