Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Ln - число подмножеств разбиения мощности n



Эти числа удовлетворяют тождеству

1 l1 + 2 l2 +.... + n ln = n.

Теорема 3.

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

Процесс построения всех разбиений множества M на k непустых частей, характеризуемых набором чисел (l1, l2,...., ln), l1 + l2 +.... + ln = k, можно представить следующим образом.

Возьмем п упорядоченных ячеек и разобьем их на k; подмножеств, характеризуемых данным набором чисел (l1, l2,...., ln). Эти подмножества занумеруем числами 0, 1,..., k - 1. Разместим в этих ячейках элементы а1,..., aп. Очевидно, что разбиение ячеек на подмножества структуры (l1, l2,...., ln) порождает разбиение элементов а1,..., aп на подмножества такой же структуры. Последнее задается набором 1, б2,..., бп), где бi — номер подмножества разбиения ячеек, которому принадлежит элемент бi Производя различные размещения элементов а1,..., aп, по ячейкам, получим все разбиения множества M на k непустых частей данной структуры (l1, l2,...., ln). При этом два размещения определяют одно и то же разбиение множества M тогда и только тогда, когда для соответствующих им наборов 1, б2,..., бп) и 1, б2,..., бп) выполнено условие

Если сравнить соответствующие слагаемые в (15) и (18), то можно увидеть, что они выражают одно и то же число. Отсюда получаем еще одно явное выражение для S(n,r) (n, r>0)

Эта формула не пригодна для практических вычислений S(n,k), так как она предполагает знание всех решений уравнения (14) или (17).

Эффективный способ вычисления чисел Стирлинга 2-го рода и изучение их свойств связано с установлением ряда реккурентных соотношений для S(n,k).

Теорема. S(m,n) = S(m-1,n-1) + n S(m-1,n)

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

Числа Стирлинга 2-го рода (Джеймс Стирлинг (1699-1770))

Комбинаторные числа S(n,k) называются числа Стирлинга 2-го рода, а комбинаторные числа B(n) - числами Белла. Эти числа связаны соотношением:

Число разбиений m -элементного множества на n блоков называется числом Стирлинга второго рода и обозначаются S(m,n)

Найдем явную формулу для определения чисел Стирлинга 2-го рода S(n,k).

По определению

S(m,0) = 0 при m > 0

S(m, m) = 1

S(0, 0) = 1

S(m,n) = 0 при n > m





Дата публикования: 2014-11-04; Прочитано: 495 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...