0 = 12.
Вывод:
F0 + F1 + F2 + F3 + F4 = 12 = F6 – 1.
Рассмотрим общий случай. Нам дана рамка длиной n + 2. Сколько есть вариантов ее заполнения, при которых первая костяшка домино находится на некой позиции k? В этом случае первые k – 1 позиций заняты квадратами. Таким образом, в общей сложности занята k + 1 позиция[99]. Оставшиеся (n + 2) – (k + 1) = n – k + 1 можно заполнить любыми способами. Это дает Fn – k +1 вариантов. Построим диаграмму:
Если k меняется от 1 до n + 1, величина n – k + 1 меняется от 0 до n. Таким образом, количество вариантов заполнения нашей рамки с использованием хотя бы одной костяшки домино равно
Fn + Fn– 1 + … + F1 + F0.
Если поставить слагаемые в обратном порядке, мы получим левую часть выражения (*). Таким образом, мы нашли второй ответ на поставленный вопрос:
F0 + F1 + … + Fn.
Итак, у нас есть два ответа на вопрос. Величины, полученные с помощью двух выведенных нами формул, совпадают, и тождество (*) доказано.
Сложение двух следующих друг за другом чисел Фибоначчи дает очередное число Фибоначчи. В этом разделе мы затронем вопрос поинтереснее: что будет, если мы поделим число Фибоначчи на предшествующее ему в ряду? Посчитаем соотношение Для возрастающих значений k. В таблице вы можете видеть соотношения от
Чем больше становятся числа Фибоначчи, тем ближе соотношение к константе, примерно равной 1,61803.
Это число – вы будете удивлены – достаточно известное, и если вы введете его в поисковую систему, вывалится уйма страниц о золотом сечении. Что это такое?
Соотношение соседних чисел Фибоначчи не одинаково. Однако оно почти одинаково, если числа достаточно велики. Давайте найдем формулу для числа 1,61803 и для этого на время будем считать, что все соотношения одинаковы. Введем обозначение x:
Это значит, что Fk+ 1 = xFk, Fk+ 2 = xFk+ 1 и т. д. Можно переформулировать:
Fk+ 2 = xFk+ 1 = x²Fk.
Но мы же знаем, что Fk +2 = Fk+ 1 + Fk. Таким образом,
x²Fk = xFk + Fk.
Если мы поделим обе части на Fk и перегруппируем слагаемые, то получим квадратное уравнение:
x² – x – 1 = 0.
Оно имеет два решения:
Соотношение должно быть положительным. И вот мы получили знакомое нам число. Обычно для обозначения золотого сечения используют греческую букву ϕ (фи):
Мы уже приметили, что соотношение соседних чисел Фибоначчи приближается (стремится) к ϕ. Это замечательно. Это дает нам еще один способ вычислять приблизительные значения чисел Фибоначчи.
Последовательность чисел Фибоначчи – это ряд F0, F1, F2, F3, F4, F5… Если все соотношения будут одинаковы, мы получим формулу:
Fn = cϕⁿ.
Здесь с – еще одна константа. Сравним округленные значения Fn и ϕⁿ для разных n:
Для больших значений n соотношение Это число равно в точности Другими словами,
Насколько хороша эта формула? Настало время новых подсчетов!
Обратите внимание: если округлить до ближайшего целого числа, мы получим в точности Fn.
Если вы не хотите утруждать себя округлениями до целого числа, то формула, названная в честь Жака Бине[100], даст вам точное значение:
Глава 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! таким манером – просто каторжный труд. Есть ли какой-нибудь быстрый способ[101]?
Красивая, но никуда не годная с точки зрения реальных вычислений идея состоит в том, чтобы определить 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.
Вот бы найти способ побыстрее… Есть ли основания предполагать, что мы можем ускорить вычисления? Да, и про это нам говорят треугольные числа[102] – суммы вида:
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.
Это похоже на факториал, но со сложением вместо умножения. Есть ли способ посчитать