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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
Пример 7. Сколькими способами из 7 человек можно выбрать комиссию, состоящую
из 3 человек ?
Решение. Чтобы определить все возможные комиссии, нужно рассмотреть все воз-
можные трехэлементные подмножества множества, состоящего из семи элементов.
Следовательно, искомое число способов равно .35
!4!3
!7
3
7
=
⋅
=C
Пример 8. Рассмотрим на плоскости с декартовой прямоугольной системой коорди-
нат «шахматный город», состоящий из nm
×
прямоугольных кварталов, границами
которых являются части 1+n горизонтальных и 1
+
m вертикальных улиц. Требу-
ется определить число различных кратчайших путей в пределах этого города, веду-
щих из левого нижнего угла (точки О(0;0)) в правый верхний угол (точку Р( nm; )).
Решение. Каждый кратчайший путь из точки О в точку Р состоит из
nm +
отрезков,
причем среди них есть
m горизонтальных и n вертикальных отрезков. Разные пути
отличаются лишь порядком чередования горизонтальных и вертикальных отрезков.
Поэтому искомое число путей равно числу способов, которыми из
nm +
отрезков
можно выбрать n отрезков, т.е. ,
n
nm
C
+
или числу способов, которыми из nm
+
от-
резков можно выбрать m отрезков, т.е. .
m
nm
C
+
Итак, число кратчайших путей равно
.
n
nm
m
nm
CC
++
= (12)
Замечание. Заметим, что равенство (12) установлено при решении геометрической
задачи. В справедливости его нетрудно убедиться и непосредственно, используя
формулу (11). Заметим так же, что рассмотренный пример дает интересную геомет-
рическую интерпретацию для чисел .
k
n
C
§ 5. Количество подмножеств данного конечного множества
Выясним, сколько всего подмножеств имеет множество
A
с .)( n
A
N
=
Теорема 7.
Число всех подмножеств множества из n элементов равно ,2
n
т.е.
.2))((
n
AMN = (13)
Доказательство. Перенумеруем элементы множества
A
и для каждого подмноже-
ства
)(
A
M
B
⊂ построим последовательность длины
n
из нулей и единиц по сле-
дующему правилу: на −
k
ом месте пишем 1, если элемент ,Ba
k
∈ и пишем 0, ес-
ли
.Ba
k
∉ Итак каждому подмножеству будет соответствовать своя последова-
тельность из нулей и единиц. Например, пустому множеству Ø соответствует по-
следовательность из одних нулей, а самому множеству
−
A
последовательность из
одних единиц. Ясно, что справедливо и обратное утверждение: каждой последова-
тельности из множества
последовательностей длины n из нулей и единиц соот-
ветствует одно подмножество )(
A
M
B
⊂ . Таким образом, между множествами
)(
A
M
и
P
установлено взаимно однозначное соответствие. Следовательно, эти
множества эквивалентны и как конечные множества имеют одинаковое количество
элементов, т.е. ).())((
P
N
A
M
N
= Но
nn
NPN 2)}1;0({)( == в силу формулы (7),
поэтому и
.2))((
n
AMN = Теорема 7 доказана.
Следствие.
Справедливо равенство

Страницы