Дискретная математика (стр. 11 )

=.

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

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

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

.

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

Решение: .

Ответ: 27 000.

3.2.3  Сочетания

Определение. Всякая неупорядоченная выборка объема k из множества, состоящего из n различных объектов, полученная в схеме без возвращения, называется сочетанием из n элементов по k.

Таким образом, сочетания различаются составом входящих в них объектов, но не порядком этих объектов. Из определения выбора без возвращения следует, что k удовлетворяет неравенствам . Число всех сочетаний из n элементов по k принято обозначать (читается «це из n по k»; С – первая буква французского слова combinasion – «сочетание»).

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

= ,

или

Данная формула получена в предположении, что k > 0, однако в силу принятого соглашения, что 0! = 1, правая часть формулы имеет смысл и при k = 0: . Принято считать, что (это соглашение представляется разумным, поскольку существует единственный способ выбрать из данных n объектов 0 объектов – это не выбрать их вовсе). Итак, формула числа сочетаний справедлива для всех k, удовлетворяющих неравенству .

Полезно помнить частные случаи этой формулы при k = 1, 2:

, .

Замечание. Количество множителей в числителе и знаменателе в правой части последней формулы одинаково и равно k.

Пример. ,

.

Пример. Для проведения контрольной работы надо составить 6 вариантов по 9 задач в каждом. Сколькими способами можно распределить 54 задачи для 6 вариантов.

Решение

Задачи для первого варианта можно выбрать способами. После этого останется 45 задач, так что второй вариант можно составить способами. Для третьего варианта задачи можно выбрать способами, для четвертого – способами, для пятого – , а для шестого – способом.

По правилу произведения получаем число: . Учитывая, что варианты равноправны, полученное число надо разделить на 6!:

способов.

Ответ: способов.

Имеет место формула бинома Ньютона

При п = 2 и п = 3 получим известные формулы квадрата и куба суммы двух слагаемых.

Если в формуле бинома Ньютона положить a = b = 1, то получим, что

или

Если обозначить причем , то из последней формулы бинома Ньютона получим:

.

3.2.4  Сочетания с повторениями

Определение. Пусть имеется m групп элементов (в каждой группе достаточно много элементов), таких что элементы внутри группы одинаковы между собой, а элементы разных групп различные. Из совокупности всех элементов возьмем подмножество, содержащее n элементов. Это подмножество из n элементов определяется числом k элементов, взятых из 1-й группы, числом k элементов, взятых из 2-й группы и т. д., числом элементов m-й группы – k. Числа k, k,…, k могут принимать любые целые значения от 0 до n, но так, чтобы сумма их равнялась n, т. е. k+ k+…+ k= n. Множество различных способов образования n-элементного множества из m групп одинаковых элементов обозначается символом и называется сочетаниями с повторениями длины n из m видов. Число сочетаний с повторениями вычисляется по формуле:

.

Пример. В кондитерской продаются 4 сорта пирожных: наполеоны, эклеры, песочные и миндальные. Сколькими способами можно купить 7 пирожных?

Решение. Число групп m = 4. Пирожные, относящиеся к разным типам, различимы, пирожные, относящиеся к одному типу, неразличимы. Рассмотрим множество из n = 7 покупаемых пирожных. Способ образования такого множества определяется числом купленных пирожных 1-го типа, 2-го типа, 3-го типа и 4-го типа.

Числа эти неотрицательные, целые и в сумме дают 7, т. е. мы имеем дело с сочетаниями с повторениями, где m = 4, n = 7. Поэтому число различных способов покупки 7 пирожных находим по формуле: