Часть. Тест- разминка. №№ 1-8

Практическое занятие № 4 (дистанционно)

Тема:«Комбинаторные задачи»

Что используем:

Ø Записи лекции № 3 по теме.

Ø Другие доступные источники (учебники, интернет и т.д.)

Что должны знать:

· Определения, правила и формулы комбинаторики.

· Уметь рассуждать и применять правила и формулы комбинаторики при решении предложенных задач, (на повышенную отметку – в задачах со *.)

Как организуем работу:

ü Материалы для работы на практическое занятие № 4   см. в этом файле.

ü Задачи и инструктаж по выполнению дом. задания ДЗ-4 см. в этом же файле.

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

**************************************************************************

Материалы и задания  для работы на практическое занятие № 4.

 

     Изучив материалы лекции 3, ответьте на следующие контрольные вопросы:

 

1. Что такое комбинаторика? Какие задачи изучает комбинаторика?

2. Какие правила комбинаторики вы знаете? В чём заключается правило суммы? Правило произведения?

3. Что такое перестановка? Как найти количество возможных перестановок?

4. Что такое размещения без повторений? Как найти количество возможных размещений без повторений?

5. В чём основное отличие сочетания от размещения?

6. Как найти количество возможных сочетаний без повторений?

7. Какие формулы комбинаторики вы знаете?

8. Какая комбинация элементов множества получится, если в выбранном подмножестве:

а) элементы не повторяются, но при этом порядок следования элементов важен?

б) элементы не повторяются, и при этом порядок следования элементов не важен?

в) порядок следования элементов важен, но элементы могут повторяться?

 

????

Ø Можете ли вы сейчас ответить на все вопросы 1-8?

Ø Если – нет, то вернитесь к ним после работы над материалами практического занятия № 4.

****

ü Повторив материалы лекции по данной теме,

ü ответив на контрольные вопросы,

ü ознакомьтесь с рассуждениями и решениями задач №№1-11 и

ü  запишите их в тетрадь, выполнив необходимые вычисления по нужным формулам.

ü !!! Формулы, используемые в задачах, необходимо записывать для каждой задачи.

ü !!! Все вычисления делайте подробно.

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

                     Комбинации без повторения элементов.

****

Отчёт о работе на практическом занятии 4

представьте в виде таблицы ( Таблица 1 ), которую вышлите вместе с ДЗ.

В таблице запишите результаты по задачам 1-10.

Таблица 1

№	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
Основные формулы
Ответ

Задачи  №№1-11

№	Задача	Вопросы, указания и пояснения к решению
1	Сколько словарей надо установить в компьютер, чтобы можно было непосредственно выполнить переводы с любого из 3 языков: русского, английского, немецкого – на любой другой из этих трех языков?	Зашифруем переводы: РА – с русского на английский, РН – с русского на немецкий и т.д. Сколько видов переводов с русского языка вы нашли? Сколько всего видов переводов вы нашли? Перечислите их. Установим связь задачной ситуации с комбинаторными соединениями: чтобы узнать число необходимых словарей, нужно для 3-х языков взять по 2 необходимых словаря, т.е. по правилу умножения 3*2=6. Сформулируем задачу немного иначе: Сколькими способами можно из трёх языков выбрать 2 так, чтобы первым языком считать тот, с которого осуществляется перевод, а вторым – тот, на который осуществляется перевод. На языке комбинаторики: выбрать 2 элемента из 3-х с учётом порядка, эта ситуация соответствует   числу всех возможных размещений из 3 по 2, т.е.   =......
2	На книжной полке стоят 8 книг, причем 3 из них по математике. Сколькими способами можно расставить все эти книги, чтобы книги по математике оказались рядом?	?? Если бы всего было только 3книги (по математике), сколькими способами вы могли бы их поставить на полку? (С учётом порядка!)  Это перестановки из 3-х элементов, т.е......... ??  Узнаем, сколькими способами вы могли бы поставить на полку все 8 книг: это НО!Где там книги по математике – неизвестно! !! Чтобы книги по математике оказались рядом, не будем их разделять, а наоборот, «свяжем» их мысленно в один блок, и тогда можно считать, что !!  у нас не 8, а 6 элементов (5 других книг и блок математических), которые мы можем переставлять местами  способами.  Теперь учтём, что книги по математике внутри этого «блока» можно тоже переставить местами (сколькими способами?), тогда всего способов расставить все эти книги, чтобы книги по математике оказались рядом       6! * 3! =............
3	Сколько существует различных четырехзначных чисел с неповторяющимися цифрами?	В числе важно, какое место занимает цифра! На первое место можно поставить любую из 9 цифр (кроме нуля), на второе – любую из 9 (ПОЧЕМУ?), на третье – из 8, на четвёртое – из 7. Т.о., по правилу произведения получим всего различных четырехзначных чисел с неповторяющимися цифрами  9*9*8*7=........... Доп. вопросы. ??? Сколько всего существует различных четырехзначных чисел? В обычном числе цифры могут повторяться, поэтому....................................................................... Продолжите рассуждение, ответив на вопросы: сколько вариантов выбрать цифру на первое место? а на второе? на третье? на четвёртое? Т.о., по правилу произведения получим всего различных четырехзначных чисел 9*10*....*......=...........   ??? Что показывает разница этих результатов?
4	Сколько различных комбинаций букв можно получить при перестановке букв в слове: а) плот; б) окно; в) ананас; г) математика?     !!!!! В случаях  б) в) г) эти комбинации называют перестановками с повторениями.   Перестановки с повторениями.     ДЗ № 4 г).	При перестановке букв в слове а) плот: имеем 4 различные буквы, их можно переставить 4! способами, т.е................ При перестановке букв в слове б) окно: имеем 4 буквы, среди которых 2 повторяются. !!   Если бы были 4 различные буквы, их можно было бы переставить 4! способами, т.е. 24 способами. Занумеруем одинаковые буквы О1 и О2, тогда слова, в которых буквы О1 и О2 меняются местами, мы прочтём как одинаковые (??Сколько различных пар слов мы получим?) Т.о., среди этих 24 слов мы прочтём ровно 12 различных: 4!/ 2!= 12. При перестановке букв в слове в) ананас: имеем 6 букв, среди которых  буква А  повторяется 3 раза, буква Н – 2 раза, !! Если бы все 6 букв были различными, то их можно было бы переставить 6! способами, т.е........... способами, но за счёт того, что буквы повторяются, некоторые слова мы будем читать одинаково (?? Сколько одинаковых слов каждого вида получится?) Т.к. при этом повторяющиеся буквы «А» можно переставить   3!  способами, а повторяющиеся буквы «Н» можно переставить 2! способами, то одинаковых будет по 3!*2! =12 слов. Тогда различные комбинации букв можно получить способами, т.е................ Самостоятельно: Сколько различных комбинаций букв можно получить при перестановке букв в слове г) математика?
5	В метро 8 вагонов. Сколькими способами можно рассадить в поезде 3 человека при условии, что все они должны ехать в различных вагонах?	Для троих пассажиров выберем 3 вагона из 8 с учётом порядка, всего таких способов 8*7*6=.................
6	Сколькими способами можно распределить три предмета между 10 лицами, если не ограничивать число предметов, приходящихся на одного человека? Такие комбинации называют размещениями с повторениями.   Обозначение формула:	Считаем предметы различными. 1-й предмет можно отдать любому из 10 человек, 2-й – также любому из 10, и 3-й – тоже любому, значит, по правилу произведения, всего способов 10*10*10= 103 =1000.      Иначе говоря, на каждый из трёх предметов может претендовать любой из 10 человек, т.е. в задаче нужно выбрать 3-х человек из 10 с учётом порядка, но с повторениями (имеется в виду, что может повториться выбор человека, которому дают ещё какой-то предмет), это  способов.   Итак,                  = 103 =1000.
7	Для участия в соревнованиях тренер отбирает 5 спортсменов из двенадцати. Сколькими способами он может составить команду?     Для любознательных *: (см. ниже)	Команда – аналогично, группа, компания, друзья (все равны, нет распределения по значимости, по местам). Выбираем 5 человек из 12 без учёта порядка, значит, считаем количество сочетаний из 12 по 5: . ??? По каким формулам можно вычислить число СОЧЕТАНИЙ из n элементов по m: =............? ??? По какой формуле удобнее это сделать? =     или     Ответ:.......................   *Бином Ньютона и число сочетаний. ?? Как связаны число сочетаний и бином Ньютона?
8	Для участия в соревнованиях тренер отбирает 5 спортсменов из двенадцати. Сколькими способами он может составить команду, чтобы в ней были не менее 3-х девушек, если всего в группе 8 девушек? Правило умножения! Почему? Правило сложения!! Почему?	Выбираем 5 человек из 12, при этом должно быть не менее 3-х девушек, а их 8.  ???     Что значит, не менее 3-х девушек? Рассмотрим, какие случаи могут быть: 1 сл. 3 девушки, а значит ещё 2 юноши, т. е. сначала выберем 3 девушек из 8 девушек без учёта порядка – считаем количество сочетаний из 8 по 3, это  способов, затем выбираем 2 юношей из 4 юношей без учёта порядка, т.е, считаем количество сочетаний из 4 по 2: . !!!   При любом выборе группы девушек возможен любой способ выбора группы юношей. Т.о., всего таких способов *   =............... ??? По какому правилу рассуждаем? Почему здесь можно использовать правило умножения? 2 сл. 4 девушки, а значит ещё 1 юноша, т. е. выбираем 4 девушек из 8 девушек без учёта порядка –значит, считаем количество сочетаний из 8 по 4, это ....... способов, затем выбираем 1 юношу из 4 юношей без учёта порядка, значит, считаем количество сочетаний из 4 по 1:......., (или просто 4 способа). При любом выборе группы девушек возможен любой способ выбора группы юношей. Т.о., всего таких способов....... * 4 =...............     3 сл.   Все 5 - девушки, а значит выбираем 5 девушек из 8 девушек без учёта порядка, т.е., считаем количество сочетаний из 8 по 5, это....  способов. ??? Как учесть в решении все 3 случая составления команды? Сложим все результаты: получили........................ способов..
9	В отделе трудится 6 человек. Поступило распоряжение о премировании трех сотрудников различными суммами. Сколькими способами можно это сделать?	Т.к. суммы премий различны, имеет немалое значение, какая именно сумма достанется «счастливчикам». Значит, идет речь о выборе 3-х человек из 6-ти с учётом порядка. Число способов такого премирования равно числу всех возможных размещений из 6 по 3, т.е.   =...................
10	В отделе трудится 6 человек. Поступило распоряжение о премировании трех сотрудников одинаковыми суммами. Сколькими способами можно это сделать?	Сравните задачи 9 и 10. Где, по-вашему, способов будет больше? Во сколько раз? Почему? ??? Чем принципиально будет отличаться эта ситуация от задачи 9? Т.к. суммы премий одинаковые, важно только то, кто именно будет выбран. Значит, идет речь о выборе 3-х человек из 6-ти без учёта порядка (как набор команды). Число способов премирования в этом случае равно числу всех возможных сочетаний из 6 по 3, т.е.  =........................   Доп. вопросы: Сравните результаты в задачах 9 и 10. Где способов больше? Во сколько раз? Почему? Отвечает ли этот результат вашим интуитивным ожиданиям?
11*	Для любознательных** Почетный караул состоит из военнослужащих пяти родов войск и составляет 12 человек. Сколькими различными способами можно составить команду для почетного караула?   ДЗ	Используем формулу сочетаний с повторениями В данном случае  = 12,  = 5 и число возможных способов равно     .   !!! Постройте какую-либо комбинацию 0 и 1 для данной задачи. ??? Сколько единиц и сколько нулей используем? Почему? Найдите самостоятельно другую задачу на сочетания с повторениями. Запишите её решение в тетрадь.

 

  Для любознательных:

