Формулы комбинаторики информатика егэ

Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.

Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.

Задача (Классика)

Все 4-буквенные слова, составленные из букв А, Е, И, О записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. АААА
2. АААЕ
3. АААИ
4. АААО
5. ААЕА
…

Запишите слово, стоящее на 248-м месте от начала списка.

Решение:

Обозначим условно А — 0, Е — 1, И — 2, О — 3.

Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.

Теперь запишем список с помощью цифр.

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
…

Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.

Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.

Переведём число 247 в четверичную систему!

Получилось число 3313₄ в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.

Ответы: ООЕО

Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.

Задача (Классика, Другая вариация)

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

1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА

Решение:

Закодируем буквы цифрами: А — 0, К — 1, Р — 2, У — 3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.

У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.

1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……

Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!

Получили число в четверичной системе 31020₄. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 31020₄ из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.

Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841

Ответ: 841

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И,
записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.

1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ
…

Под каким номером в списке идёт первое слово, которое начинается
с буквы О?

Решение:

Закодируем буквы цифрами.

Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.

Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 3000₅. Мы «забиваем нулями», чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.

Теперь, как в предыдущей задаче, переведём число 3000₅ из пятеричной системы в десятичную.

0 * 5 ⁰ + 0 * 5 ¹ + 0 * 5 ² +
3 * 5 ³ = 375 (в десят. системе)

Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.

Ответ: 376

Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)

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

Решение:

Для начала решим вводную подзадачу.

Пусть у нас есть те же буквы В, О, Л, К, каждая из букв может встречаться в слове любое количество раз или
не встречаться совсем. Сколько можно составить 5-буквенных слов ?

Т.е буквы могут повторяться!

Например

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

Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?

Выведем общую формулу для количества вариантов, когда символы могут повторяться!

Для трёхразрядных чисел от 000 до 999:

N = 10³ = 1000 вариантов.

Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).

N = 4⁵ = 1024 вариантов.

Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!

Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).

N = 3⁴ = 81 комбинация.

Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.

Таким образом, окончательный ответ будет:

N = 81 * 5 = 405 различных вариантов.

Ответ: 405

Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!

Задача(Закрепление формулы)

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

Решение:

Применим главную формулу 8 задания из ЕГЭ по информатике

N = mⁱ = 6³ = 216

Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.

В ответе будет 216.

Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!

Ответ: 216

Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)

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

Решение:

Рассмотрим количество вариантов, когда гласная И стоит в первом месте!

Подсчитаем количество слов с помощью супер-формулы

N = mⁱ = 2⁴ = 16

Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.

Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.

Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160

Ответ: 160

Отработаем главную формулу 8 задания из ЕГЭ по информатике.

Задача (Развиваем понимание формулы!)

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

Решение:

Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная

Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.

N = mⁱ = 4³ = 64

Длина изменяющихся ячеек равна 3, а количество возможных букв 4.

Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256

Ответ: 256

Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.

Задача (Другой метод решения!!)

Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?

Решение:

Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!

Решим вводную подзадачу (без дополнительных ограничений).

Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .

Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!

N = 6 * 5 * 4 * 3 * 2 * 1 = 720

Вернёмся к изначальной задаче!

В начале подсчитаем «методом умножения» количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.

N = 5 * 5 * 4 * 3 * 2 * 1 = 600

В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.

Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ

Узнаем количество вариантов в каждом таком случае.

N1 = 4 * 3 * 2 * 1 = 24

На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.

N2 = 3 * 3 * 2 * 1 = 18

Аналогично предыдущему случаю.

N3 = 3 * 3 * 2 * 1 = 18



N4 = 3 * 3 * 2 * 1 = 18

N5 = 3 * 3 * 2 * 1 = 18

24 + 18 + 18 + 18 + 18 = 96

Значит, всего слов, которые удовлетворяют условию задаче будет

N = 600 — 96 = 504

Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 6³ = 216

Ответ: 504

Задача (Закрепления «метода умножения»)

Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?

Решение:

Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять «метод умножения».

На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.

Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать «метод умножения» с гласной буквы, количество вариантов бы не поменялось.

N = 6 * 3 * 2 * 2 * 1 * 1 = 72

Ответ: 72

Задача (Азбука Морзе)

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

Решение:

Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.

У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.

Подсчитаем общее количество вариантов.

N = 2³ + 2⁴ = 8 + 16 = 24 комбинаций.

Задача (Обратная предыдущей)

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

Решение:

Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.

N = 4^x = 300

Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4^x больше 300.

4⁵ = 1024

Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!

Ответ: 5

Задача (Важная!)

Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?

Решение:

На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.

Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.

n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).

Восклицательный знак — это факториал!

Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»

Примечание: При использовании формулы сочетаний, не важен порядок, в котором мы выбираем одни и те же книги. Это будет один и тот же вариант.

Ответ: 10

Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.

Задача (Главная формула + сочетания)

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

Решение:

В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!

Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.

Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.

Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.

N = mⁱ = 4² = 16

Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160

Ответ: 160

Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.

