Сочетания, размещения, перестановки

Сочетания, размещения, перестановки

Пусть – конечное множество, набор элементов ( ) из A называется –выборкой.

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

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

Неупорядоченная –выборка без повторений называется -сочетаниемили сочетанием из n элементов по k, другими словами, это k–элементное подмножество множества А.

Упорядоченная –выборка без повторений называется –размещением (перестановкой) или размещением из n элементов по k.

Неупорядоченная –выборка с повторениями называется –сочетанием с повторениями.

Упорядоченная –выборка с повторениями называется –размещением с повторениями. –размещение без повторений называется перестановкой из n элементов.

Например, рассмотрим множество . Составим сочетания из трех элементов по два: (a₁, a₂), (a₁, a₃), (a₂, a₃).

Все сочетания с повторениями из трех элементов по два представляют собой следующие (3,2)-выборки: (a₁, a₁), (a₁, a₂), (a₁, a₃), (a₂, a₂), (a₂, a₃), (a₃, a₃).

Далее выпишем все размещения из трех элементов по два без повторений: (a₁, a₂), (a₂, a₁), (a₂, a₃); (a₃, a₂), (a₁, a₃), (a₃, a₁).

Все размещения с повторениями из трех элементов по два имеют вид: (a₁,a₁), (a₁,a₂), (a₂,a₁), (a₂,a₂), (a₁,a₃), (a₃,a₁), (a₂,a₃), (a₃,a₂), (a₃,a₃).

Наконец, перестановки из трех элементов − это следующие упорядоченные без повторений (3,3)-выборки: (a₁,a₂,a₃), (a₁,a₃,a₂), (a₂,a₁,a₃), (a₂,a₃,a₁), (a₃,a₁,a₂), (a₃,a₂,a₁).

Число сочетаний, размещений и

Размещений с повторениями

Пусть – число всех –размещений с повторениями.

Теорема 2.

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

Число всех –размещений обозначается через .

Теорема 3. .

Доказательство. Пусть – –размещение из множества , где , , для всех . Элемент может быть выбран n способами, , т.е. после выбора элемента элемент может быть выбран способом, после выбора и выбираем элемент , он может быть выбран способами и т.д. После выбора элементов , ,…, последний элемент может быть выбран способами.

По правилу произведения получаем, что число всех –размещений равно .

Пусть – число всех перестановок из элементов.

Следствие. .

Число всех –сочетаний обозначается через или . Эта величина называется биномиальным коэффициентом.

Теорема 4.

Доказательство. Рассмотрим –сочетание , эту неупорядоченную –выборку можно упорядочить способами ( в силу следствия теоремы 3). Если упорядочить каждое –сочетание, то получим все упорядоченные –выборки, т.е. . Отсюда получаем, что .

Задача 3. Сколько существует двоичных матриц с строками и столбцами, все строки которых различны?

Решение. Число различных двоичных упорядоченных наборов длины равно . Число всех двоичных матриц с строками совпадает с числом всех размещений из элементов по . Следовательно, по теореме3 получаем, что число матриц равно .

Задача 4. Сколькими способами из колоды в 36 карт можно вытащить 5 карт так, чтобы среди них были три карты червовой масти и две крестовой масти?

Решение. Всего в колоде имеем по 9 карт каждой из 4 мастей. Три карты червовой масти можем вытащить способами, а две карты крестовой масти можно вытащить способами. По правилу произведения получаем, что существует × способов вытащить из колоды 5 карт определенным образом.

Разбиение множества

Множества задают разбиение множества А, если объединение всех множеств равно А и все множества попарно не пересекаются, т.е. для всех .

Теорема 6. Число различных упорядоченных разбиений множества А мощности на подмножеств заданных мощностей равно .

Доказательство. Пусть ─ некоторое разбиение множества А на подмножеств, причем , , …, , для всех . Множество может быть выбрано способами, после выбора множество может быть выбрано способами и т.д. После выбора множеств множество может быть выбрано способами. Тогда по правилу произведений получаем, что общее число разбиений равно

Теорема доказана.

Число называется полиномиальным коэффициентом и обозначается через .

Теорема 7. Если множества задают разбиение множества А, тогда

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

Следствие. Если множества не пересекаются, то

.

Это следствие представляет собой обобщенное правило суммы.

Задача 5. Дано множество U из 9 элементов. Каким числом способов в нем можно выбрать три подмножества A, B, C так, чтобы выполнялись условия: , .

Решение. Построим диаграмму Венна для искомых подмножеств A, B, C универсального множества U (см. рис.1). Введем обозначения: , , .

