АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Разбиения

Читайте также:
  1. Матричный метод разбиения
  2. Процесс разбиения жесткого диска на логические
  3. Разбиения множеств.
  4. Разбиения чисел
  5. Способ разбиения по эквивалентности
  6. Упорядоченные разбиения
  7. Шаг разбиения для равноотстоящих узлов определяем по формуле

Напомним, что разбиением множества A называется семейство { Ai } его непустых попарно непересекающихся подмножеств, таких что È iAi = A. Подмножества Ai называются блоками разбиения. Если в семействе учитывается порядок подмножеств, и если допускаются пустые блоки, то оно называется упорядоченным разбиением.

Упорядоченные разбиения и обобщенный бином Ньютона. Будем говорить, что упорядоченное разбиение (A 1 , A 2 , ×××, Am) множества E= { e 1, e 2, ×××, en } имеет тип (k1, k2, ×××, km), если |A1| = k1, |A2| = k2,×××, |Am| = km. Число таких разбиений обозначается через P(k1, k2, ×××, km) или Pn(k1, k2, ×××, km), где n= k1 + k2 + ××× + km.

Лемма 1. .

Доказательство. Подмножество A1 можно выбрать способами. Подмножество A2 выбирается из оставшихся n-k1 элементов, его можно будет выбрать способами. Подмножество A3 – способами, и т.д. Выбор подмножества Am определен предшествующими подмножествами. Отсюда получаем

.

Поскольку n – k1 – ∙∙∙ – km-1 = km, то после сокращения дроби получаем нужное равенство.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)