Занятие 2.2

1.

Комбинаторика

2.

Определение
• Комбинаторика — это раздел математики,
который изучает:
• Сколько способов можно выбрать или
расположить объекты
• Как подсчитать количество комбинаций без
перебора всех вариантов
• Методы систематического перечисления объектов

3.

Правило произведения
• Если действие A можно выполнить m способами,
а после этого действие B можно выполнить n
способами, то выполнить A И B (последовательно)
можно m × n способами.

4.

Пример 1
• Сколькими способами можно задать номер
автомобиля.
• Номер состоит из:
• - 1 буква (из 12 разрешённых)
• - 3 цифры (каждая от 0 до 9)
• - 2 буквы (из 12 разрешённых)
• Ответ: 12 * 10 * 10 * 10 * 12 * 12 = 17 280 000
номеров

5.

Пример 2
• Сколько слов длины 5, начинающихся с гласной
буквы, можно составить из букв Е, Г, Э? Каждая
буква может входить в слово несколько раз. Слова
не обязательно должны быть осмысленными
словами русского языка.
• Ответ: 2 * 3 * 3 * 3 * 3 = 162

6.

Решение на Python
• count = 0
• for i in ["E", "Э"]:
for j in ["E", "Г", "Э"]:
for k in ["E", "Г", "Э"]:
for l in ["E", "Г", "Э"]:
for m in ["E", "Г", "Э"]:
count += 1
• print(count)

7.

itertools
• - это встроенный модуль Python, который
предоставляет готовые функции для работы с
комбинаторикой. Вместо того чтобы писать
вложенные циклы вручную, мы используем
готовые инструменты.

8.

product
• product() — Декартово произведение
• Декартово произведение — это все возможные
комбинации элементов из нескольких множеств.
Это реализация правила произведения.
• Если у нас есть множества A и B, то их декартово
произведение A × B содержит все пары (a, b), где a
∈ A и b ∈ B.
• product(list1, list2, list3, ...)
• product(list1, repeat=n)

9.

Решение на Python
• from itertools import *
• count = 0
• comb = product('ЕГЭ', repeat=5)
• for i in comb:
if i[0] != "Г":
count += 1
• print(count)

10.

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

11.

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

12.

Задача 4
• Рассматриваются символьные
последовательности длины 5 в шестибуквенном
алфавите {У, Ч, Е, Н, И, К}. Сколько существует
таких последовательностей, которые начинаются
с буквы У и заканчиваются буквой К?

13.

Задача 5
• Ольга составляет таблицу кодовых слов для
передачи сообщений, каждому сообщению
соответствует своё кодовое слово. В качестве
кодовых слов Ольга использует 4-⁠
буквенные
слова, в которых есть только буквы A, B, C, D, X, Y.
При этом первая буква кодового слова — это
буква X или Y, а далее в кодовом слове буквы X и Y
не встречаются. Сколько различных кодовых слов
может использовать Ольга?

14.

Задача 6
• Пётр составляет таблицу кодовых слов для
передачи сообщений, каждому сообщению
соответствует своё кодовое слово. В качестве
кодовых слов Пётр использует все пятибуквенные
слова в алфавите {A, B, C, D, E, F},
удовлетворяющие такому условию: кодовое слово
не может начинаться с буквы F и заканчиваться
буквой A. Сколько различных кодовых слов может
использовать Пётр?

15.

Задача 7
• Шифр кодового замка представляет собой
последовательность из пяти символов, каждый из
которых является цифрой от 1 до 4. Сколько
различных вариантов шифра можно задать, если
известно, что цифра 1 встречается ровно два раза,
а каждая из других допустимых цифр может
встречаться в шифре любое количество раз или не
встречаться совсем?

16.

Задача 8
• Составляют 5-⁠
буквенные слова из букв слова
ПЯТНИЦА. Найти количество слов, которые не
начинаются с Н и в которых есть только одна
буква Я. Буквы в слове могут повторяться.

17.

Задача 9
• Алиса составляет 6-⁠
буквенные слова из букв М, А,
Н, Г, У, С, Т. Каждая из букв может встречаться
сколько угодно раз, причём первой буквой не
может быть А, буква У должна встречаться не
менее 1 раза. Также в записи должны быть ровно
две буквы М.Сколько различных слов может
составить Алиса?

18.

Задача 10
• Игорь составляет таблицу кодовых слов для
передачи сообщений, каждому сообщению
соответствует своё кодовое слово. В качестве
кодовых слов Игорь использует пятибуквенные
слова, в которых могут быть только буквы К, О, Н, Ф,
Е, Т, А, причём буква Е появляется ровно 2 раза.
Каждая из других допустимых букв может
встречаться в кодовом слове любое количество раз
или не встречаться совсем. На втором месте НЕ
может стоять буква Ф. Сколько различных кодовых
слов может использовать Игорь?

19.

Ответы
• 1) 162
• 2) 256
• 3) 405
• 4) 216
• 5) 128
• 6) 5400
• 7) 270
• 8) 5616
• 9) 9155
• 10) 1944

20.

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