Практическое занятие №3. Решение комбинаторных задач

Практическое занятие №3. Решение комбинаторных задач.

Цель занятия: приобретение навыков решения комбинаторных задач, подсчет числа перестановок, размещений и сочетаний с повторениями.

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

1.        Дискретная математика: учебник для студентов учреждений сред. проф.

образования /М.С. Спирина, П.А. Спирин.- 7-е изд., стер.- М.: Издательский центр «Академия», 2014 г.

2.        Дискретная математика. Курс лекций и практических занятий./ С.Д. Шапорев – СПб.: БХВ – Петербург, 2010 г.

3.        Видео урок https://www.youtube.com/watch?v=rL6sKh1_pPw  

4.        Комбинаторика. Задача 10. Подготовка к ЕГЭ по информатике. Видеокурс. https://yandex.ru/video/preview/11018745585958044072  

5.        Комбинаторные задачи в информатике https://videouroki.net/razrabotki/kombinatornye-zadachi-vinformatike.html?ysclid=lod7uqzl8u528198316  

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

https://www.youtube.com/watch?v=cvQiPIB62CM  

7.        Комбинаторика. Основные формулы (перестановки, сочетания, размещения) и примеры...  https://yandex.ru/video/preview/16734105567710293112  

8.        02 Комбинаторика Задачи   https://www.youtube.com/watch?v=eiwZY1oXGvo  

КОНТРОЛЬНЫЕ 

1.                      Дайте определение комбинаторных объектов.

2.                      Сформулируйте правило суммы, запишите формулу.

3.                      Сформулируйте правило произведения, запишите формулу.

4.                      Что называется n-факториалом? Запишите чему равен n!

5.                      Что называется комбинаторикой?

6.                      Что называется перестановками? Запишите формулу для вычисления числа перестановок.

7.                      Что называется размещениями? Запишите формулу для вычисления числа размещений.

8.                      Что называется сочетаниями? Запишите формулу для вычисления числа сочетаний.

9.                      Сформулируйте основную задачу комбинаторики.

10.                 Запишите формулу для вычисления числа перестановок с повторениями.

11.                 Запишите формулу для вычисления числа размещений с повторениями.

12.                 Запишите формулу для вычисления числа сочетаний с повторениями.

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

Комбинаторные задачи (примеры)

Задача

Сколькими способами можно выбрать гласную и согласную буквы слова «полка»? 

Решение: в этом слове две гласные буквы (о, а) и три согласные (п, л, к). Каждый искомый выбор задается картежом (а(1), а(2)), где а(1) – гласная буква, а(2) – согласная. Так как а(1) можно выбрать двумя способами, а а(2) тремя способами, то кортеж (а(1), а(2)) можно по правилу произведения выбрать 2*3=6 способами. Ответ: 6 способов.

Задача

 Продают две игральные кости (каждая кость – кубик с отмеченным на его гранях точками). Одной до шести, причем на различных гранях разное число точек. Сколько различных пар точек может появиться на верхних гранях костей?

 Решение: Для каждого случая составим таблицу вариантов: N = 3*3 =9  N = 3*4 = 12 Ответ: 1) N = 9; 2) N = 12.

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

Задача

 Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно? 

Решение: Решим задачу с помощью полного графа с четырьмя вершинами А,Б,В,Г. Обозначенными первыми буквами имени каждого из мальчиков. В полном графе проводятся всевозможные ребра. В данном случае отрезки ребер обозначают органные шахматные партии. Из рисунка видно, что граф имеет 6 ребер, значит, и партий было сыграно 6. Ответ: 6 партий.

Задача

Антон, Борис, Василий купили 3 билета на 1,2,3 места первого ряда на футбольный мачт. Сколькими способами они могут занять имеющиеся места? 

Решение: на 1-е место может сесть любой из трех друзей, на 2 любой их двух оставшихся, а на 3 последний. Сказанное изобразим с помощью дерева, помещая в вершины графа первые буквы А,Б и В: 1 место 2 место 3 место упорядочная тройка друзей. Ответ: 6.

 Задача  

Из города А в город В ведут 5 дорог, а из города В в город С – 3 дороги. Сколько путей, проходящих через В, ведут из АВС?

 Решение: Каждый путь школою видов задается картежом (а(1), а(2)), где а(1) – один из путей, соединяющих В и С. Так как по условию а(1) можно выбрать 5 способами, а(2) – 3способами, то картеж (а(1), а (2)) можно по правилу произведения составить 5*3 = 15 способами. Ответ: 15 путей.

 Задача 

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

