Книга: Путеводитель для влюбленных в математику
Назад: Глава 9 Числа Фибоначчи[95]
Дальше: Глава 11 Закон Бенфорда
Глава 10
Факториал!
Книги на полке
Сколькими способами можно расставить ваши книги на полке? Разумеется, это зависит от того, сколько у вас книг. Начнем с простейшего примера. Допустим, ваша библиотека насчитывает всего три книги с незамысловатыми названиями A, B и C.
Вначале решим, какую книгу поставить с левого края. Пусть это будет A. В таком случае остается всего два варианта расположения книг на полке: ABC и ACB. То есть, когда A стоит слева, существует две комбинации.
Если поставить на левую позицию книгу B, тогда снова возможны два варианта: BAC и BCA. Если слева стоит книга C, появляются еще две комбинации: CAB и CBA.
В общей сложности есть шесть вариантов расстановки книг:
ABC, ACB, BAC, BCA, CAB, CBA.
Теперь представим, что у нас появилась четвертая книга: D. Сколькими способами можно расставить книги теперь? Используем тот же метод. Для начала решим, какую книгу поставить слева; пусть на первый раз снова будет A. Оставшиеся три книги, как мы знаем, можно расставить шестью способами – только что мы обосновали, почему это так.
Точно так же есть шесть способов расположить оставшиеся книги, если слева будет B, C или D. В общей сложности получается 6 × 4 = 24 способа. Вот они:
Прежде чем мы перейдем к вопросу о произвольном количестве книг, давайте проанализируем вариант с пятью книгами: A, B, C, D и E. Как и раньше, вначале решаем, какую книгу поставить на крайнюю левую позицию. Если это A, у нас остается четыре книги. Сколькими способами можно их расставить? Мы уже выяснили, что таких способов 24. Еще 24 способа появляется, если на крайней левой позиции стоит B. То же самое для C, D и E. Итого в совокупности 24 + 24 + 24 + 24 + 24 = 120.
Каков был наш путь решения проблемы пяти книг? Есть пять вариантов, какую книгу поставить на крайнюю левую позицию. Когда она уже там, остаются четыре книги. Таким образом, количество вариантов для пяти книг в пять раз больше, чем количество вариантов для четырех. Давайте запишем это на математическом языке.
Пусть A5 – количество вариантов расстановки пяти книг. Мы получаем формулу:
A5 = 5 × A4.
Здесь A4, как вы догадались, – количество вариантов для четырех книг.
Как найти A4? Да точно так же! Слева может быть одна из четырех книг; в каждом случае останется три книги и соответствующее количество вариантов их взаиморасположения. Мы получаем:
A4 = 4 × A3.
Соответственно, A3 = 3 × A2. Количество вариантов для двух книг (куда уж проще) составляет A2 = 2 × A1, где, разумеется, A1 = 1.
И что же мы имеем?
A5 = 5 × A4 = 5 × 4 × A3 = 5 × 4 × 3 × A2 = 5 × 4 × 3 × 2 × A1 = 5 × 4 × 3 × 2 × 1 = 120.
Теперь все ясно и с общим случаем. Количество способов расставить N книг на полке:
N × (N – 1) × (N – 2) × … × 3 × 2 × 1. (A)
Выражение (A) носит название N факториал. Факториал обозначают восклицательным знаком: N!. Например, 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720.
А есть ли формула?
Если мы задались целью вычислить значение 10! самый простой путь – перемножить числа от 1 до 10 и получить:
10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800.
Но для подсчета 20! придется перемножать двадцать чисел. А вычислять 100! таким манером – просто каторжный труд. Есть ли какой-нибудь быстрый способ?
Красивая, но никуда не годная с точки зрения реальных вычислений идея состоит в том, чтобы определить 10! через 9!. Это же «проще простого»:
10! = 10 × (9 × 8 × … × 3 × 2 × 1) = 10 × 9!.
Для произвольного значения N мы имеем:
N! = N × [(N – 1) × (N – 2) × … × 3 × 2 × 1].
Иными словами,
N! = N × (N – 1)!. (B)
Формула (B) чудесна, но она мало помогает при вычислении, скажем, 20!. Мы должны вычислить 19! и умножить его на 20. Само собой, она подсказывает, как вычислить 19!: для этого надо посчитать 18!. А затем умножить на 19. В конце концов нам придется перемножать все целые числа от 1 до 20.
Вот бы найти способ побыстрее… Есть ли основания предполагать, что мы можем ускорить вычисления? Да, и про это нам говорят треугольные числа – суммы вида:
1 + 2 + 3 + … + N.
Например, пятое треугольное число равно 1 + 2 + 3 + 4 + 5 = 15. Обозначим TN треугольное число, представляющее собой сумму N элементов:
TN = N + (N – 1) + (N – 2) + … + 3 + 2 + 1.
Например:
T10 = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55.
Это похоже на факториал, но со сложением вместо умножения. Есть ли способ посчитать T10, не складывая все десять чисел?
Есть хорошая новость: да, такое возможно, и доказательство выглядит просто и элегантно. Запишем сумму первых десяти целых положительных чисел в возрастающем и убывающем порядке:
Если мы сложим все эти 20 чисел, результат будет равен удвоенному T10. Но мы не станем сразу суммировать числа по горизонтали. Для начала сложим их попарно по вертикали:
В нижней строке все элементы равны 11, потому ответ прост: 11 × 10 = 110. Теперь поделим этот результат пополам: T10 = 110 / 2 = 55.
Как мы будем действовать в общем случае? Для вычисления TN запишем целые числа от 1 до N в возрастающем и убывающем порядке и сложим пару в каждом столбце:
В нижней строке N элементов, каждый равен N + 1; таким образом, их сумма равна N × (N + 1). Поскольку это «двойная порция» TN, получается:
Для вычисления T100 нет необходимости складывать сотню чисел. Нужно лишь посчитать:
(100 × 101) / 2 = 5050.
Вот и ответ.
Существует ли простая, элегантная формула вычисления факториала? Увы, нет. Однако есть формула для вычисления приближенного значения факториала, выведенная Джеймсом Стирлингом:
Эта формула включает два замечательных числа, о которых шла речь в предыдущих главах: π ≈ 3,14159, представляющее собой частное от деления длины окружности на ее радиус (см. главу 6), и число Эйлера e ≈ 2,71828 (см. главу 7).
Точность формулы Стирлинга возрастает при больших значениях N. Например, для N = 10 факториал 10! = 3 628 800, а вычисления по формуле (C) дают 3 598 695,6187. Погрешность – всего около 0,8 %.
Для N = 20 мы получаем:
20! = 2 432 902 008 176 640 000.
По формуле (C):
20! = 2 422 786 846 761 133 393,6839075390.
Погрешность равна около 0,4 %. Если мы перепрыгнем к N = 1000, погрешность составит менее 0,01 %.
Головоломка
Число 145 называют факторионом, потому что оно обладает волшебным свойством. Если мы сложим факториалы составляющих его цифр, то получим то же самое число:
1! + 4! + 5! = 1 + 24 + 120 = 145.
Числа 1 и 2 тоже являются факторионами (но не ноль, как мы увидим чуть позже). Существует всего четыре факториона. Попробуйте самостоятельно найти четвертый.
Это сложновато без компьютерной программы. Ответ приведен в конце главы.
Как вычислить 0!?
Многие испытывают необоримое желание ответить: «0! равен нулю!» (Второй восклицательный знак всего лишь подчеркивает экспрессивность этой фразы.) Первый множитель в N! равен N, а умножение на ноль дает ноль. Однако математики договорились, что 0! = 1, и я завершу главу разъяснением этого факта.
В главе 1 мы обсудили концепцию пустого произведения – умножения при отсутствии элементов. Факториал нуля – пример пустого произведения. Для любого N факториал представляет собой результат перемножения N элементов. Это ясно для положительных значений N, но это верно и для N = 0. По определению, при подсчете N! мы перемножаем все целые числа от 1 до N. В случае N = 0 таких чисел просто-напросто нет, и произведение оказывается пустым. По договоренности, пустое произведение равно 1.
А вот еще одно обоснование того, почему 0! = 1. При подстановке N = 1 в формулу (B) мы получаем:
N! = N × (N – 1)! => 1! = 1 × 0!
Поскольку 1! = 1, мы получаем 0! = 1.
А теперь давайте вернемся к расстановке книг на полке. Сколькими способами можно расставить на полке ноль книг? Есть один-единственный вариант: оставить полку пустой.
Назад: Глава 9 Числа Фибоначчи[95]
Дальше: Глава 11 Закон Бенфорда
