Соединения. Бином Ньютона
Рассмотрим совокупность различных элементов
. Произвольная упорядоченная выборка из этих элементов:
(
;
)
называется соединением. Эта выборка может быть как без повторений, так и с повторениями.
Раздел элементарной математики, в котором для конечных множеств рассматриваются различные соединения элементов, такие, как сочетания, размещения, перестановки, а также все виды соединений с повторениями называется комбинаторика. Задачи комбинаторики впервые рассматривались в связи с возникновением теории вероятностей, где к задачам комбинаторики приводит подсчет вероятностей на основе гипотезы равновозможных элементарных событий.
Размещениями из
элементов по
(
) называют их соединения, каждое из которых содержит ровно
различных элементов (выбранных из данных элементов) и которые отличаются либо сами элементами, либо порядком элементов.
Определим число размещений из
элементов
по
.
Будем строить произвольное соединение последовательно. Сначала определим его первый элемент
. Очевидно, что из данной совокупности
элементов его можно выбрать
различными способами. После выбора первого элемента
, для второго элемента
остается
способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Для
элементов формула приобретает вид: