Четыре лекции по комбинаторике. Семенов А.С. - 12 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

14
=!n ,!!),...,,(
121 mmn
kkkkkC ⋅⋅⋅
⋅
откуда .
!!
!
),...,,(
1
21
m
mn
kk
n
kkkC
⋅⋅⋅
=
Теорема 10 доказана.
Пример 13. Сколько различных слов можно получить, переставляя буквы слова "ма-
тематика" ?
Решение. Искомые слова представляют собой перестановки с повторением
( −= 10n число букв в слове) из элементов-букв множества },,,,,,{ т
м
киea
A
=
причем
.2,1,3
654321
=
=
==
=
= kkkkkk
Следовательно, их число равно
.151200
!2!2!3
!10
)2,2,1,1,1,3(
10
=
⋅
⋅
=C
ЛЕКЦИЯ 3
§ 9. Сочетания с повторениями
Пусть задано множество
.)(},,...,{
1
mANaaA
m
=
=
Определение 4.
Сочетаниями из m элементов множества
A
по n элементов с повторениями
называются соединения, содержащие n элементов, причем среди них могут быть
одинаковые, а отличаются они хотя бы одним элементом, но не порядком.
Пример 14. Для множества },{ ba
A
= составить все сочетания с повторениями, со-
держащие три элемента ).3,2(
=
= nm
Решение. Следуя определению 3, получаем ,, aabaaa ., bbbabb
Теорема 11.
Если обозначить через
n
m
f число всех сочетаний с повторением, то
.
1
1
1
n
nm
m
nm
n
m
CCf
−+
−+
== (18)
Доказательство. Из определения сочетания с повторением следует, что каждое та-
кое соединение полностью определяется, если указать сколько элементов каждого
из m типов в него входит. Поэтому поставим в соответствие каждому сочетанию с
повторениями последовательность из нулей и единиц, составленную по следующе-
му циклическому правилу: начиная с 1
=
k
до m
k
=
, напишем подряд столько
единиц сколько элементов
k
a входит в сочетание и далее, если ,m
k
≠ пишем
ноль. Например, написанными выше в примере 13 сочетаниям из двух букв по три
будут соответствовать такие последовательности 1110, 1101, 1011, 0111. Таким об-
разом, каждому сочетанию из
m
по
n
с повторениями соответствует последова-
тельность из n единиц и 1−m нулей, так как нулями отделяются группы единиц,
соответствующие разным элементам. Наоборот, по каждой такой последовательно-
сти однозначно восстанавливается сочетание с повторениями. Следовательно, ме-
жду множеством B построенных последовательностей и множеством D сочетаний
с повторениями имеется взаимно однозначное соответствие. Значит множества B и
D эквивалентны, поэтому ).()( D
N
B
N
=
Множество B в свою очередь эквива-
лентно множеству
C
всех
−
n элементных подмножеств множества

Страницы