Математика и информатика. Учебное пособие по всему курсу Тольятти 2008 удк 51 004 (075. 8) Ббк 22. 1832. 81 Е егорова, Э. В. Учебное пособие по дисциплине Математика и информатика для студентов гуманитарных и педагогических специальностей очной формы обучения

• Название: Учебное пособие по всему курсу Тольятти 2008 удк 51 004 (075. 8) Ббк 22. 1832. 81 Е егорова, Э. В. Учебное пособие по дисциплине Математика и информатика для студентов гуманитарных и педагогических специальностей очной формы обучения
• Дата: 27.10.2020
• Размер: 1.82 Mb.
• Имя файла: Математика и информатика.doc
• Тип: Учебное пособие; #146041
• страница: 4 из 12

Глава 3. Структуры на множестве. Комбинаторика

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

Комбинаторика – это раздел математики, в котором для конечных множеств рассматриваются различные соединения элементов: перестановки, размещения, сочетания. В задачах, связанных с выборкой элементов множества, необходимо подсчитать количество различных комбинаций этих элементов. С теоретико-множественной точки зрения решение комбинаторных задач связано с выбором из некоторого множества подмножеств, обладающих определенными свойствами, и упорядочением множеств. Комбинаторика возникла в ХVI веке. В ней рассматривались задачи, связанные в основном с азартными играми. В процессе изучения таких задач были выработаны некоторые общие подходы к их решению, получены формулы для подсчёта числа различных комбинаций.

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

В теории вероятностей приходится подсчитывать общее число исходов эксперимента и число благоприятных исходов. Такой подсчет сводится к перебору возможных вариантов. Комбинаторика изучает количества комбинаций, подчинённых определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества.

3.1. Перестановки

Задачи, связанные с перестановками, относятся к задачам комбинаторики. Например, перестановка книг на полках. В таких задачах подсчитывается количество возможных вариантов перестановок, причем в каждой комбинации должны присутствовать все объекты строго по одному разу.

Определение 1: Перестановками называют комбинации, состоящие из одних и тех же n – различных элементов и отличающиеся только порядком их расположения.

Рn = n! = 1× 2× 3× …× n.

(3.1)

где: Р_n – количество перестановок;

n! = 1 · 2 · 3· … · (n - 1) · n – произведение всех натуральных чисел от 1 до n включительно есть «n-факториал».

Необходимо учитывать, что факториал нуля равен единице: 0! = 1.

Пример 1.

Определить количество трехзначных чисел, которые можно составить из трех цифр: 3, 5, 7, с учётом использования каждой цифры в числе строго по одному разу.

Решение.

Количество трехзначных чисел в данном примере определяется по формуле перестановок (3.1) и равно: Р₃= 1× 2× 3=6.

Пример 2.

Подсчитать количество способов расстановки на полке 5 разных книг.

Решение.

На первое место можно поставить любую из 5 книг, для каждого варианта первой книги на второе место может быть поставлена любая из оставшихся 4 книг. Итак, число перестановок из 5 книг равно:

5! = 54321= 120.

3.2. Размещения

Если в выборках из n объектов по m объектов порядок их следования по условию задачи имеет значения, то имеют дело с «задачей о рассаживании»: группу из n человек следует рассадить в аудитории за каждым столом по m-человек (m
Определение 2: Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком следования.

.

(3.2)

Пример 3.

Группу из 20 студентов можно разместить в аудитории по 2 человека за каждой партой. Порядок их размещения имеет значение.

Решение.

Количество возможных вариантов размещений вычисляется по формуле (3.2):

.

Пример 4.

Найти количество трехзначных чисел с неповторяющимися цифрами, которые можно составить из цифр: 1, 2, 3, 4, 5.

Решение.

Количество трехзначных чисел в данном примере определяется по формуле размещений (3.2) и равно: .

3.3. Сочетания

Если в выборках из n объектов по m объектов порядок их следования по условию задачи не имеет значения, то размещения, отличающиеся лишь порядком следования, становятся одинаковыми.

Определение 3: Сочетанием называют комбинации, составленные из n различных элементов по m элементов, которые отличаются только составом элементов и не зависят от порядка следования.

.

(3.3)

Сочетания используются, если важен только состав элементов в выборке.

Пример 5.

Группу из 20 студентов следует рассадить в аудитории по 2 человека за каждой партой. Порядок их размещения не имеет значения. Определить количество возможных вариантов сочетаний.

Решение.

Количество возможных вариантов сочетаний вычисляется по формуле (3.3):

.

Пример 6.

Флаг государства может комбинироваться из трёх полос разного цвета. Определить число комбинаций из пяти разных цветов, которые можно получить, выбирая из них три полосы разного цвета.

Решение.

Если учитывать порядок в комбинации, то: .

Если же порядок в комбинации не имеет значения, то разных комбинаций:

.

3.4. Вопросы для самоконтроля по теме «Комбинаторика»

1. Количество перестановок букв в слове «WORD» равно:

a) 20; b) 24; c) 16; d) 8.

2. Количество перестановок букв в слове «число» равно:

a) 120; b) 24; c) 5; d) 20.

3. Сколько различных трёхбуквенных комбинаций можно составить из букв слова «студент», если все буквы в комбинации различны?

a) 210; b) 240; c) 148; d) 32.

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

a) 30; b) 720; c) 120; d) 360.

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

a) 720; b) 360; c) 120; d) 30.

6. Количество перестановок букв в слове «TIME» равно:

a) 44; b) 26; c) 2; d) 24.

7. Сколько различных чисел можно составить из пяти цифр: 9, 7, 8, 1, 6, если все цифры в числе разные?

a) 120; b) 60; c) 24; d) 0.

8. Сколько различных двузначных чисел можно составить из пяти цифр: 5, 7, 8, 4, 1, если все цифры в числе разные?

a) 24; b) 20; c) 120; d) 60.

9. Сколько различных трёхзначных чисел можно составить из шести цифр: 1, 2, 3, 4, 5, 6, если все цифры в числе различны?

a) 360; b) 120; c) 60; d) 240.

10. Сколько различных трёхбуквенных комбинаций можно составить из букв слова «ГРОМ», если все буквы в комбинации различны?

a) 6; b) 24; c) 4; d) 12.

11. Сколько различных двухбуквенных комбинаций можно составить из букв слова «ЗАЧЁТ», если все буквы в комбинации различны?

a) 4; b) 120; c) 60; d) 20.

12. Сколько различных трёхзначных чисел можно составить из пяти цифр: 7, 5, 3, 4,1, если все цифры в числе разные?

a) 4; b) 120; c) 60; d) 20.

Часть 2. Основы теории вероятностей