Решение: Эту задачу тоже можно решить по правилу произведения. Перчатка на левую руку может быть выбрана 6 способами. После того как она выбрана, перчатку на правую руку можно выбрать лишь 5 способами. (Размеры перчаток  должны быть разными). Поэтому всего имеет 6*5 =  30 способов. Ответ: 30 способов.   Задача

сколькими способами могут быть распределены золотая и серебренная медали по итогам первенства по футболу, если число команд 12.  Решение: На золотую медаль претендуют 12 команд, на серебренную 11 команд. (одна получит золотую медаль). По правилу произведения получаем 12 * 11 = 132 способа. Ответ: 132 способа.

Задачи, на перебор вариантов происходящих событий.

Задача 

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

1       способ: Перечислим возможные варианты.

2       способ: Дерево возможностей

3       способ: Правило умножения заключается в том, что для того, чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В, т.е. в нашей задаче имеется 3 элемента: первое, можно выбрать 3 раза, второе – 3 раза и третье – 2раза, получаем: 3х3х2=18.Ответ: 18.

Задача

Мисс Марпл, расследуя убийство, заметила отъезжающее от дома мистера Дэвидсона такси. Она запомнила первую цифру «2». В городке номера машин были трехзначные и состояли из цифр 1, 2, 3, 4 и 5. скольких водителей, в худшем случае, ей придется опросить, чтобы найти настоящего убийцу?

Используя правило умножения, получаем: 5*5=25.Ответ: 25 водителей.

Задача

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

Решение. Первую цифру трехзначного числа можно выбрать четырьмя способами, т.к. после выбора остается три, то вторую цифру можно выбрать из оставшихся цифр уже тремя способами. Наконец, третью цифру можно выбрать двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 4 * 3 * 2=24.Ответ: 24.

Задача 

Сколько четных двузначных чисел можно составить из цифр 0, 2, 3, 6, 7, 9? Используя правило умножения, получаем: 5*3=15 Ответ: 15

Задача 

Свете на день рождения подарили 4 плюшевых игрушки, 2 мяча и 5 кукол. Мама положила все игрушки в большую коробку. Сколькими способами Света сможет достать из коробки 1 плюшевую игрушку, 1 мяч и 1 куклу?Используя правило умножения, получаем: 2*4*5=40.Ответ:40.

Задачи на перестановки.

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке. Число перестановок из n элементов обозначается символом Рn (Р из n элементов). Например. Задача 

в книжном шкафу на полке стоят 3 книги, как  эти книги можно переставить? 

Р₃= 3*2*1= 6 = 3!

Задача 

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

Р₅ = 5! = 5*4*3*2*1 = 120.

Задача

 Сколькими способами могут быть расставлены 8 участниц, финального забега, на восьми беговых дорожках? 

Число способов равно числу перестановок из 8 элементов. По формуле числа перестановок находим, что Р₈=8! = 1*2*3*4*5*6*7*8 = 40320.

Задача

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

Решение: из цифр 0,2,4,6 можно получить Р4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0, т.к. натуральное число не может начинаться с цифры 0. Число таких перестановок равно Р₃.

значит, искомое число четырехзначных чисел равно Р₄-Р₃ = 4!-3! = 24 – 6= 18.

Задачи на размещения.

Размещением из n элементов по k (k меньше или равно n) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из данных n элементов. Обозначение:  A_n^k ( читают: «А из n по k).

 Например: Пусть имеется три шара и две пустых ячейки. В пустые ячейки можно разместить по два шара.

  Решение: из трех элементов по два будут наборы (1,2), (2,1), (1,3), (3,1), (2,3), (3,2). Размещения считаются различными, если они отличаются самими элементами или порядком их расположения. Например: (1,2), (2,1), (1,3), (3,1) в нашем примере. Число размещений можно найти, не выписывая сами размещения. Будем рассуждать так: первый элемент можно выбрать тремя способами, т.к. им может быть любой из трех, для каждого выбранного первого элемента можно двумя способами выбрать второй. В результате получаем: A₃² = 3*2 = 6.

Задача 

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

 Решение: A₈⁴ = 8*7*6*5 = 1680.

Задача

 В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день? 