* Бином Ньютона и число сочетаний. Треугольник Паскаля.

  Число сочетаний используется в формуле бинома (двучлена) Ньютона

   

 и поэтому еще называется биномиальным коэффициентом.

Ø Разложите по формуле бинома Ньютона выражение

(a+b) ⁿ, где n= 4, 2, 3, 5.

??? Сколько слагаемых получается при данном n?

??? Где вы раньше видели эту формулу?

Ø Вспомните биномиальный ряд (в теме «Ряды»), запишите биномиальные

коэффициенты ряда для натурального показателя, взяв b =1,

т. е. разложите в ряд функцию (1+ a) ⁿ (выберите, например, n=3, 4 или 5).

     ??? Что вы заметили?

      ??? Как выглядят коэффициенты этого ряда?

     ??? Почему ряд оказался конечным?

Ø Познакомьтесь с построением треугольника Паскаля,

выясните, как он связан с формулой сочетаний и биномом Ньютона.

Для этого можно посмотреть видео на Ютубе по ссылке:

1 https://www.youtube.com/watch?v=0bhpfZgZIAk

2 https://www.youtube.com/watch?v=RTG0ePEkcEY

3 https://www.youtube.com/watch?v=_nvI1QaRjMQ

4 https://youtu.be/WJ_ml-Aixj4

 