Рис.1

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

§7. Перестановки с фиксированным числом повторений

Пусть . Упорядоченную −выборку c повторениями, где встречается раз для всех , назовем перестановкой с повторениями. Число всех таких перестановок обозначим через .

Теорема 8.

Доказательство. Пусть − множество номеров мест, на которых стоит элемент в перестановке a.

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

Задача 6. Сколько различных слов можно составить, переставляя буквы слова «математика»?

Решение. В слове «математика» буква «м» встречается 2 раза, буква «а» – 3 раза, буква «т» – 2 раза, буква «е» – 1 раз, буква «и» - 1 раз, буква «к» – 1 раз. Всего в слове 10 букв, тогда число всех различных слов равно .

Задача 7. Сколько слов длины 9 в алфавите можно составить при условии, что , где обозначает число вхождений буквы в слово.

Решение. Если , тогда , и число слов, удовлетворяющих этому условию, равно числу двоичных последовательностей длины 9.

Если , тогда , и, рассматривая всевозможные разложения числа 5 на упорядоченную сумму двух слагаемых, получаем, что число слов в этом случае равно

= .

Наконец, если , тогда , и число слов равно .

По правилу суммы получаем, что всего можно составить слов.

Задача 8. Сколькими способами можно переставить буквы слова «комиссия» так, чтобы:

1) никакие две гласные не стояли рядом;

2) не менялся порядок гласных букв;

3) две буквы «с» не шли подряд?

Решение. 1) Имеется перестановок согласных. Для каждого размещения согласных имеем 5 мест для размещения четырех гласных слова, тогда число всех размещений гласных букв слова равно . По правилу произведения получаем слов.

2) Число размещений согласных букв с учетом того, что буква «c» повторяется дважды равно . Очевидно, что на оставшиеся места гласные в указанном порядке размещаются однозначно.

3) Число различных слов, которые получаются перестановками букв слова «комиссия» равно .

Число слов, в которых две буквы «с» идут подряд равно . Получаем, слов, в которых две буквы «с» не идут подряд.

Задача 9. Сколькими способами можно разместить n одинаковых карандашей в k различных ящиках?

Решение. Перенумеруем ящики. Обозначим через − число карандашей, попавших в −ый ящик. Каждому размещению карандашей поставим в соответствие последовательность из нулей и единиц следующим образом: сначала записываем нулей, затем записываем единицу, далее пишем нулей, снова единицу, и т.д. Заканчивается последовательность нулями. Эта последовательность имеет нулей и единиц.

Например, при размещению, при котором в первом ящике 5 карандашей, во втором – нет карандашей, в третьем ящике – 3 карандаша, а в четвертом – 2 карандаша, соответствует последовательность 0000011000100.

Таким образом, число всех размещений совпадает с числом всех двоичных наборов с n нулями и единицами. Число таких наборов, в силу теоремы 8, равно .

Задача 10. Сколько решений в неотрицательных целых числах имеет уравнение

Решение. Пусть решение уравнения. Этому решению поставим в соответствие двоичный набор с n нулями и единицами следующим образом:

.

Таким образом, между множеством двоичных наборов с n нулями и единицами и множеством решений заданного уравнения устанавливается взаимно-однозначное соответствие, откуда число решений равно .

Задачи

1. Студенты изучают 7 предметов. Сколькими способами можно составить расписание на один день, если в день следует устанавливать не менее двух и не более четырех предметов?

2. Сколько существует семизначных чисел, делящихся на 5? Сколько среди них четных?

3. Сколько существует девятизначных чисел, которые одинаково читаются как слева направо, так и справа налево? Сколько среди них четных?

4. В скольких точках пересекаются диагонали выпуклого n-угольника, если никакие три из них не пересекаются в одной точке?

5. В комнате n лампочек. Сколькими способами можно зажечь k лампочек? Сколько существует способов освещения комнаты?

6. Сколько существует пятизначных чисел, у которых каждая следующая цифра больше предыдущей?

7. Сколько существует шестизначных чисел, у которых цифры расположены в неубывающем порядке?

8. Имеется n черных и m белых шаров. Сколькими способами можно их выложить в ряд так, чтобы никакие два черных шара не лежали рядом?

9. Студенту необходимо сдать 4 экзамена в течение 10 дней, причем известно, что в последний день он сдает экзамен. Сколькими способами он может это сделать?

10. Сколькими способами можно рассадить n гостей за круглым столом?

11. Имеется 4 типа открыток. Сколькими способами можно выбрать 10 открыток?

12. Сколькими способами n различных (одинаковых) предметов можно разложить в k одинаковых ящиков (разных ящиков)?

13. Сколько существует чисел не больше 100, которые не делятся ни на 2, ни на 3, ни на 5?

14. На полке стоят n книг. Сколькими способами можно взять из них m так, чтобы никакие две не стояли рядом?

15. Сколькими способами можно выбрать три различных карандаша из имеющихся пяти карандашей разных цветов?

16. В группе 5 девочек и 7 мальчиков. Сколькими способами их можно разделить на 2 группы по 6 человек? Сколькими способами это можно сделать при условии, что в каждой группе должно быть хотя бы по одной девочке?

17. Сколькими способами можно рассадить за круглым столом m юношей и n девушек так, чтобы никакие две девушки не сидели рядом?

18. Имеется n абонентов телефонной сети. Сколькими способами можно одновременно соединить три пары?

19. Три студента сдают экзамен. Сколькими способами они могут сдать экзамен по пятибалльной системе? По семибалльной?

20. Сколько различных слов можно составить из букв слова «комбинаторика»?

21. Сколькими способами 12 одинаковых монет можно разложить по пяти пакетам так, чтобы ни один из пакетов не был пуст?

22. В конструкторском бюро все сотрудники знают хотя бы один из трех языков. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один сотрудник знает все три языка.

Литература

1. Алексеев В. Е. Элементы комбинаторики. – Пособие для студентов заочного отделения, Нижний Новгород, 2001.

2. Алексеев В.Е., Киселева Л.Г., Смирнова Т.Г. Задачи по дискретной математике. – Методическая разработка, Нижний Новгород, 2003.

3. Виленкин Н. Я. Комбинаторика. – М.: Наука, 1969.

4. Гаврилов Г.Н., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977.

5. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. – М.: Наука, 1977.

6. Киселева Л.Г. Элементы комбинаторики. – Методическая разработка, Нижний Новгород, 1990.

7. Киселева Л.Г., Смирнова Т.Г. Тождества и уравнения в алгебре множеств. – Методическая разработка, Нижний Новгород, 1999.

8. Марков А.А. Элементы комбинаторного анализа. – Методическая разработка, Горький, 1988.

9. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

СОДЕРЖАНИЕ

§1. Сочетания, размещения, перестановки 3

§2. Основные правила комбинаторики 4

§3. Число сочетаний, размещений и размещений с повторениями 8

§4. Основные свойства биномиальных коэффициентов 11

§5. Бином Ньютона 12

§6. Разбиение множества 13

§7. Перестановки с фиксированным числом повторений 16

§8. Число сочетаний с повторениями 21

§9. Формула включений и исключений 22

Задачи 24

Контрольные задания 32

Литература 39

Сочетания, размещения, перестановки

Пусть – конечное множество, набор элементов ( ) из A называется –выборкой.

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

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

Неупорядоченная –выборка без повторений называется -сочетаниемили сочетанием из n элементов по k, другими словами, это k–элементное подмножество множества А.

Упорядоченная –выборка без повторений называется –размещением (перестановкой) или размещением из n элементов по k.

Неупорядоченная –выборка с повторениями называется –сочетанием с повторениями.

Упорядоченная –выборка с повторениями называется –размещением с повторениями. –размещение без повторений называется перестановкой из n элементов.

Например, рассмотрим множество . Составим сочетания из трех элементов по два: (a₁, a₂), (a₁, a₃), (a₂, a₃).

Все сочетания с повторениями из трех элементов по два представляют собой следующие (3,2)-выборки: (a₁, a₁), (a₁, a₂), (a₁, a₃), (a₂, a₂), (a₂, a₃), (a₃, a₃).

Далее выпишем все размещения из трех элементов по два без повторений: (a₁, a₂), (a₂, a₁), (a₂, a₃); (a₃, a₂), (a₁, a₃), (a₃, a₁).

Все размещения с повторениями из трех элементов по два имеют вид: (a₁,a₁), (a₁,a₂), (a₂,a₁), (a₂,a₂), (a₁,a₃), (a₃,a₁), (a₂,a₃), (a₃,a₂), (a₃,a₃).

Наконец, перестановки из трех элементов − это следующие упорядоченные без повторений (3,3)-выборки: (a₁,a₂,a₃), (a₁,a₃,a₂), (a₂,a₁,a₃), (a₂,a₃,a₁), (a₃,a₁,a₂), (a₃,a₂,a₁).