алгебра

Поурочные разработки по Алгебре и началам анализа 11 класс к УМК А. Г. Мордковича - 2011 год

Сочетания и размещения - Элементы математической статистики, комбинаторики и теории вероятностей

Цель: рассмотреть основные понятия комбинаторики.

Ход уроков

I. Сообщение темы и цели уроков

II. Повторение и закрепление пройденного материала

1. Ответы на вопросы по домашнему заданию (разбор нерешенных задач).

2. Контроль усвоения материала (письменный опрос).

Вариант 1

1. Достоверное событие и его вероятность.

2. Найти вероятность того, что на игральной кости выпадет четное число очков.

3. Найти вероятность того, что при подбрасывании двух костей суммарное число очков окажется равным 8.

Вариант 2

1. Невозможное событие и его вероятность.

2. Найти вероятность того, что на игральной кости выпадет нечетное число очков.

3. Найти вероятность того, что при подбрасывании двух костей суммарное число очков окажется равным 9.

III. Изучение нового материала

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

Сначала рассмотрим некоторые задачи комбинаторики.

Пример 1

Сколько существует двузначных чисел?

При образовании чисел используются десять цифр: 0, 1, 2, ..., 9. Так как число двузначное, то число десятков может принимать одно из девяти значений: 1, 2, 3, ..., 9. Число единиц принимает те же значения, и еще 0 (10 вариантов).

Если цифра десятков 1, то цифра единиц может быть любой из десяти: 0, 1, 2, ..., 9. Если цифра десятков 2, то цифра единиц вновь может быть любой из десяти: 0, 1, 2, ..., 9, и т. д. Тогда получаем, что возможно 9 ∙ 10 = 90 вариантов (чисел). Разумеется, их легко выписать: 10, 11, 12, ..., 99.

Пример 2

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

Очевидно, что на первом (соответственно, и на последнем) месте может стоять любая цифра (кроме нуля) - 9 вариантов. На втором (соответственно и на предпоследнем) месте может стоять любая цифра - 10 вариантов. На третьем месте (в середине) также может стоять любая цифра - 10 вариантов. Тогда получаем, что возможно 9 ∙ 10 ∙ 10 = 900 вариантов (чисел).

Из рассмотренных примеров можно сформулировать комбинаторное правило умножения. Пусть имеется n элементов, и надо выбрать из них один за другим k элементов. Если первый элемент можно выбрать n₁ способами, после чего второй элемент можно выбрать n₂ способами из оставшихся, затем третий элемент можно выбрать n₃ способами из оставшихся и т. д., то число способов, которыми могут быть выбраны все к элементов, равно произведению 

Пример 3

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

Начнем распределять медали с наименее ценной. Бронзовую медаль может получить одна из 10 команд (10 вариантов). После этого серебряную медаль получит одна из оставшихся 9 команд (9 вариантов). Наконец, золотую медаль получает одна из оставшихся 8 команд (8 вариантов). Следовательно, общее число способов, которыми могут быть распределены золотая, серебряная и бронзовая медали, равно 10 ∙ 9 ∙ 8 = 720.

Пример 4

В 9 классе изучается 10 предметов. Во вторник должны быть проведены 6 различных уроков. Сколькими способами можно составить расписание занятий на вторник?

По аналогии с примером 3 на первом уроке изучается любой из 10 предметов, на втором уроке - любой из оставшихся 9 предметов, на третьем уроке - любой из оставшихся 8 предметов и т. д. Таким образом, расписание можно составить 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 = 151 200 способами.

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

Введем некоторые необходимые понятия.

Соединением из n элементов по k назовем выборку k элементов из n различных элементов (k ≤ n).

Пример 5

Пусть даны три различных элемента (n = 3): а, b и с. Перечислим соединения из трех элементов по одному (k = 1): а, b, с;

соединения из трех элементов по два (k = 2): ab, bа, ас, са, bc, cb;

соединения из трех элементов по три (k = 3): abc, асb, bас, bса, сab, cba.