Решение: А₁₀⁵=10*9*8*7*6 = 30240 способов.

Задача 

В 9 классе 15 предметов. Завучу школы нужно составить расписание на субботу, если в этот день 5 уроков. Сколько различных вариантов расписания можно составить, если все уроки различны? 

Решение: из 15 предметов 5 любых можно выбрать А₁₅⁵= 15*14*13*12*11= 360360.

Задача

 Сколькими способами можно составить трехцветный флаг из полос разной ширины, если имеются материи из 8 тканей?

 Решение: А₈³=8*7*6 = 336.

Задачи на сочетания.

Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов. Обозначение: C_n^k (читают С из n по k). 

Задача 

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

Решение: из трех элементов (1;2;3) по два будут наборы (1,2),(1,3),(2,3). В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания различны, если отличаются друг от друга хотя бы одним элементом. Например: (1,2),(1,3). В нашем примере, в каждом сочетании выполнимы все перестановки. Число таких перестановок равно Р2. В результате получим все возможные комбинации из 3 элементов по 2, которые отличаются либо самими элементами, либо порядком элементов, т.е.  все размещения из 3 элементов по 2. всего мы получим A₃² размещений. Значит если количество размещений разделить на количество перестановок, получим

² A³2 . количество сочетаний из трех элементов по два.  Отсюда C₃ 

P₃

Задача

 из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

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

A³

C₁₅3    ₁₅  151413  ₄₅₅.

               P₃                123

Задача

На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек? 

Решение: В этой задаче нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. В каждом сочетании выполнимы 5 перестановок т.е.Р5= 1*2*3*4*5, в результате получим все возможные комбинации из 20 элементов по 5: А₂₀⁵=20*19*18*17*16.

A⁵

C₂₀5   ₂₀  2019181716 ₁₅₅₀₄ P₅ 12345

ВАРИАНТЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ВЫБИРАЮТСЯ СОГЛАСНО СПИСОЧНОГО СОСТАВА В ЖУРНАЛЕ:

Вариант 1 – номера по журналу 1; 7; 13; 19

Вариант 2 – номера по журналу 2; 8; 14; 20 Вариант 3 – номера по журналу 3; 9; 15; 21

Вариант 4 – номера по журналу 4; 10; 16; 22

Вариант 5 – номера по журналу 5; 11; 17; 23

Вариант 6 – номера по журналу 6; 12; 18; 24

Ход работы.

Вариант 1.

Задание №1.

Пусть B студентов посещают математический кружок; C – физический; D – не посещают ни одного из кружков. A – количество студентов, которые посещают и математический, и физический кружок. Сколько всего студентов? Сколько студентов посещают только математический кружок?

|A|=8; |B|=31; |С|=12; |D|=5;

Задание №2.

Сколькими способами из A студентов можно выбрать делегацию, если делегация состоит из B студентов? |A|=42; |B|=8.

Задание №3.

Сколько четырехзначных кодов можно составить из 9 цифр? Задание №4

На собрании должны выступить 4 человека A,B,C,D. Сколькими способами их можно разместить в списке ораторов, если B не может выступить до того момента, пока не выступит A.

Задание №5.

Сколькими способами могут разместиться A покупателей в очереди в кассу. |A|=7 Задание №6.

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

КОМБИНАТОРИКА

Задание №7.

Сколькими способами можно выбрать A одинаковых или разных пирожных в кондитерской, где есть B разных сортов пирожных. A=5; B=12

                         Вариант                                                                                                  2.

Задание №1.

Пусть B студентов посещают математический кружок; C – физический; D – не посещают ни одного из кружков. A – количество студентов, которые посещают и математический, и физический кружок. Сколько всего студентов?

Сколько студентов посещают только математический кружок?

|A|=5; |B|=25; |С|=9; |D|=2; Задание №2.

Сколькими способами из A студентов можно выбрать делегацию, если делегация состоит из B студентов? |A|=51; |B|=10.

Задание №3.

Сколько трехзначных кодов можно составить из 10 цифр?

Задание №4

На собрании должны выступить 3 человека A,B,C. Сколькими способами их можно разместить в списке ораторов, если B не может выступить до того момента, пока не выступит A.

Задание №5.

Сколькими способами могут разместиться A покупателей в очереди в кассу. |A|=8 Задание №6.

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

ДИСКРЕТНЫЙ

