Решение уравнений с неизвестным множеством 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Решение уравнений с неизвестным множеством



А.А. Хусаинов

Н.Н. Михайлова

ДИСКРЕТНАЯ МАТЕМАТИКА

Утверждено в качестве учебного пособия

ученым советом Федерального государственного бюджетного образовательного

учреждения высшего профессионального образования

«Комсомольский-на-Амуре государственный технический университет»

 

 

Комсомольск-на-Амуре 2012

 

УДК 519.1

ББК

Х

 

 

Хусаинов А.А.

Х Дискретная математика: Учебное пособие / А.А. Хусаинов, Н.Н. Михайлова. – Комсомольск-на-Амуре: Изд-во ФГБОУ ВПО «КнАГТУ», 2012. – 90 с.

 

В пособии изложены основы дискретной математики: конечные множества и отношения, комбинаторный анализ, производящие функции и рекуррентные соотношения, теория графов, деревья, хроматические функции графов, функции Мебиуса на конечных частично упорядоченных множествах.

Предназначено для студентов направлений 230100 «Информатика и вычислительная техника» и 231000 «Программная инженерия» заочной формы обучения, обучающихся с использованием дистанционных технологий.

 

ББК

 

 

© Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2012

© Институт новых информационных технологий Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2012

 

ВВЕДЕНИЕ

Математика изучает множества с заданными на них математическими структурами в смысле Николы Бурбаки. В частности, объектами изучения являются группы, частично упорядоченные множества, топологические пространства. Поскольку числа, функции и отношения определяются как множества, то к математическим структурам относятся системы уравнений и неравенств, связывающих элементы множеств. В современной терминологии эти структуры чаще называют математическими моделями.

Дискретная математика изучает математические структуры с теми или иными условиями конечности. Как правило, эти условия конечности позволяют формализовать и наглядно формулировать проблемы дискретной математики. В то же время дискретная математика имеет много общего со всеми областями математики. Это превращает ее в достаточно общую область математики, многие методы решения которой понятны для широкого круга читателей.

Как правило, курс дискретной математики включает комбинаторный анализ и теорию графов, изложение которых невозможно без введения в теорию множеств. Кроме этих традиционных разделов добавляют алгебру логики и логику предикатов [12], [14], [17], конечные автоматы [10], [12], экстремальные задачи [6], элементы теории алгоритмов [4]. Мы предпочитаем этим разделам производящие функции и частично упорядоченные множества.

Наш курс состоит из разделов:

1. Множества и отношения.

2. Комбинаторный анализ.

3. Производящие функции.

4. Теория графов.

5. Частично упорядоченные множества.

К каждой главе прилагается список несложных упражнений. Более сложные задачи читатель может найти в [5], [7], [13].

В рамках дисциплины «Дискретная математика» выполняется одно расчетно-графическое задание и одна контрольная работа. Номер варианта определяется двумя последними цифрами номера зачётной книжки следующим образом:

если две последние цифры номера зачётной книжки находятся в диапазоне 00 – 29, то им соответствуют номера вариантов с 01 по 30, например, числу 23 соответствует вариант 24;

в других случаях к остатку от деления числа, состоящего из двух последних цифр номера зачётной книжки, на 30 прибавляется 1. Если последние цифры зачётной книжки, например, 56, то номер варианта – 27.

Отчёты по расчётно-графическому заданию и контрольной работе сдаются в письменном виде. После изучения курса сдаётся письменный экзамен. Экзаменационный билет составляется из экзаменационных вопросов и задач, приведённых в пособии.

 

 

МНОЖЕСТВА И ОТНОШЕНИЯ

Эта глава посвящена операциям над множествами, перечислительным задачам, отношениям и их приложениям.

Множеством называется совокупность некоторых объектов x, которая рассматривается как отдельный объект A. Объекты x называются его элементами. Запись x Î A будет означать в дальнейшем, что x – элемент множества A.

Ниже мы будем применять следующие стандартные обозначения:

· N – множество неотрицательных целых чисел 0, 1, 2, 3, …,

· Z – множество целых чисел,

· Q – множество рациональных чисел , где m – целое число, а n – положительное целое число,

· R – множество вещественных чисел,

· C – множество комплексных чисел.

