Презентация "Комбинаторика"

Тема учебного занятия: КОМБИНАТОРИКА

Цели учебного занятия:

• Образовательные:

• познакомить учащихся с новым разделом математики: «Комбинаторика», с его историей, основными понятиями и задачами, использованием в практических целях и в жизни человека; научить в процессе реальной ситуации использовать определения следующих понятий: «перестановки», «размещения», «сочетания»
• познакомить учащихся с новым разделом математики: «Комбинаторика», с его историей, основными понятиями и задачами, использованием в практических целях и в жизни человека;
• научить в процессе реальной ситуации использовать определения следующих понятий: «перестановки», «размещения», «сочетания»
• Развивающие: формировать коммуникативную компетенцию учащихся; выбирать способы решения задач в зависимости от конкретных условий; развивать аналитические способности, логическое мышление; рефлексия способов и условий действия, контроль и оценка процесса и результатов деятельности .
• формировать коммуникативную компетенцию учащихся; выбирать способы решения задач в зависимости от конкретных условий; развивать аналитические способности, логическое мышление; рефлексия способов и условий действия, контроль и оценка процесса и результатов деятельности .
• Воспитательные: умение слушать и вступать в диалог, участвовать в коллективном обсуждении проблем, интегрироваться в группу сверстников и строить продуктивное взаимодействие, воспитывать ответственность и аккуратность
• умение слушать и вступать в диалог, участвовать в коллективном обсуждении проблем, интегрироваться в группу сверстников и строить продуктивное взаимодействие, воспитывать ответственность и аккуратность

Задачи учебного занятия:

Познакомить с основными понятиями и формулами комбинаторики и научить решать задачи на заданную тему.

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

N-факториал

N! – это воспроизведение чисел от 1 до n

Например:

5!=1*2*3*4*5=120

Подсчитать: 7! 4! 6!

Основные комбинаторные формулы

• Размещения
• Перестановки
• Сочетания

Размещения

Размещениями  из  n  элементов по  m  элементов называются комбинации, составленные из данных  n элементов по  m  элементов, которые отличаются либо самими элементами, либо порядком элементов.

• Число размещений без повторений  из  n  по  m  ( n  различных элементов) вычисляется по формуле:

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

Число размещений с повторениями  вычисляется по формуле:

НАПРИМЕР

Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в Наборе не повторяются; 2) буквы могут повторяться?

Решение.

1) Получатся следующие наборы:  БА, БР, АР, АБ, РБ, РА .

По формуле 1

получаем:  6 наборов

2) Получатся наборы:  ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

По формуле 2

получаем 9 наборов

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

Перестановками  из  n  элементов называются размещения из этих  n  элементов по  n  (Перестановки - частный случай размещений).

• Число перестановок без повторений  (n различных элементов) вычисляется по формуле:

• Число перестановок c повторениями  ( k  различных элементов, где элементы могут повторяться m1, m2, …, mk раз и m1 + m2 +… + mk = n, где n - общее количество элементов) вычисляется по формуле:

НАПРИМЕР

Возьмем буквы  Б, А, Р . Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

Решение.

1) Получатся наборы: БАР, БРА, АРБ, АБР, РАБ.

По формуле (1) получаем:  P3=1*2*3=6  наборов. 

2) Получатся наборы:  БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

По формуле (2) получаем:   наборов

Сочетания

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

• Число сочетаний без повторений  ( n  различных элементов, взятых по  m ) вычисляется по формуле:

• Число сочетаний c повторениями  ( n  элементов, взятых по  m , где элементы в наборе могут повторяться) вычисляется по формуле:

НАПРИМЕР

Возьмем буквы  Б, А, Р . Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.

Решение.

1) Получатся наборы:  БА  ( БА  и  АБ  - один и тот же набор),  АР  и  РБ .

По формуле (1) получаем:    наборов. 

2) Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле (2) получаем:   наборов

Схема определения вида комбинации:

Закон умножения

Определение

Закон умножения  в комбинаторике: число сочетаний (способов, комбинаций) в независимых наборах умножается.

Другими словами, пусть имеется  A  способов выполнить одно действием  B  способов выполнить другое действие. Путь также эти действия независимы, т.е. никак не связаны между собой. Тогда можно найти число способов выполнить первое и второе действие по формуле: C  =  A  ·  B .

Закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.

Задача 1.

• Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 2

• (демо-2021). Игорь составляет таблицу кодовых слов для передачи сообщений, каждому
• сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Задача 3

• Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 4.

• Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 3 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 5

• Вася составляет 3-буквенные слова, в которых есть только буквы К, Р, А, Н, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 6

• Вася составляет 3-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 7.

• Вася составляет 4-буквенные слова, в которых есть только буквы П, И, Р, О, Г, причём в каждом слове буква О может встречаться не более двух раз, при этом, если она есть, то перед ней обязательно стоит согласная буква. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача 8

• Дано слово КОРАБЛИК. Таня решила составлять новые 6-буквенные слова из букв этого слова по следующим правилам: 1) слово начинается с согласной буквы; 2) согласные и гласные буквы в слове должны чередоваться; 3) буквы в слове не должны повторяться. Сколько существует таких слов?

Задача 9.

• Алексей составляет 5-буквенные слова из букв М, А, Г, И, С, Т, Р. Каждую букву можно использовать не более одного раза, при этом в слове нельзя использовать более одной гласной. Сколько различных кодов может составить Алексей?

Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. КККК

2. КККЛ

3. КККР

4. КККТ

……

Запишите слово, которое стоит на 67-м месте от начала списка.

Решение

• самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв)
• выполним замену К  0, Л  1, Р  2, Т  3; поскольку нумерация слов начинается с единицы, а первое число КККК  0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 1002 4
• Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.
• Ответ: ЛККР.

Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААК

3. ААААЛ

4. ААААО

5. ААААШ

6. АААКА

……

• На каком месте от начала списка стоит слово ШКОЛА?

решение

• по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А  0, К  1, Л  2, О  3 и Ш  4
• слово ШКОЛА запишется в новом коде так: 41320 5
• переводим это число в десятичную систему:
• 41320 5 = 4  5 4 + 1  5 3 + 3  5 2 + 2  5 1 = 2710
• поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…

Ответ: 2711 .