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

МИНИСТЕСТЕРСТВО

 

 

Оглавление

ВВЕДЕНИЕ 3

1 ЧИСЛА КАТАЛАНА 4

1.1 Разрезание треугольников. 4

1.2 Вычисление произведений. 6

1.3 Расстановка скобок. 7

1.4 Треугольник Каталана. 7

2 ЧИСЛА СТИРЛИНГА 10

2.1 Числа Стирлинга второго рода. 10

2.2 Числа Стирлинга первого рода. 11

3 ЧИСЛА БЕЛЛА 13

3.1 Определение 13

3.2 Свойства 14

4 ЧИСЛА ФИБОНАЧЧИ 15

4.1 Задача о кроликах. 15

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

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

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

 

ВВЕДЕНИЕ

Некоторые последовательности чисел возникают столь часто, что их узнают с первого взгляда  и наделяют собственными названиями. И возникают эти числа в  самых разнообразных местах: в  окружающей нас природе, в бытовой  жизни или даже в искусстве. Неудивительно, что эти числа издавна волнуют умы великих учёных, их исследуют, находят различные закономерности, многие из которых уже открыты, но думается мне, что много можно открыть.

В данной работе рассмотрены  наиболее известные числовые последовательности, которые неразрывно связаны с комбинаторикой. Детальным образом разобраны задачи, которые привели к обнаружение последовательностей этих чисел.Поговорим о числах Каталана, которые встречаются в самых различных областях и имеют более 30 определений. Исследуем числа Стирлинга и Бэлла, которые образуют треугольники коэффициентов, подобно биноминальным коэффициентам треугольника Паскаля. И в заключении повосторгаемся очаровательными числами Фибоначчи и некоторыми их важными обобщениями.

 

 

  1. ЧИСЛА КАТАЛАНА

Эжен Шарль Каталан(1814 – 1894) – бельгийский математик.

Первые несколько чисел  Каталана:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, ...

Формула для вычисления n-го числа Каталана:

 ==

Существует несколько  десятков способов определения чисел  Каталана. Рассмотрим несколько классических способов.

    1. Разрезание  треугольников.

Задача. Сколькими способами можно выпуклый n-угольник разрезать на треугольники диагоналями, не пересекающимися внутри этого n-угольника. Ответ для n=3 тривиален: никаких диагоналей проводить не надо (рис. 1). Для n=4 можно провести любую из двух диагоналей, так что способов 2 (рис. 2).


 

 

        рис.1                                                                           рис. 2                                                                                   

Для n=5 все 5 способов тоже, по сути, одинаковы: из некоторой вершины выходят две диагонали (рис. 3).


 


 

 

 

 

 

 

 

рис. 3

 

 

 

При n=6 получаем первый нетривиальный ответ: 14 способов (рис. 4).

                                             рис. 4

Для n=7 все способы рисовать не будем, можно выделить одну из сторон и расклассифицировать разрезания  в зависимости от  того, какой треугольник этой стороне примыкает (рис. 5).

                                               рис. 5

Имеем 5 различных  случаев. В первом и последнем из них количество разбиений равно 14, ибо после отрезания треугольника остается шестиугольник. Во втором и четвертом случаях при вырезании треугольника семиугольник распадается на треугольник и пятиугольник. Треугольник резать не надо, а пятиугольник, как мы уже знаем, дает 5 способов. В третьем случае от семиугольника остаются два четырехугольника. Поскольку каждый из них можно разбить двумя способами, получаем 2*2 = 4 варианта. Итак, семиугольник можно разбить всего

14 +5 + 2*2 + 5 + 14 = 42

способами.

 

Рассматривая восьмиугольник, аналогично получаем

42 + 14 + 2*5 + 5*2 + 14 + 42 = 132

способа. Для  девятиугольника имеем

132 + 42 + 2*14 + 5*5 + 14*2 + 42 + 132 = 429

способов, а  для десятиугольника – 

429 + 132 + 2*42 + 5*14 + 14*5 + 42*2 + 132 + 429 = 1430

способов.

Такие вычисления можно проводить  и дальше , и в итоге мы получим остальные числа Каталана.

    1. Вычисление  произведений.

Рассмотрим другую - алгебраическую - задачу. Произведение аbс можно понимать двояко: (ab)c и а(bс). Произведение abcd можно понимать пятью способами: ((ab)c)d, (a(bc))d, a((bc)d), a(b(cd)) и (ab)(cd). Произведение abcde - четырнадцатью способами. Чтобы убедиться в этом, не обязательно их все выписывать. Достаточно заметить, что есть 5 способов вида a(bcde), 2 способа вида (ab)(cde), 2 способа вида (abc)(de) и 5 способов вида (abcd)e.

