Задача о беспорядках и встречах. Числа Стирлинга 1го и 2го рода

Федеральное агентство по образованию  Российской Федерации

Государственное образование учреждение высшего  профессионального образования

«Южно-Уральский государственный  университет»

Факультет «Экономика и Управление»

Кафедра «Информатика»

 

 

 

 

 

Реферат по дисциплине

«Дискретная математика»

на тему:

«Задача о беспорядках и встречах. Числа Стирлинга 1го и 2го рода»

 

 

 

 

 

 

      

 

        Руководитель

             ___________________ И.В. Елюхина

      ____________________2012 г.

 

         Автор работы

         Студент группы ЭиУ-268

         ____________________Е.С. Манеева

         ______________________2013 г.

 

         Реферат защищен с оценкой

         ________________________

         ______________________2013 г.

 

 

 

 

 

 

 

Челябинск, 2013

 

 

Оглавление

 

 

1. Формула включений и исключений. Задача о беспорядках………………..3

1. Формулировка…………………………………………………....4
2. Доказательство…………..……………………………………….5
3. Применение. Постановка задачи………………………………..8

2. Числа Стирлинга.……………………………………………..........................15

1. Второго рода……………………………………………………..15
2. Первого рода……………………………………………………..19

3. Список литературы……………………………………………………………22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Формула включений и  исключений. Задача о беспорядках.

 

Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом.

Случай  двух множеств

Например, в случае двух множеств   формула включений-исключений имеет вид:

В сумме   элементы пересечения   учтены дважды, и чтобы компенсировать это мы вычитаем   из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

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

Впервые формулу включений-исключений опубликовал португальский математик Даниэль да Сильва (англ.) в 1854 году. Но еще в 1713 году Николай Бернулли (англ.) использовал этот метод для решения задачи Монмора (англ.), известной как задача о встречах (фр. Le problème des rencontres), частным случаем которой является задача о беспорядках. Также формулу включений-исключений связывают с именами французского математика Абрахама де Муавра и английского математика Джозефа Сильвестра. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре.

 

 

Формулировка

Формулу включений-исключений можно сформулировать в разных формах.

1. В терминах множеств

Пусть   — конечные множества. Формула включений-исключений утверждает:

При   получаем формулу для двух множеств, приведенную выше.

2. В терминах свойств

Принцип включений-исключений часто приводят в следующей альтернативной формулировке [4]. Пусть дано конечное множество  , состоящее из   элементов, и пусть имеется набор свойств  . Каждый элемент множества   может обладать или не обладать любым из этих свойств. Обозначим через   количество элементов, обладающих свойствами   (и, может быть, некоторыми другими). Также через   обозначим количество элементов, не обладающих ни одним из свойств  . Тогда имеет место формула:

Формулировка принципа включений-исключений в терминах множеств эквивалентна формулировке в терминах свойств. Действительно, если множества   являются подмножествами некоторого множества  , то в силу правил де Моргана   (черта над множеством — дополнение в множестве  ), и формулу включений-исключений можно переписать так:

Если теперь вместо «элемент   принадлежит множеству  » говорить «элемент   обладает свойством  », то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

Обозначим через   количество элементов, обладающих в точности   свойствами из набора  .Тогда формулу включений-исключений можно переписать в следующей замкнутой форме (англ.)

 

 

 

Доказательство

Существует несколько доказательств формулы включений-исключений.

1. По индукции

Формулу включений-исключений можно доказать по индукции.

При   формула включений-исключений тривиальна:

Пусть формула верна для  , докажем ее для  .

Пусть каждый элемент множества   может обладать или не обладать любым из свойств  . Применим формулу включений-исключений для свойств  :

Теперь применим формулу для свойств   к множеству   объектов, для которых выполнено свойство  :

Наконец, применим формулу для одного свойства   к совокупности  , объектов, которые не обладают свойствами  :

Комбинируя выписанные три формулы, получим формулу включений-исключений для   свойств  . Что и требовалось доказать.

2. Комбинаторное доказательство

Рассмотрим произвольный элемент   и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений.

Если элемент   не обладает ни одним из свойств  , то в правой части формулы он учитывается ровно 1 раз (в члене  ).

Пусть элемент   обладает в точности   свойствами, скажем  . Он дает по 1 в тех слагаемых суммы  , для которых   есть подмножество  , и 0 для остальных. Число таких подмножеств по определению есть число сочетаний  . Следовательно, вклад элемента   в правую часть равен

При   числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств  , то есть  . Что и требовалось доказать.

 

 

Применение

Задача о беспорядках

Классический  пример использования формулы включений-исключений — задача о беспорядках. 

В комбинаторике беспорядком называется перестановка без неподвижных точек.

 

 

Постановка задачи

 

 

Пусть имеется конечное упорядоченное множество элементов {1,…, n}. Из этих элементов могут быть образованы перестановки a1,…, an (aiÎ{1,…,n}). Число всех возможных перестановок – n!. Среди этих n! перестановок есть такие, что ни один элемент не стоит на своём месте (ai¹i, i= ). Иначе говоря, элемент номер 1 не стоит на 1-ом месте, элемент номер 2 не стоит на 2-м месте, и т.д., элемент номер n не стоит на n-м месте. Такие перестановки называются беспорядками. 
 
