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

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.

Решение 1
• 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

26.

Решение 2
• 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:
has_pare = False
for j in range(4):
if int(s[j])%2==int(s[j+1])%2:
has_pare = True

27.

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

28.

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

29.

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

30.

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

31.

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

32.

• Задача 4

33.

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

34.

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

35.

Задача 7
• Все шестибуквенные слова, составленные из букв М, У, Ж, Ч, И, Н, А, записаны
в алфавитном порядке и пронумерованы.
• Вот начало списка:
• 1. АААААА
• 2. АААААЖ
• 3. АААААИ
• 4. АААААМ
• 5. АААААН
• 6. АААААУ
• 7. АААААЧ
• Определите в этом списке количество слов с чѐтными номерами, которые не
начинаются с
• буквы Ж и при этом содержат в своей записи не более одной буквы Ч.

36.

Задача 8
• Все 4-буквенные слова, составленные из букв М, А, Р, Т,
записаны в алфавитном порядке и пронумерованы, начиная с 1.
• Ниже приведено начало списка.
• 1. АААА
• 2. АААМ
• 3. АААР
• 4. АААТ
• 5. ААМА
• …
• Под каким номером в списке идѐт первое слово, которое
начинается с буквы М?

37.

Задача 9
• Сколько существует шестнадцатеричных
четырѐхзначных чисел, в которых все цифры
различны и никакие две чѐтные или две нечѐтные
цифры не стоят рядом?

38.

Задача 10
• Все 6-буквенные слова, составленные из букв К, Л, Н,
Т, Э, записаны в алфавитном порядке и
пронумерованы.
• Вот начало списка:
• 1. КККККК
• 2. КККККЛ
• 3. КККККН
• 4. КККККТ
• ……
• Под каким номером стоит слово ККЛККН?

39.

Задача 11
• Определите количество пятизначных чисел,
записанных в восьмеричной системе счисления, в
записи которых ровно одна цифра 6, при этом
никакая нечѐтная цифра не стоит рядом с цифрой
6.

40.

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

41.

Задача 13
• Вася составляет 6-буквенные слова, в которых
могут быть использованы только буквы В, И, Ш, Н,
Я, причѐм буква В используется не более одного
раза. Каждая из других допустимых букв может
встречаться в слове любое количество раз или не
встречаться совсем. Слово не должно начинаться с
буквы Ш и оканчиваться гласными буквами.
Словом считается любая допустимая
последовательность букв, не обязательно
осмысленная. Сколько существует таких слов,
которые может написать Вася?

42.

Задача 14
• Все 4-буквенные слова, составленные из букв П, И,
Т, О, Н, записаны в алфавитном порядке и
пронумерованы, начиная с 1.
• Ниже приведено начало списка.
• 1. ИИИИ
• 2. ИИИН
• 3. ИИИО
• 4. ИИИП
• 5. ИИИТ
• 6. ИИНИ
•…

43.

Задача 15
• Определите количество пятизначных чисел,
записанных в девятеричной системе счисления, в
записи которых ровно одна цифра 3, при этом
никакая из цифр 5, 6, 7, 8 не стоит рядом с цифрой
3.

44.

Задача 16
• Сколько существует десятичных шестизначных
чисел, делящихся на 5, в которых все цифры
различны и никакие две чѐтные или две нечѐтные
цифры не стоят рядом?

45.

Задача 17
• Все пятибуквенные слова, в составе которых могут
быть только русские буквы Л, А, Й, М, записаны в
алфавитном порядке и пронумерованы начиная с
1. Ниже приведено начало списка.
• 1. ААААА
• 2. ААААЙ
• 3. ААААЛ
• 4. ААААМ
• 5. АААЙА
•…
• Под каким номером в списке идѐт последнее

46.

Задача 18
• Все шестибуквенные слова, составленные из букв
А, В, О, Р, Т, записаны в алфавитном порядке и
пронумерованы начиная с 1.
• Ниже приведено начало списка.
• 1. АААААА
• 2. АААААВ
• 3. АААААО
• 4. АААААР
• 5. АААААТ
• 6. ААААВА
•…

47.

Задача 19
• Игорь составляет таблицу кодовых слов для
передачи сообщений, каждому сообщению
соответствует своѐ кодовое слово. В качестве
кодовых слов Игорь использует 5- буквенные
слова, в которых есть только буквы Э, Т, А, Н,
причѐм в каждом слове есть ровно одна гласная
буква и она встречается ровно 1 раз. Каждая из
допустимых согласных букв может встречаться в
кодовом слове любое количество раз или не
встречаться совсем. Сколько различных кодовых
слов может использовать Игорь?

48.

Задача 20
• Все шестибуквенные слова, составленные из букв
Ф, А, В, О, Р, И, Т, записаны в алфавитном порядке
и пронумерованы.
• Вот начало списка:
• 1. АААААА
• 2. АААААВ
• 3. АААААИ
• 4. АААААО
• 5. АААААР
• 6. АААААТ
• 7. АААААФ

49.

Ответы
• 7) 39528
• 8) 65
• 9) 5880
• 10) 128
• 11) 2961
• 12) 192
• 13) 4352
• 14) 501
• 15) 6400
• 16) 1296
• 17) 922
• 18) 4821
• 19) 160
• 20) 8640