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

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



Смотрите также:
ЧИСЛА СТИРЛИНГА


Число Стирлинга второго рода 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

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


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

#include

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

#include

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");

}

}


^ ЧИСЛА БЕЛЛА


Число Белла 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  in). При этом количество разбиений n - элементного множества на k подмножеств равно числу Стирлинга 2 рода S(n, k). Откуда получаем формулу:

Bn =


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 разных таких конструкций.



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



Доказательство. Рассмотрим разбиение n +1 элемента в зависимости от величины блока, в котором находится (n + 1) - ый элемнент. Пусть размер этого блока равен j (1  jn + 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.


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



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

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

1834933472251084800000, 6658606584104736522240000000, …

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




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




Пример 3. Следующая программа вычисляет числа Белла и выводит их на экран.


#include

#include

#define MAX 11


int n,k,i;

int bell[MAX], s[MAX][MAX];


void Strirling(void)

{

memset(s,0,sizeof(s));

s[0][0] = 1;

for(n = 1; n < MAX; n++)

for(k = 0; k <= n; k++)

s[n][k] = s[n-1][k-1] + k * s[n-1][k];

}


void Bell(void)

{

Strirling();

memset(bell,0,sizeof(bell));

bell[0] = 1;

for(n = 1; n < MAX; n++)

for(k = 1; k <= n; k++)

bell[n] += s[n][k];

}


void main(void)

{

Bell();

for(i = 0; i < MAX; i++)

printf("%d ",bell[i]);

printf("\n");

}


Пример 4. Сколькими способами можно разложить n различимых объектов в одну или несколько неразличимых коробок?

При разложении n объектов одновременно задействовано может быть максимум n коробок, а каждому допустимому разложению соответствует некоторое разбиение множества из n объектов. Количество таких разбиений равно числу Белла Bn.


^ ЧИСЛА ЭЙЛЕРА


Числом Эйлера первого рода E(n, k) называется количество перестановок порядка n с k подъемами. То есть таких перестановок X = (x1, x2, …, xn), что существует ровно k индексов j, для которых xj < xj+1.


Для заданного n существует единственная перестановка без подъемов (n, n – 1, …, 2, 1). Также существует единственная перестановка, имеющая n – 1 подъем (1, 2, …, n – 1, n). Значит

E(n, 0) = E(n, n – 1) = 1

Зеркальным отражением перестановки с k подъемами является перестановка с nk – 1 подъемом. Таким образом

E(n, k) = E(n, nk – 1)



Скачать 165,73 Kb.
Дата конвертации06.12.2013
Размер165,73 Kb.
ТипДокументы
Разместите кнопку на своём сайте или блоге:
rud.exdat.com


База данных защищена авторским правом ©exdat 2000-2012
При копировании материала укажите ссылку
обратиться к администрации
Документы