Изучение нового материала. Правило суммы и формула включений и исключений

Комбинаторные задачи бывают самых разных видов. Однако, большинство задач решается с помощью двух основных правил – правила суммы и правила произведения.

Правило суммы и формула включений и исключений

Часто удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. В этом случае общее число комбинаций равно сумме чисел комбинаций во всех классах. Это утверждение и называют правилом суммы. Иногда это правило формулируют несколько иначе: если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами [10].

При использовании правила суммы в последней формулировке надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В (или, как мы говорили раньше, чтобы ни одна комбинация не попала сразу в два класса). Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь m + n - k способов
выбора, где k – число совпадений. Правило комбинаторики для этого случая называется формулой включений и исключений [29].

Решить задачи: 1, 3, 5, 6 (см. прил. 1).

Правило произведения

Второе правило, называемое правилом произведения, несколько сложнее. Часто при составлении комбинации из двух элементов известно, сколькими способами можно выбрать первый элемент, и сколькими способами второй, причем число способов выбора второго элемента не зависит от того, как именно выбран первый элемент. Пусть первый элемент можно выбрать m способами, а второй n способами. Тогда пару этих элементов можно выбрать m  n способами. Иными словами: если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить
m  n способами [29].

Правило произведения можно наглядно представить с помощью следующей таблицы:

(А1,В11)	(А1,В12)	…	(А1,В1n)
(А2,В21)	(А2,В22)	…	(А2,В2n)
…	…	…	…
(Аi,Вi1)	(Аi,Вi2)	…	(Аi,Вin)
…	…	…	…
(Аm,Вm1)	(Аm,Вm2)	…	(Аm,Вmn)

 

Здесь через А₁, А₂, … , А_m обозначены m способов выбора объекта А, а через В _{i 1}, B_i2, … , B_in обозначены n способов выбора объекта В, если объект А выбран  i-тым способом. В каждой строке таблицы содержится n пар, всего m строк. Следовательно данная таблица содержит все способы выбора пары  (А, В) и состоит из m  n элементов [10].

Правило произведения, сформулированное для двух объектов, можно обобщить и на случай k объектов.

Задачи: 1, 3, 5, 6, 8 (см. прил. 2).

Итог занятия

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

 

Занятие 2. Размещения

Цель: знакомство с основными формулами комбинаторики.

Задачи:

- познакомить студентов с размещениями (без повторений и с
повторениями), дать соответствующие формулы вычисления числа размещений;

- учить решать задачи на размещения;

- развивать комбинаторное мышление, математическую речь, интерес к предмету.

Ход занятия

1. Сообщение темы и цели занятия

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

⇐ Предыдущая12345678Следующая ⇒

Поделиться: