Factorielles

Factorials were counted long before they were named, and almost never by people looking for them. The Anuyogadvāra-sūtra, a canonical Jain text whose dating ranges anywhere from 300 BCE to 400 CE, works out how many ways a set of items can be ordered, setting the sorted and reversed arrangements aside and counting the rest. The Hebrew book of creation Sefer Yetzirah, from the Talmudic period, tabulates factorials up to 7! while asking how many words the Hebrew alphabet can form; the eighth-century Arab grammarian Al-Khalil ibn Ahmad al-Farahidi studied them for much the same linguistic reason. Around 1150 Bhāskara II used them in the Līlāvatī to ask in how many ways Vishnu could hold his conch, discus, mace and lotus in his four hands. Ibn al-Haytham, writing around the turn of the millennium, was the first to state what is now called Wilson's theorem, which ties factorials to the prime numbers.

European work came later, and from odd directions. Luca Pacioli computed up to 11! in a 1494 treatise about seating dinner guests. Marin Mersenne published tables reaching 64! in the 1640s, not all of them correct. In 1677 the English bell-ringer Fabian Stedman described factorials to explain change ringing, the art of permuting a peal of tuned bells. Newton wrote down the exponential series, whose coefficients are reciprocal factorials, in a 1676 letter to Leibniz.

The modern machinery then arrived in a cluster. Abraham de Moivre studied the size of large factorials in 1721, and a 1729 letter from James Stirling to de Moivre gave what is now known as Stirling's approximation — the name is Stirling's, though de Moivre had published a weaker version first. Daniel Bernoulli and Euler, working at the same time, extended the factorial to a continuous function, the gamma function. Legendre's formula for the prime factorisation of n! appeared in 1808, the same year Christian Kramp introduced the notation n!. The word itself is a little older: Arbogast coined the French factorielle in 1800, for a more general class of products.

Propriétés principales

• 0! = 1, the empty product — the convention that makes C(n, k) = n! / (k!(n−k)!) come out right at k = 0 and k = n.
• n! = n × (n−1)!, and n! is exactly the number of ways to arrange n distinct objects in a row.
• 19! = 121,645,100,408,832,000 is the first factorial to exceed 2^53 − 1, the largest integer a JavaScript number holds exactly; 20! = 2,432,902,008,176,640,000 is the largest that fits in a signed 64-bit integer.
• The number of trailing zeros in n! is ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … , a case of Legendre's formula. 100! ends in exactly 24 zeros.
• 0! and 1! are the only factorials that are perfect squares: for every n ≥ 2 there is a prime between n/2 and n, and it divides n! exactly once.
• The reciprocals of the factorials sum to e: 1/0! + 1/1! + 1/2! + 1/3! + … = 2.718281828…
• Wilson's theorem: (p − 1)! ≡ −1 (mod p) holds precisely when p is prime, which makes it a (hopelessly slow) primality test.
• Brocard's problem asks when n! + 1 is a perfect square. Only n = 4, 5 and 7 are known, giving 25, 121 and 5041 = 71²; whether any others exist is still open.

Où on les rencontre

• A 52-card deck has 52! possible orders — 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000, about 8.07 × 10⁶⁷ — which is why a properly shuffled deck has almost certainly never occurred before.
• Factorials sit in the denominators of the Taylor series for eˣ, sin x and cos x, and in the k! of the Poisson distribution, so they turn up in any numerical library that evaluates those.
• Brute-force routing: a travelling-salesman instance on n cities has (n−1)!/2 distinct tours, which is why exhaustive search stops being feasible somewhere around twenty cities.
• Sliding-puzzle state spaces: the 15-puzzle has 16!/2 = 10,461,394,944,000 reachable configurations — half of 16!, because sliding tiles can only produce even permutations.
• Change ringing: a full "extent" on n church bells rings all n! orderings without repetition, the practice Stedman documented in 1677.
• Plato proposed 5,040 = 7! as the ideal citizen count for a city, partly because it divides so many ways — a philosophical proposal rather than a mathematical result.