The product n.(n−1).(n−2).....3.2.1, is called the factorial of n, and is denoted by n! (read as ‘n-factorial’). Thus n! is the nth factorial number. It is found convenient to define 0! = 1. The first few factorial numbers in base ten are: 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, ...
Theorem (The Permutation Principle): The number of ways of arranging n different things in sequence is n!. Proof: The first can be chosen in n ways, the second in n−1 ways, the third in n−2 ways and so on. Hence by the multiplication principle the total is the product of these ways.
Example: In how many ways can n different books be arranged on a shelf so that two particular books are next to one another? Regarding the specified books as one item there are (n−1) items to arrange, and the two books themselves can be arranged in 2 ways. Answer 2.(n−1)!
Example: How many ways are there of arranging n chess rooks on a board n ranks by n files with none guarding or attacking any other. Answer n!.
Theorem (The Circular Permutation Principle): The number of ways of arranging n things round a circle that can be rotated but not reflected is (n−1)! Proof: We can rotate the circle so that one thing is always in the same position. The others can then be arranged in (n−1)! ways. Corollary: The number of ways of arranging n things round a circle that can be rotated or reflected is (n−1)!|2, provided n>2. Proof: The arrangements in the previous result occur in pairs that are reflections of each other (except when n = 2 or less, in which case reflection makes no difference). If one is regarded as ‘clockwise’ the other is ‘anticlockwise’.
Example: How many necklace designs can be formed using six different coloured beads? Answer 5!|2 = 60.
Theorem (The Truncated Factorial Rule): The number of ways of choosing a sequence of m elements, all different, from a set of n elements is n!|(n−m)!. Proof: The first element can be chosen in n ways, the second in (n−1) ways, and so on until we reach the mth element which can be chosen in (n+1)−m ways. The product of these is n.(n−1).(n−2).... as far as (n+1)−m. This is n! with the remaining terms cancelled, and can thus be expressed by the quotient n!|(n−m)!.
Example: Count the number of one-to-one operators whose domain is {1,2,...,m} and whose range is a set of n elements.
Example: Express in factorials: n.(n^2 − 1).(n^2 − 4).(n^2 − 9). Answer (n+3)!|(n−4)! This uses the property (n^2)−(r^2) = (n−r).(n+r).
Theorem (The Principle of Divided Factorials): The number of ways of arranging n things in a row when there are a alike of one kind, b of a second kind, c of a third kind is n!|(a!.b!.c!....) Proof: If the things were all different the number of arrangements would be n! However, if a of the things are alike they can be permuted among themselves in a! ways without altering the positions of the other things. Corollary: The number of ways of arranging n things in sets of a, b, c ... things (where of course n = a+b+c+...) is n!|(a!.b!.c!. ...).
Example: In the game of Bridge a pack of 52 cards is used and they are dealt out equally to the four players (known as North, South, East and West) so that each has a hand of 13 cards. The number of different ways the cards can be dealt out is thus: 52!|(13!.13!.13!.13!) = 52!|(13!^4).
Example: In how many ways can the letters of the word REARRANGE be arranged? Answer. 9!|(2!.2!.3!) = 15120.
Every three successive numbers contain 2 and 3 therefore (3.k)! has a factor of 6^k (so in base 6 has k zeros at the end).
Divisibility: The product of r consecutive numbers is divisible by r!.