Например, для перестановку 2 3 1 из (3) получим следующее: 423 1,243 1,234 1, 2 3 14. Очевидно, это все возможные перестановки из п объектов, причем ни одна из них не повторяется.

Метод 2. Для каждой перестановкиoi ог ... a„ i из {1,2,..., п-1} объектов построим еще п перестановок следующим образом. Сначала построим набор

Ol 02 ... 0„ 1 , 01 02 . . . 0„ 1 , . . . , Ol 02 . . . 0„ i (п - ) .

Затем заменим элементы каждой перестановки цифрами {1,2,...,п}, сохраняя порядок. Например, для перестановки 2 3 1 из (3) получим

231, 231, 231, 231

и после замены получим

3421, 3412, 2413, 2314.

Есть еще один способ описания этого процесса. Возьмем перестановку Oi ог ... а„ 1 и число А;, 1 < А; < п; добавим единицу к каждому Oj, значение которого >А;. В результате получим перестановку 6162 •• • bn-i из элементов {1, А; - 1, A;-f-l, ..., п}; значит, 6162 • • • fcn-ifc -это перестановка чисел {1,..., п}.

При таком способе построения тоже очевидно, что каждая перестановка из п элементов встречается только один раз. Аналогичные построения можно выполнить, помещая А; не справа, а слева либо в любой другой фиксированной позиции.

Если рп - число перестановок из п объектов, то оба описанных метода показывают, что Рп - прп-1\ это дает два дополнительных доказательства соотношения р„ = п(п - 1) ... (1), которое мы уже вывели из (2).

Рп -это очень важная величина, которую называют п-факториал и записывают следзющим образом:

п! = 1 • 2 •... • п = Д А;. (4)

1к=1

Из нашего соглашения, касающегося пустых произведений (раздел 1.2.3), следует, что

О! = 1. (5)

Учитывая это соглашение, видим, что основное тождество

п! = (п - 1)! п (6)

справедливо для всех целых положительных п.

В вычислительных задачах факториалы встречаются довольно часто, поэтому я советую читателю запомнить значения первых из них:

0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120.

Факториалы растут очень быстро, например 1000! - это целое число, имеющее свыше 2 500 цифр.

Очень полезно запомнить значение 10! = 3 628 800; кроме того, нужно знать, что 10! - это примерно 3 миллиона. В определенном смысле это число представляет собой некую грань между тем, что реально можно вычислить на компьютере, и тем, что нельзя. Если в алгоритме предусмотрена проверка более чем 10! случаев.

то на практике для его выполнения может потребоваться слишком много машинного времени. С другой стороны, если нужно проверить 10! случаев, на каждый из которых требуется, скажем, одна миллисекунда машинного времени, то выполнение алгоритма займет не больше часа. Я согласен, что все эти рассуждения весьма туманны, но во всяком случае они помогут вам получить некоторое представление о том, что реально можно вычислить на компьютере, а что нет.

Естественно, возникает вопрос, как связано п! с другими математическими величинами. Можно ли определить, насколько велико значение 1000!, не вьшолняя трудоемких операций умножения по формуле (4)? Ответ на этот вопрос дал Джеймс Стирлинг (James Stirling) в своей знамеш1ТОЙ работе Metbgdus DifferentiaUs (1730 г.), с. 137. Он получил формулу

п!?»\/2()" (7)

Здесь "rs" означает "приближенно равно", а "е"-это основание натзрального логарифма (см. раздел 1.2.2). Приближенную формулу Стирлинга (7) мы докажем в разделе 1.2.11.2. А простое доказательство менее точного результата дано в упр. 24. Рассмотрим пример применения формулы Стирлинга. Вычислим

40320 = 8! « 4v = ге"* » 67108864 • 1.77245 • 0.00033546 w 39902.

В данном случае погрешность составляет приблизительно 1%; впоследствии мы Звидим, что относительная погрешность расчетов по этой формуле приблизительно равна 1/(12п).