Число беспорядков из n элементов обозначается Dn (ясно, что Dn<n< i="">!). 
 
 
Теорема. Число беспорядков из n элементов равно: 
 
. 
 
Обозначим через свойство pi – «i-й элемент стоит на i-м месте». Тогда по формуле . 
 
Общее число перестановок n элементов – n! Число перестановок, где i-й элемент стоит на i-м месте, равно (n-1)! (ставим i-й элемент на i-е место, а оставшиеся n-1 элементы переставляем (n-1)! способами). При этом сам i-й элемент можно выбрать   способами. Таким образом, число перестановок, где хотя бы по одному элементу стоит на своём месте, равно  . 
 
Число перестановок, где i-й элемент стоит на i-м месте, а j-й на j-м (i¹j), равно (n-2)!, при этом i-й и j-й элементы можно выбрать   способами. Таким образом, число перестановок, где хотя бы два элемента стоят на своих местах –  . 
 
Аналогично, число перестановок, где на своих местах стоят хотя бы три элемента –  . Число перестановок, где на своих местах стоят хотя бы r элементов –  . Число перестановок, где все элементы стоят на своих местах  . Подставляем в формулу решета:   # 
 
 
Следствие 1. 
 
Так как  , 
 
то  . 
 
 
Следствие 2. 
 
Так как  , то  . 
 
 

 

Следствие 3. 
 
Рекуррентная формула для числа беспорядков:  . 
 
#   
 
 
 
 # 
 
Следствие 4.   
 
По рекуррентной формуле из следствия 3 получаем   или  . При n=1 получаем  . По формуле из следствия 1 получаем  . Следовательно,  . # 
 
 
Следствие 5. 
 
Ещё одна рекуррентная формула для числа беспорядков:  . 
 
Рассмотрим n элементов x1, x2, … , xn. Переставим их так, чтобы получить беспорядок. Начнём с x1: возьмём x1 и подставим его на место i-го элемента (i¹1). Тогда xi можно поставить на либо на первое место, либо на какое-то другое, кроме i-го. Если x1 стоит на i-м месте, а xi – на 1-ом, то число таких беспорядков – Dn-2 (т.е. число беспорядков оставшихся n-2 элементов). Если x1 не стоит на первом месте, то такой беспорядок определяется условием: 
 
x2 не стоит на 2-м месте, 
 
x3 не стоит на 3-м месте, 
 
… 
 
xi-1 не стоит на (i-1)-м месте, 
 
xi не стоит на 1-м месте, 
 
xi+1 не стоит на (i+1)-м месте, 
 
… 
 
xn не стоит на n-м месте. 
 
Всего здесь n-1 элемент, то есть число таких беспорядков – Dn-1. 
 
Итак, если x1 стоит на i-ом месте, то число таких беспорядков Dn-1+Dn-2. Но x1 можно поставить на любое из (n-1) мест (кроме 1-го). Для каждой установки x1 справедливы приведённые выше рассуждения. 
 
Таким образом, общее число беспорядков – (n-1)(Dn-1+Dn-2). # 
 
 
Для проверки полученной формулы вычислим количество беспорядков для некоторых значений n по рекуррентной и прямой формулам. По следствию 4,D0=1, D1=0.

Рекуррентная формула	Нерекуррентная формула

 

 
 
Для строгого доказательства правильности рекуррентной формулы, проверим ее в общем виде. 
 
. 
 
Из следствия 3  , следовательно,  . Тогда 
 
. Подставим этот результат в рекуррентную формулу: 
 
. Получили формулу из следствия 3. 
 
 
Обозначим через D_n,r число перестановок, в которых на своих местах остаются r элементов, а остальные (n-r) образуют беспорядок. Ясно, что D_n,n=1 (все элементы на своих местах), и D_n,0=D_n (ни одного элемента нет на своём месте. 
 
Теорема.  . 
 
 r элементов, стоящих на своём месте, можно выбрать из n элементов   способами. Для каждой такой выборки остальные (n-r) элементов образуют беспорядки, число которых D_n-r. Следовательно, всего таких перестановок  . 
 
С другой стороны, (n-r) элементов, образующих беспорядки, можно выбрать   способами. Следовательно,  . В силу симметричности биномиальных коэффициентов  , обе формулы дают один и тот же результат. 
 
 # 
 
Пример. Выстраиваем 5 человек в определённом порядке, после чего 3 из них переставляем так, чтобы они не стояли на своих местах. Сколько таких перестановок? 
 
Ответ: если трое не стоят на своих местах, то оставшиеся двое стоят на своих местах, т.е. 
 
. 
 
 
Следствие.  . 
 
# Из n элементов можно образовать n! перестановок без повторений. 
 
Среди них будет D_n,0 таких, где ни один элемент не стоит на своём месте; 
 
D_n,1 таких, где по одному элементу стоит на своём месте; 
 
D_n,2 таких, где по паре элементов стоит на своих местах;  
 
и т.д.; 
 
D_n,n=1 таких, где все элементы стоят на своих местах. 
 
Следовательно, общее число перестановок (n!) равно сумме этих чисел.

 

Числа Стирлинга

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

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

{1, 2, 3} È {4}, {1, 2, 4} È {3}, {1, 3, 4} È {2}, {2, 3, 4} È {1},

{1, 2} È {3, 4}, {1, 3} È {2, 4}, {1, 4} È {2, 3}

Поэтому = 7.

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

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

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

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

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