Rambler's Top100





9
что согласуется с формулой
)!(
!
kn
n
A
k
n
, так как при k=0 имеем
1
!
!
0
n
n
A
n
.
Определение 5. Пусть конечное множество A состоит из n элемен-
тов. k -размещением с повторениями множества A называется упорядо-
ченный набор длины k, элементы которого берутся из A. Элементы в k-
размещении с повторениями не обязаны быть различными.
Пример. Пусть A=
{
1,2,3}. Выпишем все 2-размещения с повто-
рениями множества A:
(1;1),(1;2),(1;3),(2;1),(2;2),(2;3), (3;1),(3;2),(3;3).
Число k-размещений с повторениями n-элементного множества
обозначается
k
n
A
.
Теорема 6.
k
k
n
nA
.
Доказательство. Применим индукцию по k. При k=1 число 1-
размещений равно числу элементов множества A, то есть
nA
n
1
. С
другой стороны, n
1
=n. Базис индукции доказан. Допустим, формула
верна при k=l, то есть
l
l
n
nA
.
Докажем утверждение при k= l +1. Из каждого упорядоченного l-
элементного набора можно получить n упорядоченных наборов длины
l+1, приписывая любой элемент A справа, то есть (l +1)-размещений с
повторениями в n раз больше, чем l -размещений с повторениями, то
есть
kll
n
l
n
nnnAA
1
. Теорема доказана.
Пример. Номер машины состоит из двух букв русского алфавита
(32 буквы) и из четырѐх цифр. Сколько всего существует номеров?
Решение. Пару букв мы можем выбрать
2
32
A
способами, четвѐрку
цифр можно выбрать
4
10
A
способами. Значит, всего машинных номеров
можно составить по принципу произведения
42
4
10
2
32
1032AA
Определение 7. Перестановкой n-элементного множества называ-
ется упорядоченный набор длины n, составленный из этих элементов,
причѐм каждый элемент входит в набор ровно один раз. Число переста-
новок n-элементного множества обозначается символом P
n
.