Помимо приближенного значения, которое вычисляется по формуле (7), можно довольно легко получить точное значение п! с помоац.ю разложения на простые множители. Действительно, простое число р является делителем п! кратности

t>o

Например, если п = 1000 и р = 3, то имеем

1000

1000

L 3 J L 9 J L 27 J

1000

1000 L 81 J

1000

L243 J

1000 L 729 J

= 333 + 111 + 37 + 12 + 4 + 1 = 498.

Таким образом, 1000! делится на 3*®*, но не на 3*. Хотя формула (8) записана в виде бесконечной суммы, на самом деле для любых чисел пир эта сумма имеет конечное число слагаемых; дело в том, что, начиная с некоторого А;, все эти слагаемые обращаются в нуль. Из упр. 1.2.4-35 следует, что L»/P*"J = [L"/P*J/pJ; это позволяет jnpocTHTb вычисления по формуле (8), так как можно просто разделить значение предыдущего члена на р и отбросить остаток.

Формула (8) следует из того, что L"/P*J - это количество целых чисел из {1,2,...,«}, кратных р*. Если рассмотреть целые числа в произведении (4), то станет ясно, что любое целое, которое делится нар-, но не делится на р, учитывается ровно j раз: один раз-в [n/pj, другой раз - в L"/PJ> •и, наконец, в [п/р\. Таким образом, учитьшаются все случаи, когда р является простым множителем в п1.

Теперь возникает еще один естественный вопрос. Мы определили п! для неотрицательных целых чисел п. Но, возможно, факториальная функция имеет смысл также для рациональных и даже для действительных чисел п? Например, чему равен (I)!? Для иллюстрации этого вопроса давайте введем "термиальную" функцию

п? = 1 + 2 + --- + п = Е> ()

которая аналогична факториальной, за исключением того, что здесь выполняется сложение, а не умножение.

Из формулы 1.2.3-(15) мы уже знаем, чему равна сумма арифметической прогрессии:

n? = in(n + l). (10)

Таким образом, используя формулу (10) вместо (9), можно обобщить определение "термиальной" функции для произвольного п. И, отвечая на заданный выше вопрос, получим (1)? = .

Стирлинг сам предпринял несколько попыток обобщить понятие факториала п! для нецелых п. Он представил приближение (7) в виде бесконечной суммы, но, к сожалению, эта сумма не сходилась ни для одного значения п. Формула (7) дает очень хорошее приближение, но ее нельзя продолжить так, чтобы получить точное значение. [Эта довольно необычная ситуация обсуждается в книге К. Кпорр, Theory and AppUcation oflnRnite Series, 2nd ed. (Glasgow: Blackie, 1951), 518-520, 527, 534.]

Стирлинг предпринял еще одну попытку, обратив внимание на то, что

,! = l+(l-l)n+(l-l4-l)n(n-l)

(Мы докажем эту формулу в следующем разделе.) Данная сумма из соотношения (11) кажется бесконечной, но на самом деле она конечна для любого неотрицательного целого п. Тем не менее формула (11) не дает желаемого обобщения для функции п\, так как бесконечная сумма сходится только в том случае, если п - неотрицательное целое число (см. упр. 16).

Но Стирлинг не упал духом и нашел последовательность 01,02,..., такую, что

Inn! = 01п-Ь 02п(п - 1)-I----= E"fc-n П (n-j)- (12)

*>о 0<j<k

Однако он не смог доказать, что эта сумма определяет функцию п! для всех дробных п, хотя и нашел значение ()! - у/тт/2.

Приблизительно в то же время данной задачей занимался и Леонард Эйлер (Leonhard Euler), и именно он первым нашел обоснованное обобщение:

П1 = lim-----г----. (13)

т-ос {п + 1){п + 2)...{п + т)

Эйлер изложил эту идею в письме Христиану Гольдбаху (Christian Goldbach) от 13 октября 1729 года. В его формуле п! определяется для любого значения п.