Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 45 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

Ут вер жде ние 4:
C C
n
m
n m
m
=
+ +1
.
Ка ж до му (n,m)-со че та нию B с по вто ре ния ми, со став лен но му из
эле мен тов мно же ст ва X = x
1
, ..., x
n
по ста вим в со от вет ст вие век тор a(B)
дли ны n + m + 1 из m ну лей и n – 1 еди ниц та кой, что чис ло ну лей, на -
хо дя щих ся ме ж ду (i – 1)-й и i-й еди ни ца ми, где 2 £ i £ n – 1, бу дет рав но
чис лу эле мен тов х
i
, вхо дя щих в со че та ние B, а чис ло ну лей, стоя щих пе -
ред пер вой еди ни цей (по сле (n – 1)-й еди ни цы), рав но чис лу эле мен -
тов х
1
, (со от вет ст вен но x
n
), вхо дя щих в со че та ние B. Это со от вет ст вие
ме ж ду (n,m)-со че та ния ми с по вто ре ния ми и век то ра ми с (n – 1) еди ни -
ца ми и m ну ля ми вза им но од но знач но. С дру гой сто ро ны, чис ло век то -
ров с (n – 1) еди ни ца ми и m ну ля ми рав но чис лу m-эле мент ных мно -
жеств (но ме ров ну ле вых ком по нен тов в век то рах), яв ляю щих ся под -
мно же ст ва ми (n + m + 1)-эле мен тар но го мно же ст ва {1, 2, ..., n + m – 1}
(мно же ст ва всех но ме ров ком по нент в век то рах), то есть чис лу
(n + m – 1, m)-со че та ний без по вто ре ний. Та ким об ра зом,
C C
n
m
n m
m
=
+ +1
.
Ут вер жде ние 5: Обо зна чим че рез Y
x
мно же ст во всех ото бра же ний
f: X®Y. Пусть |X| = m; |Y | = n. То гда |Y
x
| =
A
n
m
= n
m
= |Y|
x
.
Ут вер жде ние 6: Пусть |X | = m; |Y | = n. То гда чис ло всех инъ ек тив -
ных ото бра же ний f: X ® Y рав но
A
n
m
.
След ст вие: Для S
n
– мно же ст ва всех би ек тив ных ото бра же ний
n-эле мент но го мно же ст ва в се бя име ем: |S
n
| =
A
n
n
= P
n
= n!
При мер 1. Сколь ки ми спо со ба ми мож но рас кра сить квад рат, раз -
де лен ный на че ты ре час ти (ри су нок 1.2.1), пя тью цве та ми:
а) до пус кая ок ра ши ва ние раз ных час тей в один цвет;
б) ес ли раз лич ные час ти ок ра ши ва ют ся раз ны ми цве та ми? Бу -
дем рас смат ри вать ка ж дое рас кра ши ва ние как функ цио наль ное
ото бра же ние мно же ст ва но ме ров час тей квад ра та X = {1, 2, 3, 4}
в мно же ст во цве тов Y, где |Y | = 5. То гда, ис поль зуя ут вер жде ние 5
и 6, име ем:
45
1 2
4 3
Рис. 1.2.1
      Утверждение 4: C nm = C nm+ m +1 .
      Каждому (n,m)-сочетанию B с повторениями, составленному из
элементов множества X = x1, ..., xn поставим в соответствие вектор a(B)
длины n + m + 1 из m нулей и n – 1 единиц такой, что число нулей, на-
ходящихся между (i – 1)-й и i-й единицами, где 2 £ i £ n – 1, будет равно
числу элементов хi, входящих в сочетание B, а число нулей, стоящих пе-
ред первой единицей (после (n – 1)-й единицы), равно числу элемен-
тов х1, (соответственно xn), входящих в сочетание B. Это соответствие
между (n,m)-сочетаниями с повторениями и векторами с (n – 1) едини-
цами и m нулями взаимно однозначно. С другой стороны, число векто-
ров с (n – 1) единицами и m нулями равно числу m-элементных мно-
жеств (номеров нулевых компонентов в векторах), являющихся под-
множествами (n + m + 1)-элементарного множества {1, 2, ..., n + m – 1}
(множества всех номеров компонент в векторах), то есть числу
(n + m – 1, m)-сочетаний без повторений. Таким образом, C nm = C nm+ m +1 .

     Утверждение 5: Обозначим через Y x множество всех отображений
f: X®Y. Пусть |X| = m; |Y | = n. Тогда |Y x| = Anm = nm = |Y|x.

     Утверждение 6: Пусть |X | = m; |Y | = n. Тогда число всех инъектив-
ных отображений f: X ® Y равно Anm .
     Следствие: Для Sn – множества всех биективных отображений
n-элементного множества в себя имеем: |Sn| = Ann = Pn = n!

     Пример 1. Сколькими способами можно раскрасить квадрат, раз-
деленный на четыре части (рисунок 1.2.1), пятью цветами:
                              1                2
                              4                3
                                  Рис. 1.2.1

      а) допуская окрашивание разных частей в один цвет;
      б) ес ли раз лич ные час ти ок ра ши ва ют ся раз ны ми цве та ми? Бу -
дем рас смат ри вать ка ж дое рас кра ши ва ние как функ цио наль ное
ото бра же ние мно же ст ва но ме ров час тей квадра та X = {1, 2, 3, 4}
в множе ство цветов Y, где |Y | = 5. То гда, ис поль зуя ут вер жде ние 5
и 6, име ем:
                                                                          45

Страницы