Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Понятия перестановки, размещения, сочетания. Бином Ньютона

На главную Математический раздел Криптография и т.д. Новости

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

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

Допустим, есть множество {x, y, z}. Размещениями по два будут {x, y}, {x, z}, {y, z}, {y, x}, {z, x}, {z, y}. Скажем, {x, y} и {y, x} одинаковы по составу, но это разные размещения.

Первый элемент размещения можно выбрать n способами, второй - (n-1) - способами, k-ый - (n-(k-1)) способами. Стало быть, возможно n(n-1)(n-2)...(n-k+1) размещений из n по k. Немного преобразуем полученную нами формулу:

Так будет компактнее)

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

Сочетания и их свойства. Бином Ньютона

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

Допустим, есть множество {x, y, z}. Сочетаниями по два будут {x, y}, {x, z}, {y, z}.

Количество возможных сочетаний определяется как

Одним из самых любопытных свойств сочетаний является вот такая формула:

Если разобраться, то левая часть формулы - количество всевозможных выборок из n элементов без учёта порядка. Рассуждаем. Первый элемент мы можем выбрать либо не выбрать - 2 варианта. Аналогично второй элемент - выбираем либо не выбираем. Так же и с прочими элементами... В итоге получаем произведение n двоек.

Сочетания являются коэффициентами, появляющимися при разложении бинома Ньютона:

Например, при n=3 получим широко известную формулу для куба суммы, как выясняется, частный случай бинома Ньютона:

Теперь ещё раз взгляните на формулу для вычисления количества сочетаний. Из того, что в знаменателе находится k!(n-k)!, а числитель не зависит от k, получаем ещё одно интересное свойство:

Наконец, получим рекуррентное соотношение для расчёта числа сочетаний:

Формулу (*) и полученное рекуррентное соотношение можно скомбинировать:

Это позволит ускорить вычисление коэффициентов разложения бинома Ньютона в сравнении с использованием первой версии рекуррентного соотношения, поскольку теперь почти половину величин не нужно находить по-честному. Примечание: [x] - целая часть числа x, для положительных чисел это по сути отсечение дробной части (или отсутствие изменений, если дробной части нет).

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X