Задание №7.

Сколькими способами можно выбрать A одинаковых или разных пирожных в кондитерской, где есть B разных сортов пирожных. A=4; B=10

Вариант 3.

Задание №1.

Пусть B студентов посещают математический кружок; C – физический; D – не посещают ни одного из кружков. A – количество студентов, которые посещают и математический, и физический кружок. Сколько всего студентов?

Сколько студентов посещают только математический кружок?

|A|=7; |B|=30; |С|=10; |D|=4; Задание №2.

Сколькими способами из A студентов можно выбрать делегацию, если делегация состоит из B студентов? |A|=45; |B|=9.

Задание №3.

Сколько четырехзначных кодов можно составить из 8 цифр? Задание №4

На собрании должны выступить 4 человека A,B,C,Е. Сколькими способами их можно разместить в списке ораторов, если С не может выступить до того момента, пока не выступит В.

Задание №5.

Сколькими способами могут разместиться В покупателей в очереди в кассу. |В|=10

Задание №6.

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

ПЕРЕСТАНОВКИ

Задание №7.

Сколькими способами можно выбрать A одинаковых или разных пирожных в кондитерской, где есть B разных сортов пирожных. A=6; B=11

          Вариант                                                                                                           4.

Задание №1.

Пусть B студентов посещают математический кружок; C – физический; D – не посещают ни одного из кружков. A – количество студентов, которые посещают и математический, и физический кружок. Сколько всего студентов?

Сколько студентов посещают только математический кружок?

|A|=9; |B|=27; |С|=15; |D|=4; Задание №2.

Сколькими способами из A студентов можно выбрать делегацию, если делегация состоит из B студентов? |A|=40; |B|=11.

Задание №3.

Сколько трехзначных кодов можно составить из 9 цифр?

Задание №4

На собрании должны выступить 3 человека B,C, Е. Сколькими способами их можно разместить в списке ораторов, если С не может выступить до того момента, пока не выступит В.

Задание №5.

Сколькими способами могут разместиться С покупателей в очереди в кассу. |С|=11 Задание №6.

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

КОДИРОВАННЫЙ

Задание №7.

Сколькими способами можно выбрать С одинаковых или разных пирожных в кондитерской, где есть К разных сортов пирожных. С=5; К=9

                         Вариант                                                                                                  5.

Задание №1.

Пусть B студентов посещают математический кружок; C – физический; D – не посещают ни одного из кружков. A – количество студентов, которые посещают и математический, и физический кружок. Сколько всего студентов?

Сколько студентов посещают только математический кружок?

|A|=11; |B|=44; |С|=33; |D|=7; Задание №2.

Сколькими способами из A студентов можно выбрать делегацию, если делегация состоит из B студентов? |A|=55; |B|=12.

Задание №3.

Сколько четырехзначных кодов можно составить из 7 цифр? Задание №4

На собрании должны выступить 4 человека B,C, Е, М. Сколькими способами их можно разместить в списке ораторов, если Е не может выступить до того момента, пока не выступит С.

Задание №5.

Сколькими способами могут разместиться К покупателей в очереди в кассу. |К|=9 Задание №6.

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

ДИАГРАММА

Задание №7.

Сколькими способами можно выбрать A одинаковых или разных пирожных в кондитерской, где есть B разных сортов пирожных. A=4; B=10

Вариант 6.

Задание №1.

Пусть B студентов посещают математический кружок; C – физический; D – не посещают ни одного из кружков. A – количество студентов, которые посещают и математический, и физический кружок. Сколько всего студентов?

Сколько студентов посещают только математический кружок?

|A|=8; |B|=32; |С|=23; |D|=7; Задание №2.

Сколькими способами из A студентов можно выбрать делегацию, если делегация состоит из B студентов? |A|=34; |B|=9.

Задание №3.

Сколько пятизначных кодов можно составить из 8 цифр?

Задание №4

На собрании должны выступить 4 человека A,B,C,D. Сколькими способами их можно разместить в списке ораторов, если С не может выступить до того момента, пока не выступит В.

Задание №5.

Сколькими способами могут разместиться В покупателей в очереди в кассу. |В|=12 Задание №6.

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

РАЗМЕЩЕНИЯ

Задание №7.

Сколькими способами можно выбрать A одинаковых или разных пирожных в кондитерской, где есть B разных сортов пирожных. A=5; B=12.