Для знакомства с отношениями и их приложениями рекомендуем книгу [1]. Лучше всего связь отношений с базами данных описана в [8].

1.1. Способы задания множеств

Пусть A и B – множества. Множество A называется подмножеством множества B, если каждый элемент x множества A является элементом множества B. В этом случае применяется обозначение A Í B.

Множество можно задавать перечислением его элементов, или как подмножество элементов, обладающих некоторым свойством, или как образ некоторого множества относительно отображения:

1. M = { a1, a2 , ∙∙∙, ak }, нет равных элементов ai и aj,при i ≠ j.

2. M = { xÎ A: P (x) }, где P(x) – некоторое свойство, выполнение которого зависит от элемента x множества A.

3. M = { f (x): xÎ A }, где A – множество.

Свойство P(x) может быть получено из простейших формул вида u = v и u Î v с помощью логических операций: & (и), Ú (или), ~ (не), Þ (следует) и кванторов "(для всех), $ (существует). Например, свойство P(x), выраженное формулой

P (x) = (x Î Z) & (x >0) & ($ y)((y Î Z)& (x = y + y)),

имеет место, если и только если x – положительное целое число, кратное 2. В этом случае M = { Z: P (x) } будет множеством, состоящим из чисел 2, 4, 6, 8, ….

Операции и их свойства

Будем предполагать, что рассматриваемые далее множества A, B, C, …, Ai, I, над которыми выполняются операции, являются подмножествами некоторого множества U, которое называется универсумом. Ниже через {x: P(x)} будет обозначать множество элементов xÎU, удовлетворяющих условию P(x).

Определим операции с помощью следующих формул:

· A Ç B= { x: xÎA & xÎB }называется пересечением множеств A и B,

· A È B= { x: xÎA Ú xÎB } объединением,

· A\B= { x: xÎA & ~(xÎB) } теоретико-множественной разностью множеств,

· ADB= A\B È B\A – симметрической разностью,

· =U\A – дополнением множества A,

· Ai = { x: ($ i Î I) x Î Ai } -- объединением семейства множеств,