В зависимости от того, имеет ли значение порядок элементов или нет, а также от того, входят ли в соединение все n элементов или только k (при условии k < n), различают три вида соединений: перестановки, размещения, сочетания. Комбинаторика изучает число таких соединений (но не сами соединения).

Сначала рассмотрим простейший вид соединений - перестановки. Соединения, каждое из которых содержит n различных элементов, взятых в определенном порядке, называются перестановками из n элементов. Другими словами, имеется n позиций (мест), которые надо заполнить n различными элементами:

Пример 6

Рассмотрим перестановки из трех элементов: а, b, с.

Необходимо расположить на три позиции три элемента.

Если на первую позицию поставить элемент а, то возможны перестановки: abc, асb.

Если на первую позицию поставить элемент b, то возможны перестановки: bас, bса.

Если на первую позицию поставить элемент с, то возможны перестановки: cab, cba.

Видно, что число перестановок из трех элементов равно 6.

Вообще, число перестановок из n элементов обозначают символом Р_n (читается: Р из n). В данном примере P₃ = 6.

Выведем формулу числа Р_n перестановок из n элементов. Используем комбинаторное правило умножения. На первую позицию можно поместить любой из n элементов, на вторую позицию - любой из оставшихся (n - 1) элементов, на третью позицию - любой из оставшихся (n - 2) элементов и т. д. В результате получим:  Расположим множители в порядке возрастания. Имеем: 

Для произведения первых n натуральных чисел используют символ n! (читается: n факториал), т. е.  При этом 1! = 1 (и 0! = 1). Тогда число всевозможных перестановок из n элементов вычисляется по формуле 

Пример 7

Вычислим:

 (см. пример 6);

 (где m ∈ N).

Пример 8

Решим уравнение  (где n ∈ N).

Упростим левую часть уравнения, пользуясь определением факториала:  или  или  или 0 = n² – 5n + 6. Корни этого квадратного уравнения n = 2 и n = 3 действительно являются натуральными числами и решениями данного уравнения.

Пример 9

Сколькими способами можно расставить на полке семь различных книг?

Число таких способов равно числу перестановок из семи элементов, т. е. 

Пример 10

Имеются 10 различных книг, три из которых - справочники. Сколькими способами можно расставить эти книги на полке так, чтобы все справочники стояли рядом?

Так как справочники должны стоять рядом, то будем рассматривать их как одну книгу. Тогда на полке надо расставить 10 - 3 + 1 = 8 книг. Это можно сделать Р₈ способами. Для каждой из полученных комбинаций можно сделать Р₃ перестановок справочников. Поэтому число способов расположения книг на полке равно произведению: 

Пример 11

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

Из пяти цифр можно получить Р₅ перестановок. Из них надо исключить те перестановки, которые начинаются с нуля (т. к. первая цифра в числе не может быть нулем). Число таких перестановок равно Р₄. Тогда получаем:  пятизначных чисел.

Размещения

Соединения, отличающиеся друг от друга составом элементов или их порядком, каждое из которых содержит к элементов, взятых из n различных элементов, называют размещениями из nэлементов по k (k < n). Другими словами, из n элементов выбирают k элементов и размещают их на k позиций. Число размещений из n элементов по k обозначают символом А^k_n (читается: А из n по k).

Пример 12

Рассмотрим три элемента а, b, с и выделим две позиции (два места). Будем размещать эти элементы на два места, учитывая порядок следования элементов.

Получаем размещения: ab, bа, ас, са, bc, cb. Число этих размещений А²₃ = 6.

Получим формулу для вычисления числа размещенийn элементов по k (k < n), т. е. А^k_n. Опять учтем комбинаторное правило умножения. На первое место можно поставить любой из nэлементов, на второе место - любой из оставшихся (n - 1) элементов и т. д. Тогда на k-е место можно поставить любой из  оставшихся элементов. Получаем:  Удобнее записать эту формулу в другом виде. Для этого умножим и разделим правую часть равенства на (n - k)! Получаем:  Итак, имеем: 

Очевидно, что при k = n размещения можно рассматривать как перестановки и  (учтено, что 0! = 1).

Пример 13

Сколько существует трехзначных чисел, в которых цифры различные и нечетные?

Нечетных цифр пять: 1, 3, 5, 7, 9. Их надо разместить на три позиции. Поэтому количество искомых чисел равно числу размещений 

Пример 14

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

Из шести данных цифр можно составить А₆³ чисел, но среди них будут и трехзначные числа, начинающиеся с нуля (чего, естественно, быть не может). Посчитаем количество таких чисел. В них на первом месте стоит нуль. Значит, на оставшиеся две позиции размещают оставшиеся пять цифр. Поэтому таких чисел будет А₅². Следовательно, искомых чисел можно получить: 

Пример 15

Сколько чисел с разными цифрами можно составить из цифр 0, 1, 2, 3, 4?

Учтем предыдущий пример. Из пяти цифр можно составить A⁵₅ пятизначных чисел, в том числе и тех, которые начинаются с нуля (их число A⁴₄). Поэтому истинно пятизначных чисел будет  Из пяти цифр можно составить А₅⁴ четырехзначных чисел, из них начинаются с нуля А₄³ чисел. Поэтому истинно четырехзначных чисел будет  Аналогично находим количество истинно трехзначных чисел:  истинно двузначных чисел:  —и однозначных чисел - 5. Всего можно составить 96 + 96 + 48 + 16 + 5 = 261 пятизначных, четырехзначных, трехзначных, двузначных и однозначных числа.

Пример 16

Вычислим 

Используем формулу для числа размещений и получим: 

Пример 17

Найдем натуральное значение n, для которого выполнено условие 

Используем формулы для числа размещений и числа перестановок и запишем условие:  или  или  или  или 2 = (n - 2)!. Очевидно, что n - 2 = 2 и n = 4.

Сочетания

Соединения, отличающиеся друг от друга по крайней мере одним элементом, каждое из которых содержит k элементов, выбранных из n различных элементов, называют сочетаниями из nэлементов по k. Порядок следования элементов неважен. Число сочетаний из n элементов по k обозначают символом С^k_n (читается: С из n по k).

Пример 18

Рассмотрим три элемента а, b, с и выделим две позиции (два места). Будем расставлять эти элементы на два места независимо от порядка их следования. Получаем сочетания: ab, ас, bс. Число этих сочетаний С₃² = 3.

Получим формулу для вычисления числа сочетаний n элементов по k (k ≤ n), т. е. С^k_n. Допустим, имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно С^k_n. В каждом таком сочетании можно выполнить Р_k перестановок. В результате получим все размещения, которые можно составить из nэлементов по k (их число равно A^k_n). Получили равенство  откуда  Используя формулы для A^k_n и Р_k, имеем: 

Пример 19

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

Используем формулу для числа С^k_n сочетаний из n элементов по k и получим  способов.

Пример 20

Найти число диагоналей n-угольника.

Имеем n точек плоскости, из которых никакие три не лежат на одной прямой. Соединим эти точки попарно всеми возможными способами. Будем иметь  отрезков. Из этих отрезков n отрезков являются сторонами многоугольника. Тогда диагоналей будет:  В соответствии с полученной формулой имеем: у треугольника 0 диагоналей, у четырехугольника 2 диагонали, у пятиугольника 5 диагоналей, у шестиугольника 9 диагоналей и т. д.

Пример 21

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

Одна точка пересечения диагоналей возникает за счет двух диагоналей, т. е. четырех вершин. Их можно выбрать  Таким образом, нашли число точек пересечения диагоналей. По этой формуле получаем: у четырехугольника 1 точка пересечения диагоналей, у пятиугольника 5 точек, у шестиугольника 15 точек и т. д.

Пример 22

У Кати есть семь разных книг по математике, у Коли девять книг по физике. Сколькими способами они могут обменяться пятью книгами?

Катя может выбрать пять книг из семи  способом, Коля (независимо от Кати) может выбрать пять книг из девяти  способами. Итого возможных вариантов обмена: 

Пример 23

Из двух математиков и десяти физиков надо составить комитет из восьми человек. В комитет должен входить хотя бы один математик. Сколькими способами это можно сделать?

В гаком комитете могут быть:

а) 1 математик и 7 физиков;

б) 2 математика и 6 физиков.

Обсудим эти ситуации.

а) Одного математика из двух можно выбрать  способами, 7 физиков из 10 можно выбрать  способами. Всего же можно выбрать этот состав комитета  способами.

б) Двух математиков из двух можно выбрать  способом, 6 физиков из  способами.

Общее число выборов такого комитета:  способов.

Так как случаи а и б происходят независимо (т. е. вместе не могут быть реализованы), то использовалось еще одно правило комбинаторики - правило сложения. Если первое действие можно выполнить n₁ способами, второе действие - n₂ способами, ..., k-е действие – n_k способами, то действие, состоящее в том, что выполняется одно любое из действий, можно выполнить  способами. На это правило рассмотрим еще пример.

Пример 24

Сколько существует делителей числа 210?

Разложим число 210 на простые множители: 210 = 2 ∙ 3 ∙ 5 ∙ 7. Число делителей, состоящих из произведения двух простых множителей, равно  (числа 6, 10, 14, 15, 21, 35), из произведения трех простых множителей  (числа 30, 42, 70, 105). Кроме того, есть четыре простых делителя (числа 2, 3, 5, 7), а также само число 210 и 1. Всего получаем 6 + 4 + 4 + 1 + 1 = 16 делителей числа 210.

Пример 25

Найдите натуральные значения n, удовлетворяющие условию 

Используем формулу для нахождения числа сочетаний из n элементов по k. Получим уравнение:  или  или  или 0 = 3n² – 25n + 8. Корни этого квадратного уравнения п = 1/3 (ненатуральное число) и n = 8.

Заметим, что до сих пор рассматривались виды соединений с различными n элементами. Но некоторых из этих элементов могут быть и одинаковыми. Тогда все приведенные формулы для числа перестановок Р_n, числа размещений А^k_n и числа сочетаний С^k_n меняются. Не будем углубляться в рассмотрение соединений с одинаковыми элементами. Но для иллюстрации рассмотрим, например, перестановки с одинаковыми элементами.

Перестановки из n элементов, в каждую из которых входят n₁ одинаковых элементов одного типа, n₂ одинаковых элементов другого типа, ..., n_k одинаковых элементов k-то типа (при этом ), называют перестановками из n элементов с повторениями. Их число определяется по формуле 

Пример 26

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

Всего имеется 2 + 4 + 6 = 12 лампочек. Число способов их расположения 

IV. Контрольные вопросы

1. Соединение из n элементов по k.

2. Перечислите три вида соединений.

3. Дайте определение перестановок из n элементов.

4. Понятие факториала (n!).

5. Число перестановок Р_n из n элементов.

6. Дайте определение размещений.

7. Приведите формулу для вычисления числа размещений.

8. Определение сочетаний из n элементов по k.

9. Число С^k_n сочетаний из n элементов по k.

10. Перестановки из n элементов с повторениями.

11. Число  перестановок из n элементов с повторениями.

V. Задание на уроках

§ 52, № 1 (а, б); 2 (а, б); 3 (в, г); 4 (а, г); 5 (а, в); 6 (б, г); 8; 10 (а, б); 12 (в, г); 14; 16; 18; 20.

VI. Задание на дом

§ 52, № 1 (б, г); 2 (в, г); 3 (а, б); 4 (б, в); 5 (б, г); 6 (а, в); 9; 10 (в, г); 12 (а, б); 15; 17; 19.

VII. Подведение итогов уроков