Дискретная математика. Азарнова Т.В - 29 стр.

UptoLike

Комбинаторика
29
()( )( )
,0,121
>+=
kknnnnA
k
n
Κ
(1)
т.е.
число размещений из n элементов по k элементов равно
произведению k последовательных натуральных чисел от n до
1
+
kn
включительно
.
Формулу (1) удобно записывать в другом виде. Умножив и разделив
произведение, стоящее в правой части формулы (1), на
()
!
kn
, получим:
()( )( )( )
()
kn
knknnnn
A
k
n
+
=
!121
Κ
или
()
!
!
kn
n
A
k
n
=
(2)
Формула (1) была получена в предположении, что 0
>
k
, формулой (2)
можно пользоваться и при 0
=
k
, так как она и в этом случае дает
правильный результат, а именно
()
.1
!
!
!0
!
0
==
=
n
n
n
n
A
n
При выводе формулы (1) предполагалось также, что 0
n
, т.е. что данное
множество имеет хотя бы один элемент. Если 0
=
n
, то это означает, что
рассматривается пустое множество, а так как пустое множество имеет только
одно подмножество (само себя), то
1
0
0
=
A
.
Задача 5.
В седьмом классе изучается 14 предметов. Сколькими
способами можно составить расписание занятий на субботу, если в этот день
недели должно быть 5 различных уроков?
Решение
.
Различных способов составления расписания, очевидно,
столько, сколько существует пятиэлементных упорядоченных подмножеств у
четырнадцатиэлементного множества.
Следовательно, число способов равно числу размещений из 14
элементов по 5, т.е. равно
5
14
A
. По формуле (1), полагая в ней 5,14
==
kn
находим
.2402401011121314
5
14
==
A
Аналогичный результат получим, воспользовавшись формулой (2):
()
1413121110
!9
!14
!514
!14
5
14
==
=
A
Размещением с повторением
называются упорядоченные выборки
из
n
элементов с повторением и вычисляются по формуле
rr
n
nA
=
.