Занятие 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. Задача

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

21. Решение

from itertools import *
count = 0
comb =
product('0123456',repeat=4)
for i in comb:
if i[0]>i[1]>i[2]>i[3]:
count+=1
print(count) #35

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

• Перестановки — это все
возможные упорядоченные
комбинации элементов из
набора. При этом важен
порядок и элементы не
повторяются.

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

• from itertools import *
• comb = permutations('123')
• for i in comb:
• print(i)

24. Задача

• Сколько существует чисел, восьмеричная запись
которых содержит 5 цифр, причем в записи нет
цифры 1. Также все цифры записи различны и
никакие две чётные и две нечётные цифры не стоят
рядом.

25. Решение

from itertools import *
count = 0
comb = permutations('01234567',5)
for i in comb:
s = ''.join(i)
if s[0]!="0" and s.count("1") == 0:
s = s.replace("2","0").replace("4","0").replace("6","0")
s = s.replace("3","1").replace("5","1").replace("7","1")
if "00" not in s and "11" not in s:
count+=1
print(count)

26. Слова по порядку

Все 5-⁠
буквенные слова,
составленные из букв А, О, У,
записаны в алфавитном порядке.
Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
……
Запишите слово, которое стоит на
210-⁠
м месте от начала списка.

27. Решение

from itertools import *
count = 0
comb = product('АОУ',repeat=5)
for i in comb:
count+=1
if count == 210:
print(''.join(i))
break

28. Задача 1

Сколько существует девятеричных
пятизначных чисел, содержащих в
своей записи ровно одну цифру 5,
в которых никакие две
одинаковые цифры не стоят
рядом?
13377

29. Задача 2

Определите количество
восьмеричных пятизначных чисел,
которые не начинаются с
нечётных цифр, не оканчиваются
цифрами 2 или 6, а также
содержат не более двух цифр 7.
9135

30. Задача 3

Определите количество 15-ричных
пятизначных чисел, в записи
которых ровно одна цифра 8 и не
менее двух цифр с числовым
значением, превышающим 9.
83175

31. Задача 4

Определите количество 12ричных пятизначных чисел, в
записи которых ровно одна
цифра 7 и не более трёх цифр с
числовым значением,
превышающим 8.
67476

32. Задача 5

Все пятибуквенные слове, в составе которых могут быть только
русские буквы Я, Н, В, А, Р, Ь, записаны в алфавитном порядке и
пронумерованы, начиная с 1. Ниже приведено начало списка.
1. ААААА
2. ААААВ
3. ААААН
4. ААААР
5. ААААЬ
6. ААААЯ
7. АААВА
…
Под каким номером в списке идёт последнее слово, которое не
начинается с буквы Я, содержит не более одной буквы Ь и не
содержит букв Я, стоящих рядом?
6406

33. Задача 6

• Определите количество
шестнадцатизначных чисел в
пятеричной системе счисления,
которые не оканчиваются цифрами
3 и 4, не начинаются с цифры 1.
• 54931640625