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

 

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

Выведем рекуррентное соотношение, при помощи которого можно будет вычислить  значения . Если задано множество из 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");

  }

}

Список литературы

 

 

 

1. http://www.simvol.biz/uploadfiles/File/sostav/books/Diskret_mat2.pdf
2. http://physcontrol.phys.msu.ru/materials/DiscretAnaliz/DA_Combinator.pdf
3. http://www.studfiles.ru/dir/cat14/subj266/file843/view1739/page4.html