Замечательные комбинаторные числа

Изучая последовательности А-, В- и (А+В)-чисел, можно установить следующую закономерность в этих числовых последовательностях: каждый член последовательности равен сумме двух предыдущих. Если теперь обозначить n-й член последовательности, удовлетворяющей этому правилу через F_n, тогда указанное выше общее правило может быть записано в виде следующей математической формулы:

 = + .

2. Связь с  золотым сечением.

Чтобы связать числа Фибоначчи  с золотым сечением найдём явную  формулу для вычисления чисел  Фибоначчи. Для этого выведем  формулу производящей функции:

 

Умножим обе части равенства  на . Получим

=

=

Или

,

Откуда

 

Разложим дробь в виде суммы двух элементарных дробей:

 

где

 

 

 

Из этого  разложения получаем:

 

Таким образом, получим явную формулу для вычисления чисел Фибоначчи:

 

Теперь свяжем числа Фибоначчи  с золотым сечением. С древних времен известна задача архитектурного происхождения о нахождении золотого сечения — такого вещественного числа a, чтобы при приклеивании к кирпичу с отношением сторон, равным a, квадратного кирпича мы снова получали кирпич с отношением сторон, равным a.(рис.12)

 

  
               

 

                                                          1

                                                                              а

рис.12

Искомое число будет решение  квадратного уравнения  . Корни этого уравнения нам хорошо известны в связи с изучением чисел Фибоначчи. Они равны

 

Единственным решением этой задачи является число

 

так как второе решение отрицательное.

Рассмотрим последовательные отношения соседних чисел Фибоначчи:

 

Нетрудно заметить, что возрастание этих чисел чередуется с убыванием:

 

Из явной формулы  для чисел Фибоначчи видно, что они являются суммами двух геометрических прогрессий со знаменателями

 

При этом знаменатель первой геометрической прогрессии по модулю больше единицы, значит, прогрессия стремится  к бесконечности. Знаменатель второй прогрессии, напротив, убывает, следовательно, прогрессия стремится к нулю. Поэтому, начиная с некоторого момента, последовательность отношений соседних чисел Фибоначчи ведет себя как эта прогрессия, следовательно, искомый предел соотношений равен золотому сечению

3. Свойства  чисел Фибоначчи.

Одним из самых первых фактов о числах Фибоначчи, обнаруженным в 1680 г. французским астрономом Жан-Домиником  Кассини, является соотношение

 

Так, при n=6 соотношение Кассини справедливо утверждает, что . Соотношение Кассини лежит в основе геометрического парадокса, который был одной из излюбленных головоломок Льюиса Кэролла. Суть его в том, чтобы взять шахматную доску и разрезать её на 4 части, как показано ниже, а затем составить из этих частей прямоугольник:

Первоначальные 8×8=64 клетки переставлены так, что получилось 13×5=65 клеток. Аналогичная конструкция расчленяет любой квадрат на 4 части с размерами сторон , , , клеток. В результате получается прямоугольник, и в соответствие с соотношением Кассини, одна клетка либо утрачивается, либо прибавляется – в зависимости от того, чётно или нечётно n.

Одно из наиболее важных качеств  чисел Фибоначчи – это особый способ представления целых чисел  с их использованием. Будем писать

  равносильно

Тогда каждое целое положительное число имеет  представление вида

, . Это теорема Цеккендорфа. К примеру, представление одного миллиона выглядит так:

.

Подобное представление  всегда может быть найдено с помощью  «жадного» подхода: в качестве выбирается наибольшее число Фибоначчи ≤ n, затем в качестве выбирается наибольшее число ≤ , и т.д.

Любая система однозначного представления чисел является системой счисления – следовательно, теорема  Цеккендорфа приводит к фибоначчиевой  системе счисления. Всякое целое  неотрицательное число можно  представить в виде последовательности нулей и единиц, записав

 
 или 

Эта система счисления  отчасти напоминает двоичное представление, за исключением того, что в ней  никогда не встречается две единицы  подряд

               

          

    

    

         

 

   

   

 

 

5. БИБЛИОГРАФИЯ

1. Андерсон, Дж.: Дискретная математика и комбинаторика: Пер. с  англ. – М.: Издательский дом «Вильямс», 2004, – 960с.

ISBN: 5-8459-0498-6.

2. Аляев, Ю.А.; Тюрин, С.Ф.: Дискретная математика и математическая логика. Москва: Издательство «Финансы и статистика», 2006, - 368с.

 ISBN: 5-279-03045-7.

3. Плотников, А.Д.: Дискретная математика. Москва: издательство «Новое издание», 2005, - 288с.

ISBN: 5-94735-073-4.

4. Грэхем, Р.; Кнут, Д; Паташник, О.: Конкретная математика: Пер. с англ. – М.: Издательство «Мир», 1998, - 703с.

ISBN: 5-03-001793-3

5. Спивак, А. Числа Каталана/А.Спивак//Квант. – 2004. – №3. – с.2-10.
6. Ландо, С.: Введение в дискретную математику: Издательство Независимого Московского университета, 2012, -568с.

 

7. Стенли, Р.: Перечислительная комбинаторика: Пер. с англ. – М.: Издательский дом  «Мир», 1990, - 440с.  ISBN 5-03-001348-2