Элементы комбинаторики. Решение задач на вычисление числа размещений, перестановок и сочетаний.

ПрактическАЯ РАБОТА№ 1

Тема: Элементы комбинаторики. Решение задач на вычисление числа размещений, перестановок и сочетаний.

Цели:

• ознакомиться с понятиями: число размещений, число перестановок, число сочетаний;

• научиться решать задачи на вычисление числа перестановок, размещений с и сочетаний

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за выполнение задания 1 и верное решение всех предложенных задач из задания 2.

оценка «4» ставится за выполнение задания 1 и верное решение любых тринадцати предложенных задач из задания 2.

оценка «3» ставится за выполнение задания 1 и верное решение любых десяти предложенных задач из задания 2.

Порядок выполнения работы

Задание 1.

1. Ознакомиться с лекцией 1.

2. Выписать в тетрадь определение и свойства основных понятий

3. Записать в тетрадь решение разобранных примеров

Лекция 1.

Тема «Комбинаторика. Число размещений, перестановок и сочетаний»

В комбинаторике изучают вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).

Рождение комбинаторики как раздела математики связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказалоднуиз основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливобросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученыйответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять в толк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве   элементов, а в множестве  —  элементов. Тогда число всех различных пар , где будет равно .

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

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

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

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

Число всех размещений множества из  элементов по  элементов обозначается через  (от начальной буквы французского слова “arrangement”, что означает размещение), где  и .

Теорема. Число размещений множества из  элементов по  элементов равно

Доказательство. Пусть у нас есть элементы . Пусть  — возможные размещения. Будем строить эти размещения последовательно. Сначала определим  — первый элемент размещения. Из данной совокупности  элементов его можно выбрать  различными способами. После выбора первого элемента  для второго элемента  остается  способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

Пример1. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Решение. Искомое число трехполосных флагов:

Определение. Перестановкой множества из  элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов  — это

Очевидно, перестановки можно считать частным случаем размещений при .

Число всех перестановок из  элементов обозначается  (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

Пример2. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

Решение. Искомое число расстановки 8 ладей

 по определению!

Определение. Сочетаниями из  различных элементов по  элементов называются комбинации, которые составлены из данных элементов по  элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из  элементов по элементов в каждом обозначается  (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа 

Все сочетания из множества  по два — .

.

Свойства чисел 

1. .

Действительно, каждому -элементному подмножеству данного  элементного множества соответствует одно и только одно -элементное подмножество того же множества.

2. .

Действительно, мы можем выбирать подмножества из  элементов следующим образом: фиксируем один элемент; число -элементных подмножеств, содержащих этот элемент, равно ; число -элементных подмножеств, не содержащих этот элемент, равно .

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

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

.

Теорема. 

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

1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член

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

Домножим числитель и знаменатель этой дроби на :

Пример3. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?

Искомое числоспособов

Задание 2.

Решить предложенные задачи.

Задачи.

1. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно звуков?

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

7. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?

8. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9. Сколькими способами можно расставить в ряд числа  так, чтобы числа  стояли рядом и притом шли в порядке возрастания?
10. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 5, 7, 8, если каждую цифру можно использовать только один раз?
11. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?

12. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа 4:

Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.

Сколько существует различных разбиений числа 11 на 4 слагаемых?
13. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15. Сколькими способами можно рассадить в ряд 17 человек, чтобы  и   оказались рядом?

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

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

Контроль знаний обучающихся:

• проверить практическую работу;

• устный опрос.

1. Что называется размещением? Как вычисляются размещения?

2. Что называется перестановками? Как вычисляются перестановки?

3. Что называется сочетанием? Как вычисляются сочетания?

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия.