Permutations
Factorials
Definition 1: For \(n\in\mathbb{Z}\), \(n \ge 0\), define \(0!=1\) and \(n!=(1)(2)\cdots(n-1)(n)\). Alternatively, define \(n!\) for non-negative integers \(n\) by setting \(0!=1\) and \(n!=n(n-1)!\).
Proposition: The number of different lists of length \(n\) made up of elements from the set \(\{1,2,\ldots, n\}\), without repetitions, is \(n!\).
Permutations
Definition: Let \(X\) be a set. A permutation of \(X\) is a list of length \(|X|\) of the elements of \(X\), without repetition. (Note: There are other definitions of permutations in other contexts, all related to this one).
Examples:
Definition: Let \(X\) be a set. A \(k\)-permutation of \(X\) is a list of \(k\) elements of \(X\) without repetition. \(P(n,k)\) is the number of \(k\) permutations of a set with \(n\) elements.
Proposition: The number \(P(n,k)\) of \(k\)-permutations of a set with \(n\) elements is \(n(n-1)\cdots (n-k+1)\) or, equivalently \[ P(n,k) = \frac{n!}{(n-k)!} \]
Proof:
Examples of \(k\)-permutations
(Problem 7, page 84) How many \(9\)-digit numbers can be made from the digits \(1,2,3,4,5,6,7,8,9\) if repetition is not allowed and all the odd digits occur first, followed by all the even digits.
(Problem 15, page 84) In a club of 15 people, there is a president, vice-president, secretary, and treasurer. In how many different ways can this be done?