Rational Mathematics

Factorials

The product n·(n–1)·(n–2)· ... ·3·2·1, is called the factorial of n, and is denoted by n! (read ‘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!.