Rambler's Top100





8
Теорема 2. Пусть n N, 1≤k≤n. Тогда
)!(
!
kn
n
A
k
n
.
Доказательство. Применим индукцию по k. Докажем равенство
при k=1. 1-размещения это наборы состоящие из одного элемента, взя-
того из n-элементного множества. Очевидно, что их будет столько же,
сколько элементов, в n-элементном множестве, то есть
nA
n
1
. C дру-
гой стороны
n
n
nn
n
n
)!2(
)!1(
)!1(
!
, то есть
)!1(
!
1
n
n
A
n
.
Допустим, равенство выполняется для k<n, то есть
)!(
!
kn
n
A
k
n
. Докажем равенство для k+1≤n. Каждый (k+1)- эле-
ментный набор можно получить из k-элементного приписыванием
справа одного допустимого элемента. Для фиксированного k-
элементного набора это будет любой элемент, не входящий в этот на-
бор. Очевидно, что таких допустимых элементов будет n-k. Значит, из
одного k-элементного набора можно получить (n-k) (k+1)-
элементных наборов, поэтому
1
!
( ) ( )
( )!
!( ) !
.
( 1)!( ) ( ( 1))!
kk
nn
n
A A n k n k
nk
n n k n
n k n k n k
Теорема доказана.
Пример. В первенстве страны участвуют 12 команд. Сколькими
способами они смогут занять призовые места.
Решение. Поскольку является существенным тот факт, какая ко-
манда займет первое место, какая – второе, какая - третье, то задача
сводится к вопросу: сколькими способами можно выбрать трѐхэлемент-
ный упорядоченный набор из 12-элементного множества. Таких спосо-
бов будет
1320101112
!9
!12
3
12
A
способов.
Замечание 3. При k>n невозможно построить k-размещение, по-
этому
0
k
n
A
при k>n.
Замечание 4. При k=0 под 0-размещением мы будем понимать
пустое множество. Так как пустое множество единственно, то
1
0
n
A
,