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

Цель: обсудить последний вид соединений - сочетания.

Ход урока

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

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

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

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

Вариант 1

1. Приведите формулу для вычисления числа Рn перестановок из n элементов.

2. Найдите натуральные n, удовлетворяющие условию Аn2 = 6.

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

Вариант 2

1. Приведите формулу для вычисления числа Аnk размещений k элементов из n.

2. Найдите натуральные n, удовлетворяющие условию An2 = 12.

3. Из 28 спортсменов надо выбрать капитана команды и его заместителя. Сколькими способами это можно сделать?

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

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

Число сочетаний из n элементов по k обозначают символом Сnk (читается: С из n по k).

Пример 1

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

Получим формулу для вычисления числа сочетаний n элементов по k (k ≤ n), т. е. Сnk.

Допустим, имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно Сnk. В каждом таком сочетании можно выполнить Pk перестановок. В результате получим все размещения, которые можно составить из n элементов по k (их число равно Ank). Получили равенство Ank = Сnk · Рk, откуда

Используя формулу для Аnk и Pk, имеем:

Пример 2

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

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

Пример 3

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

Имеем n точек плоскости, из которых никакие три не лежат на одной прямой. Соединим эти точки попарно всеми возможными способами. Будем иметь

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

Пример 4

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

Одна точка пересечения диагоналей возникает за счет двух диагоналей, т. е. четырех вершин.

Их можно выбрать:

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

Пример 5

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

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

Итого возможных вариантов обмена:

Пример 6

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

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

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

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

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

Всего можно выбрать этот состав комитета способами.

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

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

Так как случаи а) и б) происходят независимо (т.е. вместе не могут быть реализованы), то использовалось еще одно правило комбинаторики - правило сложения. Если первое действие можно выполнить n1 способами, второе действие - n2 способами, ..., k-е действие – nk способами, то действие, состоящее в том, что выполняется одно любое из действий, можно выполнить n1 + n2 + ... + nk способами.

На это правило рассмотрим еще пример.

Пример 7

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

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

Всего получаем: 6 + 4 + 4 + 1 + 1 = 16 делителей числа 210.

Пример 8

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

Используем формулу для нахождения числа сочетаний из n элементов по k. Получим уравнение или или 10(n + 1) = 3(n2 – 5n + 6), или 0 = 3n2 – 25n + 8.

Корни этого квадратного уравнения n = 1/3 (не натуральное число) и n = 8.

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

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

Перестановки из n элементов, в каждую из которых входят n1 одинаковых элементов одного типа, n2 одинаковых элементов другого типа, ..., nk одинаковых элементов k-го типа (при этом n1 + n2 + ... + nk = n) называют перестановками из n элементов с повторениями.

Их число определяется по формуле

Пример 9

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

Всего имеется 2 + 4 + 6 = 12 лампочек.

Число способов их расположения:

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

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

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

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

4. Число Сn(n1, n2, ..., nk) перестановок из n элементов с повторениями.

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

№ 768; 770; 772; 774; 776 (а); 777; 779; 781.

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

№ 769; 771; 773; 775; 776 (б); 778; 780; 782.

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