Путеводитель для влюбленных в математику

Рассмотрим случай n = 4. Мы ищем варианты заполнения рамки 1 × 6, задействующие хотя бы одну костяшку домино. Мы знаем ответ: F₆ – 1 = 13 – 1 = 12, но нам необходимо получить его иным путем.

Первая костяшка домино может занимать следующие позиции:

Первая колонка демонстрирует случай, когда костяшка находится на первой позиции, вторая – когда костяшка на второй, и т. д.

Сколько вариантов в каждой колонке?

В первой колонке – пять вариантов. Если отбросить домино слева, мы получим ровно F₄ = 5 вариантов для прямоугольника 1 × 4.

Во второй колонке – три варианта. Отбросим домино и квадрат слева. Мы получим F₃ = 3 варианта для прямоугольника 1 × 3.

Аналогично для других колонок. Вот что мы обнаружили:

Таким образом, количество способов замостить квадратами и домино (хотя бы одной костяшкой) прямоугольную рамку 1 × 6 равно

F₄ + F₃ + F₂ + F₁ + F₀ = 12.

Вывод:

F₀ + F₁ + F₂ + F₃ + F₄ = 12 = F₆ – 1.

Рассмотрим общий случай. Нам дана рамка длиной n + 2. Сколько есть вариантов ее заполнения, при которых первая костяшка домино находится на некой позиции k? В этом случае первые k – 1 позиций заняты квадратами. Таким образом, в общей сложности занята k + 1 позиция[99]. Оставшиеся (n + 2) – (k + 1) = n – k + 1 можно заполнить любыми способами. Это дает F_{n – k + 1} вариантов. Построим диаграмму:

Если k меняется от 1 до n + 1, величина n – k + 1 меняется от 0 до n. Таким образом, количество вариантов заполнения нашей рамки с использованием хотя бы одной костяшки домино равно

F_n + F_{n – 1} + … + F₁ + F₀.

Если поставить слагаемые в обратном порядке, мы получим левую часть выражения (*). Таким образом, мы нашли второй ответ на поставленный вопрос:

F₀ + F₁ + … + F_n.

Итак, у нас есть два ответа на вопрос. Величины, полученные с помощью двух выведенных нами формул, совпадают, и тождество (*) доказано.

Соотношение чисел Фибоначчи и золотое сечение

Сложение двух следующих друг за другом чисел Фибоначчи дает очередное число Фибоначчи. В этом разделе мы затронем вопрос поинтереснее: что будет, если мы поделим число Фибоначчи на предшествующее ему в ряду? Посчитаем соотношение Для возрастающих значений k. В таблице вы можете видеть соотношения от

Чем больше становятся числа Фибоначчи, тем ближе соотношение к константе, примерно равной 1,61803.

Это число – вы будете удивлены – достаточно известное, и если вы введете его в поисковую систему, вывалится уйма страниц о золотом сечении. Что это такое?

Соотношение соседних чисел Фибоначчи не одинаково. Однако оно почти одинаково, если числа достаточно велики. Давайте найдем формулу для числа 1,61803 и для этого на время будем считать, что все соотношения одинаковы. Введем обозначение x:

Это значит, что F_{k + 1} = xF_k, F_{k + 2} = xF_{k + 1} и т. д. Можно переформулировать:

F_{k+ 2} = xF_{k + 1} = x²F_k.

Но мы же знаем, что F_{k + 2} = F_{k + 1} + F_k. Таким образом,

x²F_k = xF_k + F_k.

Если мы поделим обе части на F_k и перегруппируем слагаемые, то получим квадратное уравнение:

x² – x – 1 = 0.

Оно имеет два решения:

Соотношение должно быть положительным. И вот мы получили знакомое нам число. Обычно для обозначения золотого сечения используют греческую букву ϕ (фи):

Мы уже приметили, что соотношение соседних чисел Фибоначчи приближается (стремится) к ϕ. Это замечательно. Это дает нам еще один способ вычислять приблизительные значения чисел Фибоначчи.

Последовательность чисел Фибоначчи – это ряд F₀, F₁, F₂, F₃, F₄, F_5… Если все соотношения будут одинаковы, мы получим формулу:

F_n = cϕⁿ.

Здесь с – еще одна константа. Сравним округленные значения F_n и ϕⁿ для разных n:

Для больших значений n соотношение Это число равно в точности Другими словами,

Насколько хороша эта формула? Настало время новых подсчетов!

Обратите внимание: если округлить до ближайшего целого числа, мы получим в точности F_n.

Если вы не хотите утруждать себя округлениями до целого числа, то формула, названная в честь Жака Бине[100], даст вам точное значение:

Глава 10Факториал!

Книги на полке

Сколькими способами можно расставить ваши книги на полке? Разумеется, это зависит от того, сколько у вас книг. Начнем с простейшего примера. Допустим, ваша библиотека насчитывает всего три книги с незамысловатыми названиями A, B и C.

Вначале решим, какую книгу поставить с левого края. Пусть это будет A. В таком случае остается всего два варианта расположения книг на полке: ABC и ACB. То есть, когда A стоит слева, существует две комбинации.

Если поставить на левую позицию книгу B, тогда снова возможны два варианта: BAC и BCA. Если слева стоит книга C, появляются еще две комбинации: CAB и CBA.

В общей сложности есть шесть вариантов расстановки книг:

ABC, ACB, BAC, BCA, CAB, CBA.