**Формула сочетаний с повторениями

  Сочетания с повторениями образуются так. Имеются объекты  различных типов (классов). Выбираем  предметов, взяв  предметов первого типа,  предметов второго типа и т.д. так, чтобы . Значения  могут меняться (от 0 до ), порождая различные наборы.  

Чтобы подсчитать их число, представим отдельный такой набор в виде

ячейки из  клеток, в которой

· единицы показывают клетки, занятые объектами различных классов (  штук),

·  а нули — границы между классами или отсутствующие классы (  штука):

   

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

Т.е. изменение состава выборки связано с различным выбором  мест из  мест для нулей. Это число равно числу сочетаний из  по .

Таким образом, число сочетаний с повторениями из  по , обозначаемое  равно

    .

Для этого можно посмотреть видео на Ютубе по ссылке:

 

Метод «палочек и кружочков»

https://www.youtube.com/watch?v=d74-Kl1_jQE  

                                                                              и др. ресурсы.

 

**************************************************************************

 

Задачи для домашнего задания ДЗ-4:

 

часть. Тест- разминка. №№ 1-8.

 

   В решении следующих 8 задач используются какие-либо комбинаторные соединения.

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

   По итогам работы:

заполните таблицу, где каждому номеру задачи поставьте в соответствие букву с ответом.

 

!! Если вы с успехом справитесь с Тестом- разминкой,

это будет значить, что вы уже имеете базовый уровень по данной теме.

 

1. Сколькими способами можно расположить все 7 нот в разной последовательности, если каждая нота используется только один раз?

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

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

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

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

6. Студенты одной группы должны сдать 5 экзаменов в течение восемнадцати дней. Сколькими способами можно составить расписание экзаменов, если в один день разрешается сдавать не более одного экзамена?

7. Перед выпуском группа учащихся в 25 человек обменялась фотокарточками. Сколько всего было роздано фотокарточек?

8. 25 ребят, встретившись перед занятиями, обменялись рукопожатиями. Сколько было сделано рукопожатий?

 

                                                                                                   Таблица 2

!! Если вы с успехом справились с Тестом- разминкой, значит, вы уже имеете базовый уровень по данной теме.