Размещения

Определение:

Размещением из [math]\displaystyle{ n }[/math] элементов по [math]\displaystyle{ k }[/math] называется упорядоченная выборка без повторений объема [math]\displaystyle{ k }[/math] из [math]\displaystyle{ n }[/math]-элементного множества.

Не умаляя общности, можно называть размещением из [math]\displaystyle{ n }[/math] элементов по [math]\displaystyle{ k }[/math] упорядоченный набор из [math]\displaystyle{ k }[/math] различных чисел, принадлежащих множеству [math]\displaystyle{ \{1, ..., n\} }[/math].

Количество различных размещений из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] обозначают [math]\displaystyle{ A_n^k }[/math] .

Пример 1

Пусть на экзамене у преподавателя [math]\displaystyle{ n }[/math] различных билетов и сдавать пришло [math]\displaystyle{ k }[/math] студентов. Тогда существует ровно [math]\displaystyle{ A_n^k }[/math] способов выдать всем студентам по одному билету для подготовки.

Пример 2

Пусть [math]\displaystyle{ S = \{1,2,3\} }[/math]. Тогда [math]\displaystyle{ (1,2) }[/math], [math]\displaystyle{ (1,3) }[/math], [math]\displaystyle{ (2,1) }[/math], [math]\displaystyle{ (2,3) }[/math], [math]\displaystyle{ (3,1) }[/math], [math]\displaystyle{ (3,2) }[/math] — все возможные размещения из трех элементов по два.

Утверждение:

Пусть [math]\displaystyle{ k,n\in\mathbb{N} }[/math] и [math]\displaystyle{ 1 \leq k \leq n }[/math]. Тогда [math]\displaystyle{ A_n^k = n\cdot (n-1)\cdot ... \cdot(n-k+1) =\frac{n!}{(n-k)!} }[/math].

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

Действительно, существует [math]\displaystyle{ n }[/math] различных способов выбрать первый элемент набора из элементов множества [math]\displaystyle{ \{1, ..., n\} }[/math]. Аналогично, существует [math]\displaystyle{ n-1 }[/math] способ выбора второго элемента и так далее.

[math]\displaystyle{ \blacksquare }[/math]

Рис. 1. Дерево выбора для размещений: на первом шаге [math]\displaystyle{ n }[/math] вариантов, на втором [math]\displaystyle{ n-1 }[/math], на [math]\displaystyle{ k }[/math]-м — [math]\displaystyle{ n-k+1 }[/math]. Для [math]\displaystyle{ S=\{1,2,3\} }[/math] и [math]\displaystyle{ k=2 }[/math] получается [math]\displaystyle{ 3\cdot 2=6 }[/math] упорядоченных пар.

Конспект: Дискретная математика