Презентация к докладу "Разбор задания №8. Комбинаторика"

Разбор задания №8 Комбинаторика

Учитель информатики МОУ Яхромская СОШ №1 Дубинкин П.Н.

Типы заданий

• Правило умножения
• Размещение одной/двух/трёх букв
• Подслучаи, подсчёт от «противного»
• Перестановки

Правило умножения

• Сколько слов длины 5 , начинающихся с согласной буквы и заканчивающихся гласной буквой , можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

2 4 4 4 2

— — — — —

КМ КУМА УА

Программное решение (Python)

Правило умножения

• Иван составляет 5-буквенные слова из букв А, Б, В, Г, Э, Ю, Я. Первой и последней буквами этого слова могут быть только буквы Э, Ю или Я, на остальных позициях эти буквы не встречаются. Сколько различных кодовых слов может составить Иван?

3 4 4 4 3

— — — — —

ЭЮЯ АБВГ ЭЮЯ

Программное решение (Python)

Размещение одной /двух/трёх букв

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

6 3 3 3 3 3

— — — — — —

О КРТ

Программное решение (Python)

Размещение одной/ двух /трёх букв

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

5 4 4 4 4

— — — — —

К К РАНТ

Программное решение (Python)

Размещение одной/двух/ трёх букв

• Леся составляет слова, содержащие ровно 3 буквы М, из букв Ч, О, А, Н, И, М, Е. Слово может иметь длину от 4 до 6 букв. Сколько слов может составить Леся?

6 5 4 6 6 6

4 3 2 6

— — — — — —

— — — —

М М М ЧОАНИЕ

М М М ЧОАНИЕ

5 4 3 6 6

— — — — —

М М М ЧОАНИЕ

Программное решение (Python)

Подслучаи, подсчёт от «противного»

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

Решение «в лоб»

5 4 3 3 3

— — — — — = 90

Е Е Е ЛТО

5 3 3 3 3

— — — — — = 405

Е ЛТО

3 «Е»

1 «Е»

5 4 3 2 3

— — — — — = 15

Е Е Е Е ЛТО

4 «Е»

5 4 3 3 3

— — — — — = 270

Е Е ЛТО

2 «Е»

405 + 270 + 90 + 15 + 1 = 781

Подслучаи, подсчёт от «противного»

Решение «от противного»

Всего комбинаций

Комбинаций без «Е»

4 4 4 4 4

3 3 3 3 3

— — — — — = 1024

— — — — — = 243

ЛЕТО

ЛТО

1024 - 243 = 781

Программное решение (Python)

Подслучаи, подсчёт от «противного»

• Вася составляет 5-буквенные слова из букв Ж, И, Р, А, Ф. При этом в каждом слове одна буква Ж, слово не может начинаться на букву Ф и заканчиваться буквой Р. Какое количество слов может составить Вася?

Ж 4 4 4 3

— — — — — = 192

3 4 4 4 Ж

— — — — — = 192

192 × 2 + 432 = 816

3 3 4 4 3

— — — — — = 432

Ж

Программное решение (Python)

Итог

• Основы комбинаторики
• Основы теории множеств

• Сайт Полякова К.Ю.
• КЕГЭ (kompege.ru)

• https://www.youtube.com/live/xElROiCJvg8?feature=share – самое подробное и адекватное объяснение