Задача о беспорядках и встречах. Числа Стирлинга 1го и 2го рода
Реферат, 10 Июля 2013, автор: пользователь скрыл имя
Краткое описание
Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом.
Случай двух множеств
Например, в случае двух множеств формула включений-исключений имеет вид:
В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.
Содержание
Формула включений и исключений. Задача о беспорядках………………..3
Формулировка…………………………………………………....4
Доказательство…………..……………………………………….5
Применение. Постановка задачи………………………………..8
Числа Стирлинга.……………………………………………..........................15
Второго рода……………………………………………………..15
Первого рода……………………………………………………..19
Список литературы…………………………
Вложенные файлы: 1 файл
дискретка.docx
— 984.86 Кб (Скачать файл)
Треугольник
Стирлинга для числа подмножеств
Выведем рекуррентное соотношение, при помощи которого можно будет вычислить значения . Если задано множество из n > 0 объектов, которое должно быть разбито на k непустых частей, то мы либо помещаем последний объект в отдельный класс, а оставшиеся n – 1 объект разбиваем на k – 1 часть способами, либо помещаем его в любую из k частей, на которые разбиты n – 1 объект. В последнем случае имеется k * возможных вариантов, поскольку каждый из способов распределения первых n – 1 объектов по k непустым частям дает k подмножеств, с которыми можно объединить n -ый объект. Имеем рекуррентную формулу:
= + k * , n > 0
Пример 1. Рассмотрим программу, вычисляющую числа Стирлинга второго рода, причем значение S(n, k) будет вычисляться в ячейке s[n][k]. Выведем полученные значения в виде форматированной таблицы на экран.
#include <stdio.h>
#include <memory.h>
int n, k, s[10][10];
void main(void)
{
memset(s,0,sizeof(s));
s[0][0] = 1;
for(n = 1; n < 10; n++)
for(k = 1; k <= n; k++)
s[n][k] = s[n-1][k-1] + k * s[n-1][k];
for(n = 0; n < 10; n++)
{
for(k = 0; k <= n; k++)
printf("%4d ",s[n][k]);
printf("\n");
}
Числа Стирлинга первого рода
Число Стирлинга первого рода s(n, k) равно количеству способов представления 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]
Поэтому = 11.
Единичный цикл (цикл, состоящий из одного элемента) – это то же самое, что и единичное множество. 2-цикл подобен 2-множеству, поскольку [A, B] = [B, A] как и {A, B} = {B, A}. Однако уже существует два различных 3-цикла: [A, B, C] и [A, C, B]. Из любого n-элементного множества могут быть составлены n! / n = (n – 1)! циклов, если n > 0 (всего имеется n! перестановок, а каждый цикл соответствует сразу n из них, так как отсчет цикла может быть начат с любого из его элементов). Поэтому
= (n – 1)!.
Если все циклы являются единичными или двойными, то = . Например,
= = 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]. Таким образом, рекуррентность имеет вид:
= + (n – 1) * , n > 0
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 |
Треугольник Стирлинга для числа циклов
Теорема. Имеет место соотношение:
Доказательство. обозначает число перестановок n объектов, которое содержит ровно k циклов. Если просуммировать по всем k, то должно получиться общее число перестановок, равное n!.
Пример 2. Рассмотрим программу, вычисляющую числа Стирлинга первого рода. Значение s(n, k) вычисляется в ячейке s[n][k]. Выводим полученные значения в виде форматированной таблицы на экран.
#include <stdio.h>
#include <memory.h>
int n, k, s[10][10];
void main(void)
{
memset(s,0,sizeof(s));
s[0][0] = 1;
for(n = 1; n < 10; n++)
for(k = 1; k <= n; k++)
s[n][k] = s[n-1][k-1] + (n-1) * s[n-1][k];
for(n = 0; n < 10; n++)
{
for(k = 0; k <= n; k++)
printf("%6d ",s[n][k]);
printf("\n");
}
}
Список литературы
- http://www.simvol.biz/
uploadfiles/File/sostav/books/ Diskret_mat2.pdf - http://physcontrol.phys.msu.
ru/materials/DiscretAnaliz/DA_ Combinator.pdf - http://www.studfiles.ru/dir/
cat14/subj266/file843/ view1739/page4.html