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

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

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

Задача. Все буквы, цифры, знаки в ЭВМ кодируются двоичными последовательностями определенной длины, компоненты которой равны 0 или 1.

Например:

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

Обратная задача. Сколько различных чисел (знаков) может быть записано двоичными словами длиной 4, 8, 16:

Или имеется алфавит из 64 слов. Сколько необходимо разрядов, чтобы закодировать в двоичной системе.

Бином Ньютона. Это формула, представляющая выражение (a + b) ⁿ при положительном целом n в виде многочлена:

Заметим, что сумма показателей степеней для a и b постоянна и равна n.

П р и м е р 1.

(См. формулу куба суммы двух чисел).

Числа называются биномиальными коэффициентами.

Их можно вычислить, применяя только сложение, если пользоваться следующей схемой. В верхней строке пишем две единицы. Все последующие строки начинаются и заканчиваются единицей. Промежуточные числа в этих строках получаются суммированием соседних чисел из предыдущей строки. Эта схема называется треугольником Паскаля:

Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая - для n = 2; третья - для n = 3 и т.д. Поэтому, если необходимо, например, разложить выражение:

(a + b)⁷,

мы можем получить результат моментально, используя таблицу:

Свойства биномиальных коэффициентов.

1. Сумма коэффициентов разложения (a + b) ⁿ равна 2 ⁿ.

Для доказательства достаточно положить a = b = 1. Тогда в правой части разложения бинома Ньютона мы будем иметь сумму биномиальных коэффициентов, а слева:

2. Коэффициенты членов, равноудалённых от концов разложения, равны.

Это свойство следует из соотношения:

48 До сих пор мы рассматривали задачи, в которых на порядок элементов в комбинациях не накладывалось никаких ограничений или дополнительных условий. Либо (как в сочетаниях) порядок вообще не учитывался. Рассмотрим задачи с ограничением.

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

Обозначим львов буквой Л. Для тигров имеется 6 мест.

_____Л₁_____Л₂_____Л₃____Л₄_____Л₅______

Львов можно расположить ! Способами, то есть 120. На шести местах для тигров их можно расположить способами.

Общее число способов .

Для задачи в общем виде, если имеется: тигров и львов.

, но так как то

Это возможно лишь при условии, что

49 Задача 1. На книжной полке стоят 12 книг. Сколькими способами можно выбрать 5 из них так, чтобы никакие две из них не стояли рядом.

Зашифруем выбор 0 и 1: каждой оставленной книге поставим в соответствие 0, каждой выбранной - 1. Таким образом, имеем 5 единиц и 7 нулей и задача сводится к предыдущей.

В общем виде: Если стоит книг, а выбирается книг, не стоящих рядом, то это можно сделать

Задача 2. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует с соседом. Надо выбрать 5 рыцарей (например в экспедицию, чтобы освободить заколдованную принцессу), причем так, чтобы среди них не было враждующих. (рис. 8.3) Сколькими способами это можно сделать?

Рис. 8.3.

Отличие от предыдущей задачи состоит в том, что рыцари сидят не в ряд, а по кругу. Но ее легко свести к случаю, когда рыцари сидят в ряд. Для этого возьмем рыцаря, например сэра Ланселота, и разомкнем круг. Все выбираемые комбинации распадаются на два класса: в одном участвует сэр Ланселот, в другом - нет. Подсчитаем сколько комбинаций входит в каждый класс.

1. Если сэр Ланселот отправился в поход, то его соседи справа и слева не должны участвовать. Остаются 9 рыцарей из которых надо выбрать 4. Надо проследить, чтобы среди выбранных не было врагов, то есть чтобы никакие двое не сидели рядом. Цепь разорвана следовательно:

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

. По правилу суммы всего .

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

Это доказывается точно так же, как и выше. Все комбинации элементов разбиваются на два класса в зависимости от одного из них (сэра Ланселота). В первом варианте будет комбинаций, а во втором . Легко проверяется, что

Доказательство:

, ч. т. д.

Задачи

Общая постановка этих задач: