Подгтовка к КЕГЭ. Комбинаторика.

8 ЗАДАНИЕ. КОМБИНАТОРИКА.

КЕГЭ-2021

Чубарова Е.Г. – учитель информатики МБОУ «СОШ № 5 г. Гурьевска» Кемеровской области

Кодирование данных, комбинаторика,

системы счисления

Что нужно знать :

• если слово состоит из L букв, причем есть n 1 вариантов выбора первой буквы, n 2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение

N = n 1 · n 2 · … · n L

• если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = n L

Пример 1.

Вася составляет 3-буквенные слова , в которых есть только буквы М, У, Х, А. Сколько существует таких слов, которые может написать Вася?

• Буквы могут повторяться
• Каждую букву можно использовать только один раз

1) в каждом случае в трех позициях может быть любая из четырех букв М, У, Х, А , поэтому имеем 4 3 = 64 слова

• всего вариантов 4 · 3 · 2 = 24 слова.

Пример 2.

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

• буква В может стоять на одном из пяти мест:

В ****,

* В ***,

** В **,

*** В *

**** В , где * обозначает любой из оставшихся трёх символов ( О, Л, К )

• в каждом случае в остальных четырёх позициях может быть любая из трёх букв О, Л, К , поэтому при заданном расположении буквы В имеем 3 4 = 81 вариант
• всего вариантов 5 · 81 = 405 .

Пример 3.

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

• первая буква слова может быть выбрана двумя способами ( М или Р ), остальные – тремя ( М, И и Р )

М или Р

2

*

*

3

*

3

*

3

3

• общее число различных слов равно 2*3*3*3*3 = 162

Пример 4.

Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите { A, З, О, T }, которые содержат ровно две буквы A ?

• рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:

АА***,

А*А**,

А**А*,

А***А

в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами ( З, О, T) , поэтому общее число комбинаций (для каждого шаблона!) равно 3 3 = 27

всего 4 шаблона, они дают 4 · 27 = 108 комбинаций

• далее рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции: *АА**, *А*А*, *А**А они дают 3 · 27 = 81 комбинацию

3)два шаблона, где первая по счёту буква А стоит на третьей позиции: они дают 2 · 27 = 54 комбинации **АА*, **А*А 4) и один шаблон, где сочетание АА стоит в конце: ***АА они дают 27 комбинаций

5) всего получаем 108+81+54+27=270

Пример 5.

Сколько существует различных символьных последовательностей длины 3 в пятибуквенном алфавите { М, Ы, Ш, К, А }, в которых буква A встречается хотя бы один раз?

1) рассмотрим различные варианты слов из 3 букв, которые содержат одну букву А: А**, *А*, **А в каждом шаблоне есть 2 позиции, каждую из которых можно заполнить четырьмя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 4 2 = 16

всего 3 шаблона, они дают 3 · 16 = 48 комбинаций

• далее рассматриваем шаблоны, где встречается две буквы А , их всего три: АА*, *АA, А*А они дают 3 · 4 = 12 комбинаций

3) шаблона, где все буквы А - 1 комбинация

Итого 48+12+1=61 комбинация

Пример 6.

Вася составляет 5-буквенные слова из букв П, А, Н, Е, Л, Ь. При этом слово не может начинаться с буквы Ь . Сколько различных слов может составить Вася?

1 способ

1) Всего составить 5 буквенные слова возможно 6 5 = 7776 способами

2) рассмотрим различные варианты слов из 6 букв, которые содержат первую букву Ь:

Ь****

6 4 = 1296 комбинаций

Итого 7776-1296=6480 комбинация

2 способ

Первую букву можно заполнить 5 способами, остальные 6 способами

Получаем

5 · 6 · 6 · 6 · 6= 5 · 6 4 = 5 · 1296=6480 комбинаций

Пример 7.

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

1) Всего составить 6 буквенные слова возможно 6! = 6  5  4  3  2  1 =720 способами

2) рассмотрим различные варианты слов из 6 букв, которые содержат первую букву Ь:

Ь***** 1  5  4  3  2  1 = 120 комбинаций

3) Рассмотрим следующее исключение: ЕЬ

ЕЬ****, *ЕЬ***, **ЕЬ**, ***ЕЬ*, ****ЕЬ

для каждого из остальных случаев количество вариантов распределения остальных букв равно 4  3  2  1 = 24 варианта, то есть запрет сочетания ЕЬ исключает 5  24= 120 кодов

Итого 720-120-120= 480 кодов

Пример 8.

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

1) Всего составить 6 буквенные слова возможно 6! = 6  5  4  3  2  1 = 720 способами

2) рассмотрим различные варианты слов из 6 букв, которые содержат первую букву Ь:

Ь***** 1  5  4  3  2  1 = 120 комбинаций

3) Рассмотрим следующее исключение: ЬЕ

ЬЕ****, *ЬЕ***, **ЬЕ**, ***ЬЕ*, ****ЬЕ

первый случай уже исключен (слово не может начинаться с буквы Ь)

для каждого из остальных случаев количество вариантов распределения остальных букв равно 4  3  2  1 = 24 варианта, то есть запрет сочетания ЬЕ исключает 4  24= 96 кодов

Итого 720-120-96= 504

Пример 9.

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

1) Всего составить 5 буквенные слова возможно 6  5  4  3  2 = 720 способами

2) рассмотрим различные варианты слов из 5 букв, которые содержат первую букву Ь:

Ь**** 1  5  4  3  2 = 120 комбинаций

3) Рассмотрим следующее исключение: ЕЛ

ЕЛ***, количество вариантов распределения остальных букв равно 4  3  2 = 24 варианта

*ЕЛ**,

** ЕЛ *,

*** ЕЛ ,

для каждого из остальных случаев количество вариантов распределения остальных букв равно 3  3  2 = 18 вариантов, так как Ь ранее учтен

24+18*3=24+54= 78

4) Итого 720-120-78= 522