Тема 22. Элементы комбинаторики




Комбинаторика изучает способы подсчета числа элементов различных конечных множеств.

Определение 1. Пусть задана совокупность из элементов. Из этой совокупности определенным образом выбрали элементов. В этом случае говорят, что задана выборка длиной в элементов из элементов.

Выборки могут формироваться по-разному. Различия обусловлены следующими причинами:

1) допускается ли в выборках повторение элементов;

2) учитывается ли в выборке порядок следования элементов.

Определение 2. Перестановками без повторений называют выборки из элементов длиной в элементов () без повторений с учетом порядка.

Формула для подсчета: .

Определение 3. Размещениями без повторений называют выборки из элементов длиной в элементов () без повторений с учетом порядка.

Формула для подсчета: .

Определение 4. Сочетаниями без повторений называют выборки из элементов длиной в элементов () без повторений и без учета порядка.

Формула для подсчета: .

Определение 5. Пусть имеется элементов, из которых элементов принадлежит первому типу, – второму, и т.д., -му типу, при этом , а элементы одного типа неразличимы между собой. Выборки из этих элементов длиной в элементов с повторениями и с учетом порядка называют перестановками с повторениями .

Формула для подсчета: .

Определение 6. Выборки из элементов длиной в элементов с повторениями и с учетом порядка называют размещениями с повторениями . Здесь возможно, что .

Формула для подсчета: .

Определение 7. Выборки из элементов длиной в элементов с повторениями и без учета порядка называют сочетаниями с повторениями . Здесь возможно, что .

Формула для подсчета: .

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

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

Правило сложения. Пусть необходимо выполнить действий, причем никакие два из которых не могут производиться одновременно (действия попарно несовместны). Если первое действие можно выполнить способами, второе действие можно выполнить способами и т.д., -е действие можно выполнить способами, то хотя бы одно действие можно выполнить способами.

Алгоритм решения задачи

1) Определить длину исходной совокупности элементов .

2) Определить длину искомой выборки .

3) Выяснить, целесообразно ли искомую выборку разбивать на подвыборки, и каковы параметры этих подвыборок?

4) Выяснить, допускается ли в выборках (подвыборках) повторение элементов?

5) Выяснить, учитывается ли в выборке (подвыборке) порядок следования элементов?

6) Выяснить, как, зная число подвыборок, получить число искомых выборок (какое правило требуется использовать: сложения или умножения)?

7) Вычислить число подвыборок, а затем число искомых выборок.

Пример 1. Имеются 3 различные книги: А, В и С. Сколькими различными способами их можно расставить на полке?

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

Пример 2. Из трех различных книг А, В и С две отбирают на выставку. Сколько выставочных комплектов можно составить?

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

Пример 3. Имеется 5 карточек с буквами A, B, C, D, E. Сколько различных «слов», содержащих не более трех букв, можно из них составить?

Решение. Длина исходной совокупности элементов . По условию задачи каждое «слово» содержит либо 1, либо 2, либо 3 буквы, то есть имеется 3 искомых подвыборки, длины которых , и . Так как все карточки различны, то повторение элементов в каждой подвыборке не допускается. Так как «слова» отличаются не только составом букв, но и порядком следования элементов, то в каждой подвыборке порядок следования элементов учитывается. Таким образом, искомые подвыборки представляют собой размещения без повторений. Вычислим число искомых подвыборок.

При получится «слов».

При получится «слов».

При получится «слов».

Так как «слово», составленное только из одной буквы не может содержать только две или только три буквы; «слово», составленное только из двух букв не может содержать только одну или только три буквы; «слово», составленное только из трех букв не может содержать только одну или только две буквы, то действия по составлению «слов» только из одной, только из двух и только из трех букв попарно несовместны. Поэтому для подсчета общего числа искомых выборок применяем правило сложения. Тогда число «слов», содержащих не более трех букв 5+20+60=85.

Пример 4. В конкурсе по пяти номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по каждой номинации установлены: а) различные по значимости призы; б) одинаковые по значимости призы.

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

а) Пусть по каждой номинации установлены различные по значимости призы. В этом случае каждый из вариантов распределения призов отличается от других как составом фильмов, так и их порядком по номинациям (или и тем и другим), причем одни и те же фильмы могут повторяться несколько раз (каждый из фильмов может выиграть как в одной, так и в нескольких номинациях). Следовательно, искомая выборка представляет собой размещение с повторениями из 10 элементов по 5. Их число .

б) Пусть по каждой номинации установлены одинаковые по значимости призы. Тогда порядок следования фильмов в комбинации пяти призеров значения не имеет, число вариантов распределения призов представляет собой число сочетаний с повторениями из 10 элементов по 5, которое равно .

Теоретический материал: [2, гл. 10], [3, гл. 17], [8], [10], [12, гл. 22], [13, гл. 1], [37].

 



Поделиться:




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

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-04-14 Нарушение авторских прав и Нарушение персональных данных


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