Задача (Таблица соревнований)

Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?

Решение:

Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.

	1 команда	2 команда	3 команда	…	20 команда
1 дисциплина	1	—	1	…	3
2 дисциплина	—	2	1	…	2
…	…	…	…	…	…
10 дисциплина	1	1	2	…	—

Сделав рисунок, задача обрела привычные очертания.

Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.

N = mⁱ = 2ⁱ = 4

i=2 бита (длина равна «2 буквам», если воспринимать задачу, как со словами.)

Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.

Всего ячеек = 20 * 10 = 200

Тогда вся таблица будет весит:

V = 2 бита * 200 = 400 бит.

Ответ: 400

Формула Шеннона

Задача (Формула Шеннона)

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Решение:

Найдём вероятность p того, что вытащили чёрный шарик.

p = (количество чёрных шаров) / (количество всех шаров) = 8 / (24 + = 8 / 32 = 1 /4

p = 1 / 4

Применим формулу Шеннона.

x = log₂(4)
2^x = 4

x = 2 бита

Ответ: 2

МУНИЦИПАЛЬНОЕ
АВТОНОМНОЕ ОБЩЕБРАЗОВАТЕЛЬНОE
УЧРЕЖДЕНИЕ

МУНИЦИПАЛЬНОГО
ОБРАЗОВАНИЕ ГОРОД КРАСНОДАР ЛИЦЕЙ № 90

ИМЕНИ
МИХАИЛА ЛЕРМОНТОВА

ПРОЕКТ по информатике

Тема: «Восьмое задание в КИМах
ЕГЭ по информатике”

Ученика 11” В” класса

МАОУ Лицей №90

г. Краснодара

Прутский Дмитрий

Руководитель проекта:

Савина Р. Р.

2021–2023 учебный
год

Оглавление

Введение

Глава
первая.

Комбинаторика — правила, формулы и примеры
с решением

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

Глава
вторая.

Заключение.

Список
литературы

Введение

В наше время, многие
выбирают в виде экзамена для сдачи в 11 классе информатику. В некоторых номерах
экзамена используется метод комбинаторики. Комбинаторика зачастую вызывает
сложность у сдающих. Существует множество видов решения комбинаторных задач.

Актуальность проекта:

В 8 номере ЕГЭ
используется метод комбинаторики. Я хочу ознакомиться с ним и показать
различные методы решения этого номера.

Цель работы:

 Упрощение решения ЕГЭ.

Значимость проекта:

 Данная работа упростит
решение 8 номера ЕГЭ, продемонстрирует различные способы решения. Каждый из нас
сможет выбрать свой способ решения.

Задачи:

·        
проанализировать номера ЕГЭ по информатике

·        
подготовить несколько решений номера 8 и
организовать их

Предмет исследования —
контрольно-измерительный материал экзамена по информатике

Глава первая.

Комбинаторика
— правила, формулы и примеры с решением

Комбинаторика — это
раздел математики, в котором изучаются способы выбора и размещения элементов
некоторого конечного множества на основании определенных условий. Выбранные
(или выбранные и размещенные) группы элементов называются соединениями. Если
все элементы полученного множества разные, получаем соединения без повторений,
а если элементы повторяются — соединения с повторениями.

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

Перестановкой из n
элементов называется любое упорядоченное множество из n данных элементов. Иными
словами, это такое множество, для которого указано, какой элемент находится на
первом месте, какой — на втором, …, какой — на n-формула числа перестановок
Комбинаторика — правила, формулы и примеры с решением. Комбинаторика — правила,
формулы и примеры с решением

Пример:

Количество различных
шестизначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, не
повторяя эти цифры в одном числе, равно Комбинаторика — правила, формулы и
примеры с решением.

Размещения

Размещением из n
элементов по k называется любое упорядоченное множество из k элементов,
состоящее из элементов данного n-элементного множества. Формулы для нахождения
количества соединений с повторениями обязательны только для классов
физико-математического профиля. Формула числа размещений Комбинаторика —
правила, формулы и примеры с решением Комбинаторика — правила, формулы и
примеры с решением

Пример:

Количество различных
трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, если цифры
не могут повторяться, равно Комбинаторика — правила, формулы и примеры с
решением

Сочетания

Сочетанием без повторений
из n элементов по k называется любое k-элементное подмножество данного
n-элементного множества. Формула числа сочетаний Комбинаторика — правила,
формулы и примеры с решением Комбинаторика — правила, формулы и примеры с
решением (по определению считают, что Комбинаторика — правила, формулы и
примеры с решением

Пример:

Из 25 учащихся одного
класса можно выделить пятерых для дежурства по школе Комбинаторика — правила,
формулы и примеры с решением способами, то есть Комбинаторика — правила,
формулы и примеры с решением способами. Некоторые свойства числа сочетаний без
повторений Комбинаторика — правила, формулы и примеры с решением (в частности,
Комбинаторика — правила, формулы и примеры с решением) Комбинаторика — правила,
формулы и примеры с решением

Понятие соединения.
Правило суммы и произведения

При решении многих
практических задач приходится выбирать из определенной совокупности объектов
элементы, имеющие те или иные свойства, размещать их в определенном порядке и
т. д. Поскольку в этих задачах речь идет о тех или иных комбинациях объектов,
то такие задачи называют комбинаторными. Раздел математики, в котором
рассматриваются методы решения комбинаторных задач, называется комбинаторикой.
В комбинаторике рассматривается выбор и размещение элементов некоторого
конечного множества на основании определенных условий. Выбранные (или выбранные
и размещенные) группы элементов называют соединениями. Если все элементы
полученного множества разные, получаем размещения без повторений, а если
элементы могут повторяться — размещения с повторениями. В этом параграфе мы
рассмотрим соединения без повторений. Решение многих комбинаторных задач
базируется на двух основных правилах — правиле суммы и правиле произведения.
Правило суммы. Если на тарелке лежат 5 груш и 4 яблока, то выбрать один фрукт
(грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде справедливо
такое утверждение: если элемент А можно выбрать m способами, а элемент В — n способами
(при этом выбор элемента А исключает одновременный выбор элемента В), то А или
В можно выбрать m + n способами. Уточним содержание этого правила, используя
понятие множеств и операций над ними. Пусть множество А состоит из m элементов,
а множество В -из n элементов. Если множества А и В не пересекаются (то есть
Комбинаторика — правила, формулы и примеры с решением), то множество А
Комбинаторика — правила, формулы и примеры с решением В состоит из
Комбинаторика — правила, формулы и примеры с решением элементов. Правило
произведения. Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать
набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5æ4 = 20
способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В
общем виде имеет место такое утверждение: если элемент А можно выбрать m
способами, а после этого элемент В — n способами, то А и В можно выбрать
Комбинаторика — правила, формулы и примеры с решением способами. Это
утверждение означает, что если для каждого из m элементов А можно взять в пару
любой из n элементов В, то количество пар равно произведению Комбинаторика —
правила, формулы и примеры с решением. В терминах множеств полученный результат
можно сформулировать следующим образом. Если множество А состоит из т
элементов, а множество В — из n элементов, то множество всех упорядоченных пар*
(а; b), где первый элемент принадлежит множеству А (а ∈
А), а второй  множеству В (b ∈
В), состоит из Комбинаторика — правила, формулы и примеры с решением элементов.
Повторяя приведенные рассуждения несколько раз (или, более строго, используя
метод математической индукции), получаем, что правила суммы и произведения
можно применять при выборе произвольного конечного количества элементов. 

Упорядоченные множества:

При решении комбинаторных
задач приходится рассматривать не только множества, в которых элементы можно
записывать в любом порядке, но и так называемые упорядоченные множества. Для
упорядоченных множеств существенным является порядок следования их элементов,
то есть то, какой элемент записан на первом месте, какой на втором и т. д. В
частности, если одни и те же элементы записать в разном порядке, то мы получим
различные упорядоченные множества. Чтобы различить записи упорядоченного и
неупорядоченного множеств, элементы упорядоченного множества часто записывают в
круглых скобках, например (1; 2; 3) ≠ (1; 3; 2). Рассматривая упорядоченные
множества, следует учитывать, что одно и то же множество можно упорядочить
по-разному. Например, множество из трех чисел {–5; 1; 3} можно упорядочить по
возрастанию: (–5; 1; 3), по убыванию: (3; 1; –5), по возрастанию абсолютной
величины числа: (1; 3; –5) и т. д.* Множество всех упорядоченных пар (а; b),
где первый элемент принадлежит множеству А (а ∈
А), а второй — множеству В (b ∈
В), называют декартовым произведением множеств А и В и обозначают А × В.
Отметим, что декартово произведение В × А также состоит из m*n элементов.
Заметим следующее: для того, чтобы задать конечное упорядоченное множество из n
элементов, достаточно указать, какой элемент находится на первом месте, какой
на втором, …, какой на n-м.

Размещения:

Размещением из n
элементов по k называется любое упорядоченное множество из k элементов,
состоящее из элементов заданного n-элементного множества. Например, из
множества, содержащего три цифры {1; 5; 7}, можно составить следующие
размещения из двух элементов без повторений:

(1; 5), (1; 7), (5; 7),
(5; 1), (7; 1), (7; 5).

Количество размещений из
n элементов по k обозначается Комбинаторика — правила, формулы и примеры с
решением (читается: «А из n по k», A — первая буква французского слова
arrangement, что означает «размещение, приведение в порядок»). Как видим,
Комбинаторика — правила, формулы и примеры с решением. Выясним, сколько всего
можно составить размещений из n элементов по k без повторений. Составление
размещения представим себе как последовательное заполнение k мест, которые
будем изображать в виде клеточек (рис. 21.1). На первое место можем выбрать
один из n элементов данного множества (то есть элемент для первой клеточки
можно выбрать n способами). Если элементы нельзя повторять, то на второе место
можно выбрать только один элемент из оставшихся, то есть из n – 1 элементов.
Теперь уже два элемента использованы и на третье место можно выбрать только
один из n – 2 элементов и т. д. На k-е место можно выбрать только один из n –
(k –1) = n – k +1 элементов (см. рис. 21.1). Комбинаторика — правила, формулы и
примеры с решением. Поскольку требуется выбрать элементы и на первое место, и
на второе, …, и на k-е, то используем правило произведения и получим
следующую формулу числа размещений из n элементов по k: Комбинаторика —
правила, формулы и примеры с решением.

Например, Комбинаторика —
правила, формулы и примеры с решением (что совпадает с соответствующим
значением, полученным выше). Аналогично можно обосновать формулу для нахождения
числа размещений с повторениями. При решении простейших комбинаторных задач
важно правильно выбрать формулу, по которой будут проводиться вычисления. Для
этого нужно выяснить следующее:

·        
Учитывается ли порядок следования
элементов в соединении?

·        
Все ли заданные элементы входят в
полученное соединение?

Если, например, порядок
следования элементов учитывается и из n данных элементов в соединении
используется только k элементов, то по определению это — размещение из n
элементов по k. После определения вида соединения следует также выяснить, могут
ли элементы в соединении повторяться, то есть выяснить, какую формулу
необходимо использовать — для количества соединений без повторений или с
повторениями.

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

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

Модуль itertools
находится в стандартной библиотеке Python.

Модуль представляет
следующие типы итераторов:

·        
Бесконечные итераторы;

·        
Конечные итераторы;

·        
Комбинаторные генераторы.

Возвращаемый объект также
будет итератором. Мы можем проходиться по итератору с помощью:

·        
функции «next»

·        
цикла for

·        
конвертации в список с помощью list ()

Комбинаторные генераторы:

1. prоduct()

Декартово произведение
итерируемых объектов, подаваемых на вход.

Определение декартова
произведения: произведение множества X и
множества Y – это множество,
содержащее все упорядоченные пары (x, y),
в которых x принадлежит
множеству X, а y принадлежит множеству Y.

Чтобы вычислить
произведение итерируемого объекта умноженного самого на себя, нужно указать
количество повторений с помощью опционального аргумента с ключевым словом repeat. Например,
product (A, repeat=4) – тоже
самое,
что
и product (A, A, A, A).

itertools.product(*iterables,repeat)

2. permutations()

Возвращает
последовательные r перестановок элементов в итерируемом
объекте. Если параметр r не указан или стоит в значении None, то по умолчанию r
принимает длину итерируемого объекта и генерирует все возможные полноценные
перестановки. Кортежи перестановок выдаются в лексикографическим порядке в
соответствии с порядком итерации входных данных. Таким образом, если входные
данные итерируемого объекта отсортированы, то комбинация кортежей будет
выдаваться в отсортированном порядке.

Элементы рассматриваются
как уникальные в зависимости от их позиции, а не от их значения. Таким образом,
если входные элементы уникальны, то в каждой перестановке не будет
повторяющихся значений.

itertools.permutations(iterable,r=None)

Примечание:
в перестановках порядок
элементов имеет значение.

3. combinations()

Возвращает
подпоследовательности длины r из элементов
итерируемого объекта, подаваемого на вход.

Комбинация кортежей
генерируется в лексикографическом порядке в соответствии с порядком элементов
итерируемого объекта на входе. Таким образом, если входной итерируемый объект
отсортирован, то комбинация кортежей будет генерироваться в отсортированном
порядке.

Лексикографический
порядок – способ упорядочивания слов в алфавитном порядке.

Элементы рассматриваются
как уникальные в зависимости от их позиции, а не значения. Таким образом, если
выходные элементы уникальны, то в каждой комбинации не будет повторяющихся
значений.

itertools.combinations(iterable, r)

4.
combinations_with_replacement():

Возвращает
подпоследовательности длины r из элементов
итерируемого объекта, подаваемого на вход, при этом отдельные элементы могут
повторяться больше одного раза.

itertools.combinations_with_replacement (iterable, r)

Глава вторая.

Практическая часть

№1

Алексей составляет
таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует
своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные
слова, в которых есть только буквы A, B, C, X, причём буква X может появиться
на первом месте или не появиться вовсе. Сколько различных кодовых слов может
использовать Алексей?

Решение 1

На первой позиции в слове
могут быть все четыре буквы А, В, С и Х, а со второй по пятую — 3. Значит,
всего можно составить 4 · 3 · 3 · 3 · 3 = 324 слова

Решение 2

В решение два мы
прогоняем через цикл сразу с выполнением выше поставленных условий и считаем ,
все возможные варианты

Решение 3

В решение 3 мы используем
встроенный модуль itertools, а именно prоduct. Прогоняем через цикл получая
картеж, потом преобразовываем картеж в список, и выполняем все выше
поставленные условия. Считаем все возможные варианты исхода

№2

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

Решение 1

Составляем
четырехбуквенные слова. На первые два места можно поставить одну из трех букв
X, Y или Z. Это можно сделать 3*3=9 вариантами. На два последних места берем
букву из четырех букв A, B, C или D. Получаем 4*4=16 вариантов. Таким образом,
всего 9*16 = 144 варианта.

Решение 2

В решение 3 мы используем
встроенный модуль itertools, а именно prоduct. Прогоняем через цикл получая
картеж, потом преобразовываем картеж в список, и выполняем все выше
поставленные условия. Считаем все возможные варианты исхода

Решение 3

В решение два мы
прогоняем через цикл сразу с выполнением выше поставленных условий и считаем , все
возможные варианты

Заключение.

В ходе данного проекта нам удалось
познакомиться с методом комбинаторики, и благодаря этому мы смогли лучше
понимать эту тему. Также, нам предоставилась возможность изучить различные
варианты решения 8 номера по предмету информатики для единого государственного
экзамена. Хотелось бы добавить, что мы также узнали новый метод на языке
программирования Phyton,
и вдобавок показали различные решения довольно сложных задач по комбинаторике.

Список литературы

1.       
https://www.evkova.org/kombinatorika#Комбинаторика

2.       
https://mosmetod.ru/files/Informatika/KEGE-2021/Задание_8_Кодирование_данных_Павлова_ИБ.pdf

3.       
Райгородский, А. М. Вероятность и алгебра
в комбинаторике / А.М. Райгородский. — М.: МЦНМО, 2008. — 48 c.

4.       
Райгородский, А. М. Вероятность и алгебра
в комбинаторике / А.М. Райгородский. — М.: МЦНМО, 2010. — 48 c.

5.       
Райгородский, А. М. Линейно-алгебраический
метод в комбинаторике / А.М. Райгородский. — М.: МЦНМО, 2007. — 136 c.

6.       
Савельев, Л. Я. Комбинаторика и
вероятность / Л.Я. Савельев. — М.: Наука. Сибирское отделение, 1975. — 424 c.

7.       
Шахмейстер, А. Х. Комбинаторика.
Статистика. Вероятность / А.Х. Шахмейстер. — М.: КДУ, Петроглиф, МЦНМО, 2014. —
296 c.

8.       
Шахмейстер, А. Х. Комбинаторика.
Статистика. Вероятность / А.Х. Шахмейстер. — М.: МЦНМО, Петроглиф, Виктория
плюс, 2010. — 296 c.

9.       
Шахмейстер, А. Х. Комбинаторика.
Статистика. Вероятность / А.Х. Шихтмейстер. — М.: Петроглиф, Виктория плюс,
МЦНМО, 2015. — 296 c.

10.    Эрдеш,
П. Вероятностные методы в комбинаторике / П. Эрдеш, Дж. Спенсер. — М.: Мир,
1976. — 136 c.

11.    Яковлев,
И. В. Комбинаторика для олимпиад ников / И.В. Яковлев. — М.: МЦНМО, 2016. — 80
c.

На этой странице вы узнаете

• Как и для чего информатика использует целый раздел математики?
• Как работают безопасные пароли?
• Зачем считать, если можно не считать? 

Что общего у автомобильного номера, карточной игры и расписания школьных занятий? Наука, их изучающая, — комбинаторика. 

Применение комбинаторики

Комбинаторика — это раздел математики, который занимается решением задач, связанных с выбором и расположением элементов какого-либо множества по заданным параметрам.

Что может служить примерами таких данных?

• автомобильные номера — набор букв и цифр в определенном порядке;
• карточные игры — наборы карт, которые могут находиться у вас на руках;
• расписание занятий — варианты порядка проведения уроков. 

Собственно, комбинаторика может помочь нам:

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

Размещения и перестановки

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

• Размещения — элементы набора могут использоваться в последовательности определенной длины любое количество раз (в том числе ни разу).

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

• Перестановки — возможные последовательности образуются изменением порядка следования элементов друг за другом. Каждый элемент набора используется ровно 1 раз.

Пример: распределение 5 человек на дежурства в течение 5 дней. Было бы справедливо, если бы один человек дежурил только один раз, но вот в какой из дней — уже есть выбор.

Подсчет количества комбинаций

Количество комбинаций зависит от вариантов расстановки элементов. Чем больше символов может стоять на каждой позиции, тем больше будет комбинаций. Полное их количество рассчитывается как произведение количества возможных символов на каждой позиции.

В размещениях каждый элемент может быть на любой позиции и может встретиться любое количество раз. То есть на каждой из k позиций может быть любой из n символов, тогда всего размещений может быть N=n^k.

В перестановках последовательности отличаются только порядком следования элементов. Значит, каждый из элементов будет использоваться ровно 1 раз.

• На первой позиции может стоять любой из n символов;
• На второй — любой из оставшихся n − 1 символов;
• На третьей — любой из еще не использовавшихся, то есть n − 2;
• В конце концов — на самой последней позиции может использоваться только 1 оставшийся символ.

Поэтому количество комбинаций перестановок рассчитывается как факториал количества символов: произведение всех чисел от 1 до количества.

В остальных случаях — составляем выражение согласно требованиям:

• Считаем, какое количество символов может находиться на каждой позиции.
• Перемножаем полученные значения.

Например, мы выбираем пароль по следующим условиям:

• длина пароля — 6 символов;
• используются только символы “P”, “A”, “S”, “W”, “O”, “R”, “D”, “1”, “2”, “3”;
• “Р” должен быть на первом месте и больше не встречаться в пароле;
• “3” должен быть на последнем месте и больше не встречаться в пароле.

Определим, какие символы на каких позициях могут находиться:

Теперь можем составить выражение, чтобы найти количество всех возможных вариантов пароля. Перемножим количество возможных символов на каждой позиции:

N = 1 * 8 * 8 * 8 * 8 * 1 = 4096.

Размещения и перестановки в программе Python

Для облегчения работы с ними в Python существует модуль itertools, который содержит инструменты для их создания:

• permutations(набор символов) — создает перестановки переданного набора

---

from itertools import permutations
for i in permutations(“abc”):
    print(i)

Вывод:
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

---

• product(набор символов, repeat = длина последовательности) — создает размещения заданной длины из заданного набора символов

---

from itertools import product
for i in product("abcd", repeat = 2):
    print(i)

Вывод:
('a', 'a')
('a', 'b')
('a', 'c')
('a', 'd')
('b', 'a')
('b', 'b')
('b', 'c')
('b', 'd')
('c', 'a')
('c', 'b')
('c', 'c')
('c', 'd')
('d', 'a')
('d', 'b')
('d', 'c')
('d', 'd')

---

Все комбинации будут возвращены в виде списка символов.

Пример.

Допустим, мы будем составлять пароли длиной 6 символов из того же набора символов “P”, “A”, “S”, “W”, “O”, “R”, “D”, “1”, “2”, “3”, но с дополненными условиями:

• символ “Р” может использоваться в пароле любое количество раз, но обязательно должен быть на первом месте;
• символ “3” должен быть использован в пароле ровно 3 раза;
• в пароле не должно быть сочетания “123”.

Пошагово наш код должен состоять из следующих элементов:

1. Для создания всех вариаций пароля будем использовать product модуля itertools, все пароли будем перебирать циклом for. Также предварительно создадим переменную-счетчик подходящих паролей.
2. Нам нужно проверить все условия задачи. Элемент комбинации с индексом 0 равен “Р”, “3” встречается в ней ровно 3 раза, а также в списке символов комбинации не должно быть набора (“1”, “2”, “3”).
3. При нахождении подходящего пароля будем увеличивать наш счетчик на 1, в конце программы выведем его значение на экран.

---

from itertools import product

cnt = 0
for i in product("PASWORD123", repeat = 6):
    if i[0] == "P" and i.count("3") == 3 and ("1", "2", "3") not in i:
        cnt += 1
print(cnt)

Вывод: 810

---

Фактчек

• Размещения — наборы последовательностей определенной длины, состоящие из определенных символов, которые могут встречаться в последовательности сколько угодно раз. Количество размещений N зависит от длины последовательности k и количества символов n как N=n^k.
• Перестановки — наборы последовательностей, отличающиеся только порядком следования символов друг за другом. Количество перестановок N зависит от количества символов в них n как N = n!.
• В общем виде количество комбинаций высчитывается как произведение количества возможных символов на каждой позиции.
• Для записи перестановок в Python используется permutations из модуля itertools, для записи размещений — product из того же модуля.

Проверь себя

Задание 1.
Сколько будет размещений длинной 5, состоящих из набора “123”?

1. 243
2. 125
3. 120
4. 6

Задание 2.
Что такое перестановки?

1. Комбинации, состоящие из символов определенного набора, разной длины.
2. Комбинации, состоящие из символов определенного набора, одной длины.
3. Комбинации, состоящие из символов определенного набора и отличающиеся только порядком следования символов друг за другом.
4. Комбинации, состоящие из символов определенного набора и отличающиеся только длиной.

Задание 3.
Сколько может быть паролей длиной 4, состоящих из набора символов “ПАРОЛЬ”, в которых любой символ может использоваться сколько угодно раз, кроме “Ь” (используется только один раз и только на последнем месте)?

1. 15
2. 20
3. 125
4. 625

Задание 4.
Какая из записей на языке Python создаст размещения набора “ПАРОЛЬ” длинной 4?

1. itertools(“ПАРОЛЬ”, repeat = 4)
2. product(4, repeat = “ПАРОЛЬ”)
3. permutations(“ПАРОЛЬ”, repeat = 4)
4. product(“ПАРОЛЬ”, repeat = 4)

Ответы: 1. — 1; 2. — 3; 3. — 3; 4. — 4.

Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».

Добрый день, дорогие друзья! С вами я, Есакова Лада, преподаватель информатики с 20-летним стажем.
Сегодня разберем основы комбинаторики и буквенные цепочки.

Задача:
«Все 4-буквенные слова, составленные из букв В, Н, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ВВВВ
2. ВВВН
3. ВВВР
4. ВВВТ
5. ВВНВ
………
Запишите слово, которое стоит под номером 251.»

Обозначим В = 0, Н = 1, Р = 2, Т = 3 и получим вот такой ряд:

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010

Это числовой ряд в четверичной системе исчисления. Нам нужно найти слово, которое стоит под номером 251.

Здесь важный нюанс, на котором часто ребята теряют балл. На первом месте стоит 0, то есть номер строчки на единицу больше самого числа. Поэтому на 251 месте у нас будет стоять число на единицу меньше – 250, но только в четверичной системе исчисления.

Переведем 250 в четверичную систему. Будем делить столбиком. У нас получается 250 = 3322₄. Теперь переводим цифры в буквы — ТТРР. Вот такой ответ должен получиться.
Вот такие буквенные цепочки – это, по сути, числовые ряды.

Следующая задача:
«Все 6-буквенные слова, составленные из букв С, В, Е, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ВВВВВВ
2. ВВВВВЕ
3. ВВВВВС
4. ВВВВВТ
5. ВВВВЕВ
………
Под каким номером стоит первое из слов, которое начинается с буквы Т?»

Здесь есть еще одна ловушка: нам сказали, что все 6-буквенные слова составлены из этих букв, и очень хочется пронумеровать букву в том же порядке, в котором они представлены – С = 0, В = 1, Е = 2, Т = 3. Вот здесь-то и ошибка.

Если посмотрим на числовой ряд, то увидим, что на первой строчке у нас стоит В, значит, она будет равна 0. Далее появляется Е, значит, она равна 1, С = 2 и Т = 3.

И снова у нас четверичная система исчисления. Необходимо определить, под каким номером стоит первое из слов, которое начинается с буквы Т. Перефразирую вопрос: под каким номером стоит четверичное число, которое начинается на 3? Значит, оно должно выглядеть как 300000. Это число стоит на месте, которое на единицу больше, чем оно само, но в десятичной записи. Необходимо это число, 300000, из четверичной системы перевести в десятичную.

300000₄=3*4⁵=3*1024=3072

У нас получается число 3072, а номер строки на единицу больше, то есть номер строки будет 3073. Это и есть ответ задачи.

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

Чтобы понять, о чем я сейчас буду говорить, давайте представим такую ситуацию: допустим, надоело нам жить в Москве и решили переехать на необитаемый остров. Для связи с внешним миром мы запасли некоторое количество цветных флажков, которые мы можем прикрепить к флагштокам и при необходимости подать сигнал. У нас есть два флагштока и флажки только двух цветов: красные и синие. Что же при помощи этого мы можем сообщить во внешний мир?

Мы можем составить 4 комбинации:

Если нам этого не хватает, мы можем добавить флажки еще одного цвета. Допустим, у нас еще есть зеленые флажки, и мы можем составить следующие комбинации:

У нас получилось 9 комбинаций.

Если же все-таки у нас флажки только двух цветов, третьего нет, у нас есть другой путь увеличить количество комбинаций, увеличив количество флагштоков. Получаем следующие комбинации:

и их получилось 8 штук.

Мы видим, что количество сообщений, которые мы можем передать внешнему миру, зависит от двух параметров: от количества букв в нашем алфавите (или, в нашем случае, от разных цветов флажков) и от длины слова (или от количества флагштоков).

Количество слов, которые мы можем закодировать, равно количеству букв в нашем алфавите (еще это называется мощностью алфавита) в степени «длина слова» A=aⁱ

«Сколько различных символов можно закодировать, используя код азбуки Морзе длиной не менее четырех и не более пяти сигналов (точек и тире)?»

Если я делаю слово из четырех сигналов, то таких слов я могу сделать 2⁴, если я делаю из пяти сигналов, то таких слов я могу придумать 2⁵. А в задаче как раз этот интервал, то есть и те, и те мне подойдут. Вот столько разных слов я могу составить 2⁴ + 2⁵ = 48.

«Коля составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово. В качестве кодовых слов Коля использует 4-буквенные слова, в которых есть буквы А, Б, В, Г, Д, причем буква Д появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Коля?»

Не буду мудрить, придумывать какие-то сложные формулы, а просто распишу, как буква Д может встречаться ровно один раз. Это выглядит так

Д — — —
— Д — —
— — Д —
— — — Д

то есть она может встретиться на каком-то из четырех мест. На остальных трех местах может стоять все, кроме Д, то есть 4 любые буквы по трем позициям, 4³. И так в каждом ряду. Все это сложим и получим 4*4³=4⁴=256

«Паша составляет таблицу кодовых слов для передачи сообщений. В качестве кодовых слов Паша использует 4-буквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, Ж. При этом первая буква кодового слова – это буква Д, Е или Ж, а далее в кодовом слове буквы Д, Е и Ж не встречаются. Сколько различных кодов может использовать Паша?»

У нас получается такой вид

Д — — —
Е — — —
Ж — — —

А в остальных местах используются остальные буквы, кроме Д, Е и Ж. Получаем 3*4³=3*64=192

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

Тут немного схитрим. Необходимо обязательно чередовать гласные и согласные, а для этого посмотрим, сколько у нас гласных. 3. А согласных 4. Поэтому на гласную начать слово я не могу, иначе их не хватит на все слово, и согласные где-то обязательно повторятся. Поэтому слово будет выглядеть таким образом: согласная – гласная – согласная – гласная – согласная – гласная – согласная.

Далее каждую букву я должна использовать ровно один раз.

Вначале состава слова согласных у нас 4, гласных – 3, далее согласных остается 3, т.к. одну я уже использовала, а согласных – 2, затем согласных 2, гласных – одна и согласная осталась одна. Теперь мы перемножаем все эти цифры

и получаем 144.

«Ольга составляет 5-буквенные коды из букв О, Л, Ь, Г, А. Каждую букву нужно использовать ровно 1 раз, при этом Ь нельзя ставить первым и нельзя ставить после гласной. Сколько различных кодов может составить Ольга?»

Давайте пойдем от противного: посчитаем все варианты, а потом выбросим те, которые нам запретили, но сразу выкинем вариант с мягким знаком на первом месте. То есть на первом месте мы можем поставить 4 различные буквы. На втором месте могу поставить все, кроме этой буквы, но зато мы можем добавить Ь, то есть тоже 4. Две буквы уже использовали. Осталось 3, 2 и 1. Все это перемножаю и получаю 96. То есть это все возможные слова, где используется буквы по одному разу, но только не начинающиеся на Ь.

Теперь из этого числа нужно выбросить ситуации, когда Ь стоит после гласной. Это, например, вот так

О Ь — — —
— О Ь — —
— — О Ь —
— — — О Ь

Таких слов 24

О Ь — — — 3*2*1
— О Ь — — 3*2*1
— — О Ь — 3*2*1
— — — О Ь 3*2*1
——
24

Абсолютно такая же ситуация с буквой А

А Ь — — —
— А Ь — —
— — А Ь —
— — — А Ь
———
24

И их тоже 24. То есть 96-48=48.

На этом прощаемся. Если вопросов нет, пока!

Все видео по информатике

Что такое комбинаторика и зачем оно нам надо на ЕГЭ по информатике?   

Комбинаторика — область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов заданного множества.

 

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

  ◾ПЕРЕСТАНОВКИ 

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

   Представь, что у тебя есть 10 книжек и тебе необходимо их расставить на полке в каком-то порядке, так сколько способов это сделать у тебя есть? 

   Формула подсчета перестановок: 

  📍Pn = n·(n−1)·(n−2)…3·2·1 = n!, где n- количество элементов данного множества. 

  ! — это факториал числа — произведение натуральных чисел от 1 до самого числа (включая данное число. 

  То есть, решением поставленной задачей будет: P(10) = 10·(10−1)·(10−2)…3·2··1 = 3628800

◾РАЗМЕЩЕНИЯ 

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

  Например, тебе уже надо не все 10 книжек расставить по порядку, а только 5 из них,так вот сколько будет способов это сделать? 

   Число размещений из n по m обозначается A(n;m) и определяется по формуле 

  📍A(n;m) = n·(n − 1)·(n − 2)·…·(n − m + 1) = n!/(n − m)! 

  Так вот количество способов подсчитать такое расположение пяти книжек из 10 на полке и будет число размещений из 10 по 5. То есть: A(10;5) = 10!/(10 − 5)! =10!/5!=30240 

  ◾СОЧЕТАНИЯ 

  Неупорядоченные выборки называются сочетаниями из n элементов по m и обозначаются С(n;m) 

  Ключевое слово здесь неупорядоченные, то есть нам не важно, какая книжка будет стоять на первом месте, а какая на втором, мы хотим посчитать любые варианты расстановки. Можно интерпретировать как: у нас все также есть 10 книжек, пять из которых нужно расставить в любом порядке, сколько существует возможных вариантов? 

  📍Число сочетаний определяется по формуле С(n;m) = n!/((n − m)!*m!)    

  То есть в нашей задаче получится: С(10;5) = 10!/((10 − 5)!*5!)= 252 

ВАЖНО: далеко не всегда в ЕГЭ применяются формулы комбинаторики (иногда задачу проще решить перебором), но в любом случае знать основы необходимо.