По одному из определений, число Каталана - это количество способов расставить скобки в произведение n множителей. Получается, что =  = 1, = 2,    = 5, = 14. Выведем для последовательности Каталана рекуррентную формулу. Для этого рассмотрим умножение, которое будет выполнено в последнюю очередь. Произведение ... получается,  в конечном счёте, как произведение некоторого произведения первых нескольких символов на некоторое произведение остальных:

... = (...)(...).

Первые r символов могут быть скомбинированы способами, последние n – r символом способами. Таким образом,

= ++…+. 

Это и есть рекуррентная формула для последовательности чисел Каталана. Например, чтобы  получить , достаточно выписать одно за одним первые 9 чисел Каталана, а под ними – те же числа, но в обратном порядке:

1 1 2 5 14 42 132 429 1430

1430 429 132 42 14 5 2 1 1

Умножив каждое верхнее число  на соответствующее нижнее и сложив, получим

= 4862.

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

    1. Расстановка скобок.

Рассмотрим какое-нибудь арифметическое выражение и сотрем все, кроме скобок. Получим некоторую  систему открывающих и закрывающих  скобок. Во-первых, открывающих скобок ровно столько же, сколько и  закрывающих. Во-вторых, ни в каком  начальном отрезке количество закрывающих  скобок не может оказаться больше количества открывающих скобок. Например, расстановки ) ( и ((( ))))( неправильные. Эти два условия не только необходимы, но и достаточны.

Рассмотрим несколько  примеров. Одна пара скобок может выглядеть  единственным способом: ( ). Две пары - двумя способами: ( )( ) или (( )). Три пары - пятью способами: ( )(  )(), ( )(( )), (( ))( ), (( )( )) или ((( ))). Четыре пары, как нетрудно проверить,- четырнадцатью способами. Что понять, сколькими способами могут выглядеть правильно расставленные 5 пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре пары тогда разделятся на две группы: расположенные внутри рассмотренной пары и расположенные справа от нее. (Разумеется, любая из этих групп может состоять из 0 скобок.) Способов, когда все четыре пары внутри или все четыре справа, - по 14 в каждом случае. Когда три пары внутри, а одна справа – 5 способов. Столько же – когда одна внутри, а три справа. Наконец, когда две пары внутри, а две справа, имеем 2*2 = 4 способа. Итого,

14 + 5 + 2*2 + 5 + 14 = 42

Очевидно, что для случаев 6 пар скобок и больше, получим  такую же последовательность чисел  как и в задаче о разрезаниях  на треугольники, то есть числа Каталана.

    1. Треугольник Каталана.

Известный треугольник Паскаля (рис.6) получается, если начать с верхней  единицы и затем действовать  по правилу «каждое очередное  число равно сумме чисел, расположенных  над ним «справа и слева» (а  на краях — единицы). Он обладает многими интересными свойствами. Но сейчас речь не о нем. Давайте  проведем вертикальную черту, левее  которой заходить нельзя, и будем  выписывать числа так, словно мы составляем треугольник Паскаля (рис. 7). На самой  левой вертикали - числа Каталана!

                                   1


        1. 1

                    1              2              1

             1              3              3           1

      1            4               6             4          1

1          5              10           10           5         1

рис. 6

 

 

1


      1

1           1

       2          1

2            3         1

        5           4        1

5             9          5         1

        14        14         6         1

14          28         20        7         1

        42         48        27       8         1

42           90        75        35       9         1

        132      165      110      44      10        1

132        297      275      154     54       11       1

                   429       572      429      208    65        12      1

                                 рис. 7

Почему же на левой вертикали возникают числа Каталана? Другими словами, как связать треугольник Каталана с какой-нибудь из ранее рассмотренных задач, например, с задачей о правильных расстановках скобок?

Открывающей скобке сопоставим движение вниз-вправо, а закрывающей – движение вниз-влево. Путь возвращается к исходной вертикали, если количества открывающих и закрывающих скобок уравнялись. Путь пересекает эту вертикаль, как только количество закрывающих скобок превышает количество открывающих. Правильные расстановки скобок взаимно однозначно соответствуют правильным - т.е. возвращающимся к вертикальной черте и не пересекающим ее - путям. На рисунках 8, 9 и 10 проиллюстрированы случаи 1, 2 и 3 пар скобок соответственно.



 

 

 

       ( )      

рис. 8

 

 

                             (( ))                                                      ( )( )

                                                  рис. 9


 

     

 

 

   ((( )))                      (( )( )) ( )(( )) ( )( )( ) (( ))( )

рис.10

Итак, любой правильной расстановке  скобок соответствует путь в треугольнике Каталана;   любое  число треугольника Каталана равно количеству путей, которыми можно прийти в соответствующую  точку вершины.

В завершении, перечислю задачи, которые приводят к определению  чисел Каталана. Итак, n-ое число Каталана равно количеству:

    • способов расположить несколько одинаковых бревен, когда в нижнем ряду их n – 1;
    • путей Дика, т.е. путей, начинающихся в начале координат, не спускающихся ниже оси абсцисс, где каждый шаг - перемещение на единицу вправо и на единицу вверх или вниз, оканчивающихся на оси абсцисс, обладающих n – 1 точками локального минимума (другими словами, n – 1 пиками) и не имеющих трех подряд идущих шагов в одном и том же направлении;
    • путей Дика, оканчивающихся в точке (2n; 0), ни один из пиков (т.е. локальных максимумов) которых не расположен на высоте 2;
    • горизонтальных полимино ширины n;
    • симметричных полимино периметра 4(2n - 1);
    • последовательностей ≤≤...≤  натуральных чисел,   удовлетворяющих неравенствам ≤ k , где 1≤ k < n , а именно, при n = 4 это последовательности 1 ≤ 1 ≤ 1, 1 ≤ 1 ≤ 2, 1 ≤ 1 ≤ 3, 1 ≤ 2 ≤ 2, 1 ≤ 2 ≤ 3;

 

 

 

 

 

 

 

 

 

 

  1. ЧИСЛА СТИРЛИНГА

Джеймс Стирлинг(1692 – 1770) – шотландский математик.

Эти числа выступают в  двух разновидностях, традиционно носящих  незатейливые названия « чисел Стирлинга  первого и второго рода». До сих  пор нет общепринятого обозначения  для этих чисел, некоторые обозначают так: {}- числа Стирлинга второго рода, а через [] – первого рода; S(n, k) – числа Стирлинга второго рода, s(n, k) – первого рода.

Числа Стирлинга второго  рода возникают намного чаще, чем  числа Стирлинга первого рода, так что вторые рассмотрим первыми (И сам Стирлинг в своей книге  в первую очередь рассмотрел этот род чисел). 

    1. Числа Стирлинга  второго рода.

Символом S(n, k) обозначается число способов разбиения множества из n элементов на k непустых подмножеств. S(n, k) читается так: k подмножеств из n. Так, существует 7 способов разбиения четырёхэлементного множества на две части:

{1, 2, 3}U{4}, {1, 2, 4}U{3}, {1, 3, 4}U{2}, {2, 3, 4}U{1},

{1, 2}U{3, 4}, {1, 3}U{2, 4}, {1, 4}U{2, 3},

следовательно, S(4, 2) = 7.

Рассмотрим  значения чисел Стирлинга для  малых значений k:

1. k = 0. Существует только один способ разбиения пустого множества на нулевое число непустых частей, поэтому S(0, 0) = 1. Для непустого множества нужна по крайней мере хотя бы одна часть, так что S(n, 0) = 0  при n > 0.

2. k = 1. Существует только один способ помещения n элементов в одно-единственное непустое множество, поэтому S(n, 1) = 1 при n > 0. Однако S(0, 1) = 0, так как 0-элементное множество пусто.

3. k = 2. Очевидно, что S(0, 2) = 0. Если же множество из n > 0 объектов разделено на две непустые части, то одна из этих частей содержит последний объект и некоторое подмножество из первых n — 1 объектов. Имеется способов выбора последнего подмножества, ибо каждый из первых n — 1 объектов либо входит, либо не входит в него. Но нам вовсе не нужно помещать в него все эти объекты, поскольку у нас должны остаться две непустые части. Поэтому вычтем 1:

S(n, 2) = – 1, целое n>0.

Выведем рекуррентное соотношение, при помощи которого можно  будет вычислить значения S(n, k). Если задано множество из n > 0 объектов, которое должно быть разбито на k непустых частей, то мы либо помещаем последний объект в отдельный класс, а оставшиеся n – 1 объект разбиваем на k – 1 часть S(n – 1, k – 1) способами, либо помещаем его в любую из k частей, на которые разбиты n – 1 объект. В последнем случае имеется     k*S(n - 1, k)  возможных вариантов, поскольку каждый из S(n – 1, k) способов распределения первых n – 1 объектов по k непустым частям дает k подмножеств, с которыми можно объединить n -ый объект. Имеем рекуррентную формулу:

S(n, k) = S(n – 1, k – 1) + k *S(n – 1, k), n > 0

Таблица 1. Треугольник Стирлинга для числа подмножеств

n

S(0,n)

S(1, n)

S(2, n)

S(3, n)

S(4, n)

S(5, n)

S(6, n)

S(7, n)

S(8,n)

S(9,n)

0

1

                  

1

0

1

                

2

0

1

1

              

3

0

1

3

1

            

4

0

1

7

6

1

          

5

0

1

15

25

10

1

        

6

0

1

31

90

65

15

1

      

7

0

1

63

301

350

140

21

1

    

8

0

1

127

966

1701

1050

266

28

1

  

9

0

1

255

3025

7770

6951

2646

462

36

1


    1. Числа Стирлинга  первого рода.

Символом s(n, k) обозначается количество способов представления n объектов в виде k циклов. s(n, k) читается так: k циклов из n.

Например, циклы  из 4 элементов [a, b, c, d],  [b, c, d, a], [c, d, a, b] и [d, a, b, c]  являются одинаковыми. Цикл можно прокручивать, так как его конец соединен с началом.

Существует 11 различных способов составить два цикла из четырех элементов:

[1, 2, 3][4], [1, 2, 4][3], [1, 3, 4][2], [2, 3, 4][1],

[1, 3, 2][4], [1, 4, 2][3], [1, 4, 3][2], [2, 4, 3][1],

[1, 2][3, 4], [1, 3][2, 4], [1, 4][2, 3].

Поэтому s(4, 2) = 11.

Единичный цикл (цикл, состоящий из одного элемента) – это то же самое, что и единичное  множество. 2-цикл подобен 2-множеству, поскольку [A, B] = [B, A] как и      {A, B} = {B, A}. Однако уже существует два различных 3-цикла: [A, B, C] и [A, C, B]. Из любого n-элементного множества могут быть составлены = (n – 1)! циклов, если n > 0 (всего имеется n! перестановок, а каждый цикл соответствует сразу n из них, так как отсчет цикла может быть начат с любого из его элементов). Поэтому

s(n, 1) = (n – 1)!

Если все  циклы являются единичными или двойными, то s(n, k) =  S(n, k). Например,

s(n, n) = S(n, n) = 1, 

s(n, n – 1 )= S(n, n – 1)=

Выведем рекуррентную формулу для вычисления чисел  Стирлинга первого рода. Каждое представление n объектов в виде k циклов либо помещает последний объект в отдельный цикл s(n – 1, k – 1) способами, либо вставляет этот объект в одно из s(n – 1, k) циклических представлений первых n – 1 объектов. В последнем случае существует n – 1 различных способов подобной вставки. Например, при вставке элемента d в цикл [a, b, c] можно получить только 3 разных цикла: [a, b, c, d], [a, b, d, c], [a, d, b, c]. Таким образом, рекуррентность имеет вид:

s(n, k)= s(n – 1, k – 1) + (n – 1) *s(n – 1, k), n > 0

Таблица 2. Треугольник Стирлинга для числа циклов

n

s(0, n)

s(1, n)

s(2, n)

s(3, n)

s(4, n)

s(5, n)

s(6, n)

s(7, n)

s(8,n)

s(9, n)

0

1

                  

1

0

1

                

2

0

1

1

              

3

0

2

3

1

            

4

0

6

11

6

1

          

5

0

24

50

35

10

1

        

6

0

120

274

225

85

15

1

      

7

0

720

1764

1624

735

175

21

1

    

8

0

5040

13068

13132

6769

1960

322

28

1

  

9

0

40320

109584

118124

67284

22449

4536

546

36

1


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. ЧИСЛА БЕЛЛА

Белл Эрик Темпл (1883 – 1960) – американский математик шотландского происхождения.

    1. Определение

Число Белла Bn равно количеству разбиений множества из n элементов на произвольное количество непустых подмножеств. Очевидно, что B0 = 1, так как существует только одно разбиение пустого множества. Например, B3 = 5, так как существует 5 возможных разбиений множества {a, b, c} из трех элементов:

{{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}},  {{a, b, c}}

Заметим, что n элементов можно разбить на i множеств (1 £ i £ n). При этом количество разбиений n - элементного множества на k подмножеств равно числу Стирлинга 2 рода S(n, k). Откуда получаем формулу:

Bn =

Таблица 3. Таблица чисел Белла

n

0

1

2

3

4

5

6

7

8

9

10

Bn

1

1

2

5

15

52

203

877

4140

21147

115975


 

Рассмотрим  следующие конструкции, в которых  точки обозначают одноэлементные множества, а сегменты объединяют элементы, принадлежащие  одному множеству. Из n элементов можно построить Bn разных таких конструкций (рис. 11).

рис.11

Теорема. Числа Белла удовлетворяют следующему рекуррентному соотношению:

 

Доказательство. Рассмотрим разбиение n +1 элемента в зависимости от величины блока, в котором находится (n + 1) - ый элемнент. Пусть размер этого блока равен j (1 £ j £ n + 1). Тогда существует способов выбрать в него кроме (n + 1) - ого еще j – 1 элемент. Остальные n + 1 – j элементов можно разбить Bn + 1 – j способами.Таким образом:

 

Например, B4 = B0 + B1 + B2 + B3 = 1 * 1 + 3 * 1 + 3 * 2 + 1* 5 = 15.

    1. Свойства

    • Числа Белла удовлетворяют следующему свойству:

 

Для значений n = 0, 1, 2, … получим следующие значения детерминанта:

1, 1, 2, 12, 288, 34560, 24883200, 125411328000, 5056584744960000,

1834933472251084800000, 6658606584104736522240000000, …

    • При разложении функции   в ряд Маклорена коэффициенты ряда образуют числа Белла:

 

    • Числа Bn могут быть построены при помощи треугольника Белла. Первая строка содержит 1. Каждая следующая строка начинается числом, стоящим в конце предыдущей строки. Каждое следующее число в строке равно сумме чиcел, стоящих слева и сверху от него. Числа Белла образуют последние числа в строках.

 

Таблица 4. Треугольник Белла

 

1

  
 

1

2

  
 

2

3

5

  
 

5

7

10

15

  
 

15

20

27

37

52

  
 

52

67

87

114

151

203

  
 

203

255

322

409

523

674

877

  

877

1080

1335

1657

2066

2589

3263

4140


  1. ЧИСЛА ФИБОНАЧЧИ

Леонардо Пизанский, больше известный под прозвищем Фибоначчи  (около 1170 – около 1250) – первый крупный математик средневековой Европы.

Таблица 5. Числа Фибоначчи

n

0

1

2

3

4

5

6

7

8

9

10

 

0

1

1

2

3

5

8

13

21

34

55


Числа Фибоначчи определяются рекуррентным соотношением:

 = 0,

 = 0,

 = +   для n>1

Бесхитростность этого правила, в котором каждое число зависит от двух предыдущих, служит объяснением того, почему числа  Фибоначчи встречаются в самых  разнообразных ситуациях.

    1. Задача о  кроликах.

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

Существо своей "задачи о размножении кроликов" Фибоначчи  сформулировал предельно просто: «Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов. Возникает вопрос: сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?»

рис.11

Для решения этой задачи, которая наглядно демонстрируется  с помощью рисунка, обозначим  через A пару зрелых кроликов, а через B - пару новорожденных кроликов. Тогда процесс "размножения" может быть описан с помощью двух "переходов", которые описывают ежемесячные превращения кроликов в процессе размножения:

А→АВ                  (1)

В→А                     (2) 

Заметим, что  переход (1) моделирует ежемесячное  превращение каждой зрелой пары кроликов А в две пары, а именно в ту же самую пару зрелых кроликов А и новорожденную пару кроликов В. Переход (2) моделирует процесс "созревания" кроликов, когда новорожденная пара кроликов В через месяц превращается в зрелую пару А. Тогда, если мы начнем в первом месяце со зрелой пары А, тогда процесс размножения кроликов может быть представлен с помощью таблицы.

Таблица 6. Процесс размножения кроликов

Дата

Пары кроликов

А

В

А + В

1-го января

А

1

0

1

1-го февраля

АВ

1

1

2

1-го марта

АВА

2

1

3

1-го апреля

АВААВ

3

2

5

1-го мая

АВААВАВА

5

3

8

1-го июня

АВААВАВААВААВ

8

5

13

Замечательные комбинаторные числа 📙 Курсовая → 🆔 80970

Замечательные комбинаторные числа 📙 Курсовая → 🆔 80970

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