ВУЗ:
Составители:
Рубрика:
12
b
−
2
раза
,
c
−
один
раз
.
Такой
перестановкой
будет
,
например
,
(
)
, , , ,
a b a b c
или
(
)
, , , ,
b c a a b
.
Выведем
формулу
количества
перестановок
с
повторениями
.
Занумеруем
все
одинаковые
элементы
,
входящие
в
перестановку
,
различными
индексами
,
т
.
е
.
вместо
перестановки
(
)
, , , ,
a b a b c
получим
(
)
1 1 2 2
, , , ,
a b a b c
.
Теперь
все
элементы
перестановки
различны
,
а
количество
таких
перестановок
равно
(
)
1 2
! ... !
k
n m m m
= + + +
.
Первый
элемент
встречается
в
выборке
1
m
раз
.
Уберем
индексы
у
первого
элемента
(
в
нашем
примере
получим
перестановку
(
)
1 2
, , , ,
a b a b c
),
при
этом
число
различных
перестановок
уменьшится
в
1
m
!
раз
,
т
.
к
.
при
изменении
порядка
одинаковых
элементов
наша
выборка
не
изменится
.
Уберем
индексы
у
второго
элемента
–
число
перестановок
уменьшится
в
2
m
!
раз
.
И
так
далее
,
до
элемента
с
номером
k
−
число
перестановок
уменьшится
в
k
m
!
Получим
формулу
( )
1 2
1 2
!
, ,...,
! !... !
n k
k
n
P m m m
m m m
=
⋅
.
Пример
.
Сколько
различных
«
слов
»
можно
получить
,
переставляя
буквы
слова
«
передача
»?
В
этом
слове
буквы
«
е
»
и
«
а
»
встречаются
два
раза
,
остальные
по
одному
разу
.
Речь
идет
о
перестановке
с
повторением
состава
(2,2,1,1,1,1)
длины
2 2 1 1 1 1 8
n
= + + + + + =
.
Количество
таких
перестановок
равно
( )
8
8!
2,2,1,1,1,1 7! 2 10080.
2! 2! 1! 1! 1! 1!
P
= = ⋅ =
⋅ ⋅ ⋅ ⋅ ⋅
8.
СОЧЕТАНИЯ
Задача
.
Сколько
различных
множеств
из
m
элементов
можно
составить
из
множества
,
содержащего
n
элементов
?
Будем
составлять
вначале
упорядоченные
наборы
по
m
элементов
в
каждом
.
Количество
таких
наборов
(
это
размещения
из
n
элементов
по
m
)
равно
( )
!
.
!
m
n
n
A
n m
=
−
Теперь
учитываем
,
что
порядок
записи
элементов
нам
безразличен
.
При
этом
из
m
!
различных
размещений
,
отличающихся
только
порядком
элементов
,
получим
одно
сочетание
.
Например
,
два
различных
размещения
(
)
,
a b
и
(
)
,
b a
из
двух
элементов
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
