Элементы дискретной математики - 14 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

14
Переставляя буквы слова «март» получим 24 различные перестановки, так как все
переставляемые элементы различны.
Если же некоторые переставляемые предметы одинаковы, то получается меньше
перестановок – некоторые перестановки совпадают друг с другом.
При перестановке букв слова «мама» имеем две пары одинаковых букв мм и аа.
Сделаем их различными, дописав к одинаковым буквам различные индексы: м
1
а
1
м
2
а
2
.
Рассмотрим все возможные перестановки:
м
1
а
1
м
2
а
2
м
1
м
2
а
1
а
2
а
1
а
2
м
1
м
2
м
1
а
1
м
2
а
2
м
1
а
1
а
2
м
2
а
1
м
1
м
2
а
2
а
1
м
1
а
2
м
2
м
2
а
1
м
1
а
2
м
2
м
1
а
1
а
2
а
2
а
1
м
1
м
2
м
2
а
1
м
1
а
2
м
2
а
1
а
2
м
1
а
1
м
2
м
1
а
2
а
1
м
2
а
2
м
1
м
1
а
2
м
2
а
1
м
1
м
2
а
2
а
1
а
1
а
2
м
2
м
1
м
1
а
2
м
2
а
1
м
1
а
2
а
1
м
2
а
2
м
1
м
2
а
1
а
2
м
1
а
1
м
2
м
2
а
2
м
1
а
1
м
2
м
1
а
1
а
1
а
2
а
1
м
2
м
1
м
2
а
2
м
1
а
1
м
2
а
2
а
1
м
1
а
2
м
2
м
1
а
1
а
2
м
2
а
1
м
1
Получили 24 различные перестановки, которые разбиваются на четверки одинаковых слов,
если убрать индексы при буквах «м» и «а». Значит, всего различных перестановок 6
4
24
= .
Общая задача формулируется следующим образом:
Перестановками с повторениями из n
1
элементов первого типа, n
2
элементов
второго типа, ... , n
k
элементов k-го типа называются всевозможные комбинации из этих
элементов, каждая из которых содержит n
i
элементов i-го вида. Комбинации отличаются
друг от друга лишь порядком элементов.
Число перестановок с повторениями обозначают через Р(n
1
, n
2
, ..., n
k
). Общее
правило вычисления количества перестановок с повторениями:
Р(n
1
, n
2
, ..., n
k
)=.
!...!!
!
21 k
nnn
n
⋅⋅⋅
.
Доказательство
Если бы все элементы были различны, то число перестановок равнялось бы n!. Но
из-за того, что некоторые элементы совпадают, получится меньшее число перестановок.
Возьмем, например, перестановку
aa ... a bb ... b ... xx ... x,
n1 n2 n
k
в которой сначала выписаны элементы первого типа, потом все элементы второго типа, …,
наконец, все элементы k-го типа. Элементы первого типа можно переставлять n
1
! способами,
это ничего не меняет. Точно так же ничего не меняют n
2
! перестановок элементов второго
типа, ... , n
k
! перестановок элементов k-го типа. Перестановки элементов первого типа,
второго типа и т. д. можно делать независимо друг от друга. По правилу произведения
элементы перестановки можно переставлять n
1
!·n
2
! ·...·n
k
! способами так, что она останется
неизменной. То же самое верно и для любого другого расположения элементов. Поэтому

Страницы