· пересечение семейства множеств Ai = { x:(" i Î I) xÎAi },

Через |A| будем обозначать количество элементов конечного множества.

Предложение. Пусть U – множество. Тогда для любых его подмножеств A, B и C верны равенства:

1. A Ç B = B Ç A, A È B = B È A, (коммутативность).

2. A Ç(B Ç C) = (A Ç BC, A È(B È C)=(A È BC, (ассоциативность).

3. A Ç(A È B) = A È(A Ç B)= A (закон поглощения).

4. A Ç(B È C) = (A Ç B)È(A Ç C),

A È (B È C) = (A È B)Ç(A È C) (дистрибутивность).

5. , .

6. A Ç A = A, A È A = A.

7. A È U = U, A ÇÆ=Æ.

8. A ÈÆ= A, A Ç U = A.

9. .

10. , (законы де Моргана).

Доказательство. Докажем, например, первое из свойств дистрибутивности (равенство 4). Для этой цели нужно доказать, что левая часть равенства содержится в правой, и наоборот. Пусть xÎ AÇ(BÈC). Тогда xÎA и xÎ BÈC. И значит (xÎA и xÎ B) или (xÎA и xÎC). Следовательно xÎ(AÇB)È(AÇC).

Эти свойства иллюстрируются с помощью показанных на рис.1.1 диаграмм Эйлера-Венна. Точки прямоугольников соответствуют элементам универсума U. Точки кругов – подмножествам A, B, C. Слева элементы множеств B и C заштрихованы вертикальными линиями. Отсюда область, заштрихованная вертикальными линиями будет соответствовать объединению BÈC. Элементы из A заштрихованы горизонтальными линиями. Следовательно, область AÇ(BÈC) будет заштрихована в клетку. Справа область B заштрихована косыми линиями, а область A – горизонтальными. Область AÇB будет заштрихована косыми и вертикальными. Аналогичное верно для области AÇC. Из рис.1.1 видно, что область, показанная слева и заштрихованная горизонтальными и вертикальными линиями равна области, показанной справа, заштрихованной косыми и горизонтальными линиями. Значит, соответствующие множества AÇ(BÈC) и (AÇB)È(AÇC) равны.

 

       
   

 

 


Рис. 1.1. Диаграммы Эйлера-Венна

 

 

Перечисление подмножеств

Пусть M – произвольное множество. Его мощность обозначается | M |. Если множество M состоит из конечного числа элементов, то | M | число его элементов. Обозначим через 2M = { A: A Í M } – множество всех подмножеств множества M.

Теорема. Если множество М имеет конечное число элементов, то | 2M | = 2| M |.

Доказательство. Пусть M = {a0, a1, ××××, an-1 }. Каждому подмножеству можно поставить в соответствие битовую строку, состоящую из n разрядов, равных 0 или 1. Эта битовая строка представляет собой двоичную запись некоторого неотрицательного целого числа. Ее i -й разряд равен 1, если ai ÎA, и равен 0, в других случаях. Хорошо известно, что количество двоичных n -разрядных чисел равно 2 n . Следовательно, количество подмножеств будет равно 2| M |.

Упражнение. Докажите предыдущую теорему с помощью индукции по числу элементов множества M.

Замечание. Получаем алгоритм перебора подмножеств. Каждому подмножеству соответствует неотрицательное целое число, двоичная запись которого содержит единичные разряды, соответствующие элементам этого подмножества. Прибавляя по 1, получаем все подмножества. Например, для M = { a, b, c } этот алгоритм можно проиллюстрировать с помощью таблицы 1.1.

Таблица 1.1.

Перебор подмножеств множества { a, b, c }

Номер   Двоичная запись Подмножество
    Æ
    { c }
    { b }
    { b, c }
    { a }
    { a, c }
    { a, b }

Отношения и функции

В данном параграфе изучаются частично упорядоченные множества и решетки. Рассматривается также отношения эквивалентности и их связь с разбиениями множества. Доказывается, что частично упорядоченное множество отношений эквивалентности на множестве является решеткой.

Определение 1. Пусть X – множество. Бинарное отношение R Í X ´ X называется отношением порядка на X, если оно рефлексивно, антисимметрично и транзитивно. Таким образом, R – отношение порядка, если

(1) (a,a) ÎR для всех a Î X,

(2) aRb & bRa Þ a = b,

(3) для всех a, b, c Î X верна импликация aRb & bRc Þ aRc,

Пара (X, R), состоящая из множества X и отношения порядка R на X называется частично упорядоченным множеством.

Пусть (X, R) – частично упорядоченное множество. Всякое подмножество A Í X будет частично упорядоченным множеством с отношением порядка R Ç(A ´ A).

Отношение порядка обычно обозначается символом £.

Элемент x частично упорядоченного множества (X,£) называется наибольшим (соответственно наименьшим), если для всякого y Î X верно y £ x (соответственно x £ y).

Определение 2. Пусть (X,£) – частично упорядоченное множество. Нижней гранью множества его элементов называется наибольший элемент подмножества

.

Нижняя грань обозначается через . Двойственно, как наименьший элемент множества , определяется верхняя грань .

Заметим, что нижняя грань должна принадлежать множеству , и, значит, удовлетворять неравенствам для всех 1≤ in. И среди элементов, удовлетворяющих этим неравенствам, она должна быть наибольшим элементом.

При n =2 нижняя грань множества обозначается , а верхняя .

Пример 1. Пусть (N+, |) – множество положительных натуральных чисел {1, 2, 3, …}, с отношением делимости:

m | n Û n делится на m Û ($ k Î N+) mk = n.

Тогда нижняя грань m Ù n равна наибольшему общему делителю, а m Ú n – наименьшему общему кратному.

Определение 3. Частично упорядоченное множество (X,£) называется нижней (соответственно верхней) полурешеткой, если для любых множество имеет нижнюю (соответственно верхнюю) грань в X. Если (X,£) является нижней и верхней полурешеткой, то оно называется решеткой.

Пример 2. Пусть X – множество. Частично упорядоченное множество (P(X),Í) подмножеств множества X с отношением включения будет решеткой.

Пример 3. Частично упорядоченное множество положительных натуральных чисел (N+, |) будет решеткой.

Лемма 1. Если конечное частично упорядоченное множество (X,£) является нижней полурешеткой и имеет наибольший элемент, то оно будет решеткой.

Доказательство. Пусть . В этом случае множество

S=

непусто и конечно. Поскольку X – нижняя полурешетка, то существует . Положим . Для всех i=1, …, n имеет место z³ ai. И z – наименьший среди обладающих этим свойством. Стало быть, z = .

Определение 4. Пусть X – множество. Бинарное отношение R Í X´X называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Таким образом, R – отношение эквивалентности на X, если

(1) (a,a)ÎR для всех a Î X,

(2) aRb Þ bRa

(3) для всех a, b, c Î X верна импликация aRb & bRc ÞaRc,

Определение 5. Разбиением множества X называется множество { Xi: iÎI } попарно непересекающихся подмножеств Xi Í X таких, что . С каждым разбиением { Xi: iÎI } можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого Xi.

Каждому отношению эквивалентности ~ на X соответствует разбиение { Xi: i Î I }, элементами которого являются подмножества, состоящие из эквивалентных элементов. Эти подмножества называются классами эквивалентности. Множество классов эквивалентности {Xi: iÎI} называется фактор-множеством множества X по отношению эквивалентности ~ и обозначается: X/~.

Теорема 1. Пусть X – конечное множество. Множество отношений эквивалентности на X с отношением включения Í является решеткой.

Доказательство. Множество отношений эквивалентности является нижней полурешеткой, ибо точной нижней гранью отношений эквивалентностей будет их пересечение. Оно будет иметь наибольший элемент X´X. Стало быть, оно будет решеткой, по лемме 1.

Поскольку разбиения множества X взаимно однозначно соответствуют отношениям эквивалентности на X, то множество разбиений легко превратить в частично упорядоченное множество. Отношение порядка между разбиениями определяется как имеющее место тогда и только тогда, когда разбиение P1 мельче чем P2, т.е. когда верна импликация

.

В этом случае будет верно включение , и, стало быть, отношение эквивалентности, соответствующее разбиению P1, будет содержаться в отношении эквивалентности, соответствующем разбиению P2 . Мы установили биекцию между разбиениями и отношениями эквивалентности на множестве. Эта биекция сохраняет порядок. Получаем

Следствие 1. Множество разбиений множества является решеткой.

Упражнение 1. Пусть (X, R) – конечное частично упорядоченное множество. Будет ли решеткой множество отношений порядка rÍR, упорядоченное отношением Í?

Определение 2.

· Атрибут Ak функционально зависит от множества атрибутов , еслидля любых элементов x, y ÎR Í A1 ´ A2 ´ ××× ´ An из равенства их компонент следует равенство .

· Если атрибут Ak функционально зависит от множества атрибутов , но не зависит функционально ни от какого строго содержащегося в нем подмножества , то Ak называется функционально полно зависящим от множества атрибутов .

· Множество атрибутов называется ключом записи файла, если во-первых для всех k Î{ 1, 2, ×××, n } атрибуты Ak функционально зависят от , и во-вторых это множество атрибутов удовлетворяет условию минимальности, в том смысле, что для любого подмножества множества некоторый атрибут Ak не зависит функционально от атрибутов этого подмножества. Во множестве всех ключей можно отметить некоторые ключи. Эти ключи называются выделенными. Остальные – не выделенными.

· Первичным ключом называется произвольный выделенный ключ. Ключ, не являющийся первичным, называется возможным.

Определение 3. (2NF) Файл с первичным ключом находится во второй нормальной форме, если он находится в первой нормальной форме, и для любого атрибут Ak функционально полно зависит от атрибутов .

Поскольку множество записей для файла в первой нормальной форме совпадает с отношением, определенном этим файлом, то можно говорить о второй нормальной форме отношения.

Пример 2. В приведенной выше таблице 1.2 определим первичный ключ как множество атрибутов {ВУЗ, Номер зачетки}. Год поступления зависит от номера зачетки. Поэтому зависимость года поступления от первичного ключа не является функционально полной. Стало быть, файл не находится во второй нормальной форме. Разобьем этот файл на два файла (таблицы 1.3 и 1.4), находящиеся во второй нормальной форме. Первый файл (таблица 1.3) не будет содержать года поступления.

Таблица 1.3.

Первый файл разбиения

ВУЗ Номер зачетки ФИО
АмГПГУ   Иванов Павел Сергеевич
КнАГТУ   Петрова Галина Сергеевна

Второй (таблица 1.4) содержит номер зачетки и год поступления. Он состоит из одной записи.

Таблица 1.4.

Второй файл разбиения

Номер зачетки Год поступления
   

Третья нормальная форма

Определение 4. Атрибут Ak транзитивно зависит от множества атрибутов , если существует множество, состоящее из атрибутов , каждый из которых функционально зависит от , такое, что Ak функционально зависит от .

Определение 5. (3NF) Файл с первичным ключом находится в третьей нормальной форме, если он находится в первой нормальной форме, и для любого функциональная зависимость атрибута Ak от атрибутов не является транзитивной.

Произвольный ключ отношения можно выделить как первичный. Если с помощью выделения любого ключа как первичного мы получаем отношение, находящееся в третьей нормальной форме, то заданное отношение называется находящимся в нормальной форме Бойса-Кодда. В частности, отношение будет находиться в нормальной форме Бойса-Кодда, если оно допускает единственный ключ.

Упражнения

1. Задано подмножество AÍU. Найти все подмножества XÍU, для которых

A ÇX= Æ.

2. Решить систему уравнений

3. Решить уравнения

(1) .

(2) .

(3) .

(4) .

4. Пусть - множество всех функций B ® A. Установить биекции между множествами

(1) A ´ B и B ´ A;

(2) (A ´ B)С и AC ´ BC;

(3) (AB)C и AB´C;

(4) ABÈC и AB ´ AC, если B Ç C = Æ.

5. Построить бинарное отношение

(1) рефлексивное, симметричное, не транзитивное,

(2) рефлексивное, антисимметричное, не транзитивное,

(3) рефлексивное, транзитивное, не симметричное,

(4) антисимметричное, транзитивное, не рефлексивное.

6. Доказать, что пересечение семейства отношений эквивалентности на заданном множестве является отношением эквивалентности.

7. Построить пример частично упорядоченного множества, имеющего ровно один минимальный элемент, но не имеющего наименьшего элемента.

8. Доказать, что если R – отношение порядка, то R-1 – отношение порядка.

9. Доказать, что пересечение отношений порядка является отношением порядка. Всегда ли объединение отношений порядка является отношением порядка?

10. Найти число рефлексивных отношений на множестве из n элементов.

11. Найти число симметричных отношений на множестве из n элементов.

12. Будет ли множество функций X ® R решеткой относительно отношения порядка

f£g Û f(a) £g(a)?

13. Сколько подмножеств множества A={1,2,∙∙∙,300} содержат по крайней мере одно число кратное 5, и ни одного – кратного 10.

14. Сколько подмножеств множества A={1,2,∙∙∙,300} не содержат ни чисел кратных 4, ни чисел кратных 6?

15. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4, но не содержат чисел кратных 6?

16. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4 и, сверх того, содержат по крайней мере одно число кратное 6?

 

КОМБИНАТОРИКА

Комбинаторикой называется раздел дискретной математики, который занимается следующими вопросами:

1. Задача перечисления: найти количество элементов заданной математической модели.

2. Задача перебора: построить алгоритм перебора этих элементов.

Основное внимание мы будем уделять задаче перечисления.

Конечная математическая модель в комбинаторике называется конфигурацией. Мы изучим следующие конфигурации: размещения, сочетания, разбиения и их обобщения. Для дальнейшего изучения рекомендуем [14], [15], [21].

Размещения

Постановка задачи. Дано m предметов и n ящиков, в которые размещаются предметы. Сколько существует размещений, удовлетворяющих некоторым заданным условиям?

Определение 1. Размещением с повторениями называется функция

f:{ x1, x2, ×××, xm } ®{ y1, y2, ×××, yn }.

Элементы xi называются предметами, а yj - ящиками.

Полагая ai = f(xi), легко убедиться в том, чточисло всех размещений с повторениями равно количеству последовательностей { a1, a2, ×××, am } чисел 1£ ai £ n и значит оно равно nm.

Определение 2. Рассмотрим некоторое конечное множество равновероятных элементарных событий, которые мы будем иногда назвать исходами. Событием называется подмножество множества всех исходов. Его элементы называются благоприятными исходами. Вероятность события определяется как отношение количества благоприятных исходов к количеству всех исходов.

Например, если мы бросаем монету, то возможны два исхода. Число исходов выпадения «орла» равно 1. Значит, вероятность выпадения орла равно 0.5.

Сочетания

Сочетанием элементов множества X называется подмножество конечного множества AÍX. Если |A|=k, |X|=n, то подмножество X называется с очетанием из n по k. Например, сочетания трех цветов семицветной радуги будут описываться подмножествами, состоящими из трех элементов выбранных из множества, состоящего из 7 элементов.

Треугольник Паскаля и бином Ньютона. Для вычисления числа сочетаний построим таблицу, которая называется треугольником Паскаля. Она основана на следующей теореме:

Теорема 1. Число сочетаний удовлетворяет соотношениям:

; (при 0 < k < n).

Доказательство. Число пустых подмножеств равно 1. Стало быть, . Подмножества, состоящие из n элементов, совпадают со всем множеством, отсюда . Число сочетаний, не содержащих n -й элемент, равно , а содержащих – . Следовательно, при 0 < k < n,

Следующая таблица 2.1 строится на основе теоремы 1 и называется треугольником Паскаля.

Таблица 2.1

Треугольник Паскаля

 

n k            
             
             
             
             
             
             
             

Теорема 2. Число сочетаний из n по k равно .

Доказательство. По индукции по n. При n=0 и k=0 получаем . Пусть теорема верна для n. С помощью теоремы 1 получаем

.

Откуда формула верна для n +1 и всех k < n +1.

Другой способ доказательства заключается в сопоставлении каждой инъекции ее образ. В этом случае, учитывая, что число инъекций с одинаковым образом равно k!, получаем Þ .

Теорема 3. (Бином Ньютона).

Доказательство. По индукции по n. Пусть формула верна для n. Тогда

Можно предложить также другое доказательство: Рассмотрим произведение n сомножителей (1 +x) (1 +x) × × × (1 +x). Сомножители будем рассматривать как ящики. Произведение равно сумме степеней xk, причем при каждом k слагаемые xk получаются выбором из ящиков k элементов, равных x. Отсюда коэффициент при xk будет равен количеству содержащих k элементов подмножеств множества, состоящего из n элементов.

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

Рис. 2.2. Решение уравнения x1 + ××× +xn = k

Каждому решению x1 + ××× +xn = k соответствует неубывающая последовательность y1 ≤y2 × × × ≤yn-1, где y1=x1, y2 = y1+x2, ×××, yn-1 = yn-2 + xn-1.

Теорема 7. .

Доказательство. Рассмотрим график неубывающей функции

Рис. 2.3. График неубывающей функции

График задается последовательностью из 0 и 1

0 0 1 1 0 0 … 0 1 0 0 … 1 1 … 1

состоящей из n-1+k разрядов, имеющих k единиц.

Следствие 1. равно числу неубывающих функций

{1,2, ×××, k } ® {1,2, ×××, n }.

Доказательство. Первый способ: транспонировать графики. Если график, показанный на рис.2.3, отразить относительно прямой y = x, то получим график функции {1,2, ×××, k } ® {1,2, ×××, n }. Это доказывает утверждение следствия.

Второй способ: число неубывающих функций {1,2, ×××, k } ® {1,2, ×××, n } равно = = .

Получаем следующую таблицу 2.2, содержащую числа конфигураций

Таблица 2.2

Число конфигураций

 

  функций m®n неубывающих функций m®n
Всех nm
Инъективных
Сюръективных ?
Биективных n!, если m=n, иначе 0 1, если m=n, иначе 0

Здесь m = {0,1, ×××, m-1}. Например, число неубывающих сюръективных отображений {0,1, ×××, m -1} ® {0,1, ×××, n -1} равно .

 

Теорема 2.

где q 1, …, qт являются различными простыми делителями числа n.

Доказательство. Находим число не взаимно простых с n по формуле включения и исключения, пользуясь тем, что количество делящихся среди {1,2, …, n } на число q равно n/q. Затем это число отнимаем от n.

Разбиения

Напомним, что разбиением множества 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.

.

Доказательство. Рассмотрим как ящики сомножители произведения

.



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 904; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.238.235.181 (0.2 с.)