ВУЗ:
Составители:
Рубрика:
Рассмотрим еще одну задачу. Сколько различных расписаний экзаменов может быть составлено,
если в экзаменационную сессию сдается
4 экзамена двум преподавателям (каждому по 2 экзамена).
Решение. Обозначим первого преподавателя p, а второго − v. Тогда возможны ситуации pvpv vpvp
pvvp vppv
ppvv vvpp.
Других ситуаций не получится, так как записать две «p» на 2-х из
4-х мест можно
2
4
С способами, а две «v» на оставшиеся два места
можно определить
2
2
С способами. По правилу произведения получим,
что количество различных расписаний может быть: 6
!2 !2
!4
!0 !2
)!24(
)!24(!2
!4
2
2
2
4
==
−
⋅
−
=⋅СС штук.
В этой задаче мы встретились с перестановками с повторениями.
Определение. Перестановка п элементов, среди которых k
1
элемент первого типа, k
2
элементов
второго типа, …, k
m
элементов m-го типа
(k
1
+ k
2
+ … + k
m
= п), причем элементы разных типов различны, называется перестановкой с повторе-
ниями п элементов, среди которых k
1
элементов первого типа, k
2
элементов второго типа, …, k
m
элемен-
тов m-го типа (или короче: перестановкой с повторениями, если заранее известно, что есть п, k
1
,…, k
т
).
Число всех вышеупомянутых перестановок с повторениями обозначается Р(k
1
, …, k
т
). В предыду-
щей задаче мы показали, что Р(2, 2) = 6.
Теорема. Число всех перестановок с повторениями п элементов,
среди которых k
1
элементов первого типа, …, k
m
элементов m-го типа
(k
1
+ … + k
т
= п) вычисляется по формуле:
!!...
)!...(
!!...
!
)...,,(
1
1
1
1
m
m
m
m
kk
kk
kk
n
kkР
++
==
.
Доказательство. В каждой перестановке с повторениями п «мест», из них k
1
«мест» занимают эле-
менты первого типа, …, k
m
«мест» занимают элементы т-го типа. Элементы первого типа можно распо-
ложить
1
k
п
С способами, элементы второго типа –
2
1
k
kп
С
−
способами, …, элементы т-го типа –
m
m
k
kkn
C
11
...
−
−−−
способами. По правилу произведения, число всех рассматриваемых перестановок с повторениями будет
равно:
.
!...!!
!
)!...(!
)!...(
...
)!(!
)!(
)!(!
!
...),...,(
2111
11
212
1
11
...
1
11
2
1
1
mmmm
m
k
kkn
k
kn
k
nm
kkk
n
kkknk
kkn
kknk
kn
knk
n
CCCkkP
m
m
⋅⋅⋅
=
−−−−
−−−
⋅⋅
−−
−
⋅
−
=
=⋅⋅⋅=
−
−
−−−−
−
Теорема доказана.
Задача. Сколько различных последовательностей букв можно составить, переставляя буквы в слове
«криминалистика».
Решение. Так как в слове «криминалистика» 14 букв, то п = 14. Элементов первого типа (буквы
«к») 2 штуки (k
1
= 2). Далее: k
2
= 1 (буква «р»), k
3
= 4 (буква «и»), k
4
= 1 (буква «м»), k
5
= 1 (буква «н»),
k
6
= 2 (буква «а»), k
7
= 1 (буква «л»), k
8
= 1 (буква «с»), k
9
= 1 (буква «т»). Следовательно, количество
всех слов:
Р(2, 1, 4, 1, 1, 2, 1, 1, 1) =
!2!4!2
!14
.
Рассмотрим следующую задачу. Трехсменное дежурство на КПП обеспечивают два подразделения.
Сколько различных расписаний дежурства можно составить?
Решение. Обозначим факт дежурства представителя первого подразделения через p, второго – через
v. Тогда возможны расписания: ppp, ppv, pvv, vvv. Каждая из четырех комбинаций отличается от любой
другой составом элементов, порядок здесь не существенен, так как основное – сколько людей выделяет
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
