Кнопка меню
ИНФОРМАТИКА
подготовка к ЕГЭ
Задачи

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

Размещения с повторениями: \( \overline{A}^k_n = n^k \)

Например, в цифровом трехзначном кодовом замке на чемодане, когда в каждом из трех разрядов может быть 10 различных цифр: 103 = 10 ⋅ 10 ⋅ 10 = 1000 комбинаций.

Предположим, что мы забыли комбинацию замка, но точно помним, что первая цифра 5, а вторая 3 или 4, т.е первой может быть только одна цифра, а второй - 2. Тогда нам надо перебрать 1 ⋅ 2 ⋅ 10 = 20 комбинаций, чтобы открыть замок.

Рассмотрим кодовый замок с десятью кнопками цифр, который обычно используется для входа в подъезд. Чтобы открыть дверь, нужно нажать в определенной последовательности 3 цифры. Первой цифрой может быть любая из 10, второй - 9 оставшихся, третьей - 8. Рассчитаем количество различных комбинаций: 10 ⋅ 9 ⋅ 8 = 720.

Размещения без повторений: \( A^k_n = \frac{n!}{(n - k)!} \)

Для примера выше: \( \frac{10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1}{7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1} = \) 10 ⋅ 9 ⋅ 8

Частным случаем размещения без повторений, когда n = k, является перестановка: \(P_n = A^n_n = n! \)

Допустим в замке, пример которого мы приводили выше, нужно нажать все 10 цифр в определенной последовательности. В таком замке 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 3628800 комбинаций.

Для числа перестановок с повторениями справедлива формула: \( P_n (n_1, n_2, …, n_k) = \frac{n!}{n_1! ⋅ n_2! ⋅ .. ⋅ n_k!} \)

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

\( \frac{10!}{5! ⋅ 4! ⋅1!}\) = 1260

Если же в замке нужно нажать всего три цифры одновременно, то количество комбинаций можно вычислить по формуле сочетания: \( C^k_n = \frac{n!}{(n - k)! ⋅ k!} \)

В таком замке \( \frac{10!}{7! ⋅ 3!} = \frac{10 ⋅ 9 ⋅ 8}{1 ⋅ 2 ⋅ 3} = \) 120 комбинаций.

Задача: Некоторый алфавит содержит 4 различных символа. Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться? Слова не обязательно должны быть осмысленными словами русского языка.

Решение: по формуле размещения с повторениями, при n = 4, k = 3: 43 = 64. Ответ: 64

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

Решение: Первая буква должна быть одной из двух: Е и Э, остальные могут быть любой из трех. 2 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 = 162. Ответ: 162

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

Решение: Пусть буква С стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего 1 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 = 81 вариантов слова.

Таким образом букву С можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант, поэтому всего 81 ⋅ 5 = 405 таких слов. Ответ: 405

 

Задачи для самостоятельного решения