1.2.8 Counting

Knowledge Base > Math

Permutation

A permutation of a finite set S is an ordered sequence of all the elements of S, with each element appearing exactly once. There are n! permutations of n elements, sin ce the first element of the sequence can be chosen in n ways, the second in n- 1 ways, and so on. A k-permutation of S is an ordered sequence of k elements of S, with no element appearing more than once in the sequence. For example, a six 2-permutations of the set {a, b, c} are {ab, ac, ba, bc, ca, cb}. Thus, the number of k-permutation of an n-set is

(1.2.26)

Combinations

A k-combination of an n-set S is a unordered version of k-subset of S, where the 2-set {a, } denoted by ab, for instance. For every k-combination, there are exactly k! permutations of its element, each of which is a distinct k-permutation of the n-set. Thus, the number of k-combinations of an n-set is the number of k-permutations divided by k![1].