Урок 32. Сочетания с повторениями

Конспект урока

Алгебра и начала математического анализа, 11 класс

Урок №32. Сочетания с повторениями.

Перечень вопросов, рассматриваемых в теме:

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

Глоссарий по теме

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

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

Перестановки элементов одного и того же множества отличаются только порядком расположения элементов друг относительно друга.

Pn=1∙2∙3∙4∙…∙(n-1)∙n

Если элементы множества расставлены по кругу, то это так называемые перестановки n элементов по кругу. Их количество равно (n — 1)!

Если множество содержит одинаковые элементы, то подсчет количества перестановок с повторениями производится следующим образом: элементы первого типа можно переставить между собой (n1 – количество таких элементов) способами, второго типа – способами, k -го типа — способами. Значит, число перестановок с повторениями меньше n! в раз, чем число перестановок без повторения, то есть это число равно

Размещения

В комбинаторике упорядоченные подмножества данного множества называются «размещениями из n элементов на k мест» или, проще: «размещениями из n по k».

Выбор m элементов из множества, содержащего n элементов с повторением и с упорядочиванием выбранных элементов в последовательную цепочку называют размещениями с повторениями из n элементов по m , а общее число обозначают

В комбинаторике подмножества данного множества называются «сочетаниями из n по k элементов» или, проще: «сочетания из n по k».

Основная литература:

Колягин Ю.М., Ткачёва М.В., Фёдорова Н.Е.,   Шабунин М.И. под ред. Жижченко А.Б. Алгебра и начала математического анализа. 11 класс: учеб. для общеобразоват. учреждений: базовый и профил. Уровни – 2-е изд. – М.: Просвещение, 2010. – 336 с.: ил. – ISBN 978-5-09-025401-4

Открытые электронные ресурсы:

Решу ЕГЭ образовательный портал для подготовки к экзаменам https://ege.sdamgia.ru/

Теоретический материал для самостоятельного изучения

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

Считаем, что aab, aba или baa одинаковые наборы

aba и abc –разные наборы

Изучение этого случая начнем с простого примера:

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

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

Зашифруем каждый заказ нулями и единицами. Сначала напишем столько единиц, сколько заказали пирожных первого вида. Потом напишем ноль. Дальше напишем столько единиц, сколько заказали пирожных второго вида. Затем опять ноль. Опять напишем столько единиц, сколько заказали пирожных третьего вида.

Каждый «зашифрованный» заказ представляет собой комбинацию из пяти 1 и двух 0. Число выбора заказа равно числу перестановок с повторениями элементов множества {1,1,1,1,1,0,0}. В этом множестве 1 повторяется пять раз и 0 – два раза

Применим формулу для числа перестановок с повторениями

Значит, способов заказать набор пирожных 21.

Выбор m элементов из множества, содержащего n элементов с повторением и без упорядочивания выбранных элементов в последовательную цепочку называют сочетаниями с повторениями из n элементов по m

Пусть множество содержит n элементов, а выборка будет содержать m элементов. Аналогично тому, как мы делали в примере, зашифруем каждую выборку единицами и нулями.

Число единиц равно числу выбираемых элементов, то есть m. Поскольку всего различных элементов в множестве n, то мы должны поставить между единицами (n-1) «перегородку», то есть (n-1) нулей. Число размещений с повторениями равно числу перестановок с повторениями элементов полученного множества из m единиц и (n-1) нулей

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

Примеры и разбор решения заданий тренировочного модуля

Пример 1.

Сколько существует треугольников, длины сторон которых принимают одно из следующих значений: 5, 6, 7, 8, 9?

Решение:

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

Ответ: 35

Пример 2.

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

Решение. Это задача о числе сочетаний из пяти цифр по одному, по два, по три, по четыре и по пяти с повторениями в каждом случае.

Поскольку  ,  ,  ,  , , то существует 5+15+35+70+126=251 чисел, удовлетворяющих условию задачи.

Ответ: 126