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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

1.2.2 Раз ме ще ния, со че та ния и пе ре ста нов ки
1) На бор эле мен тов x
1
, x
2
, ..., x
m
из мно же ст ва X = {x
1
, ..., x
n
} на зы ва -
ет ся вы бор кой объ е ма m из n эле мен тов или, ина че, (n, m)-вы бор кой.
Вы бор ка на зы ва ет ся упо ря до чен ной, ес ли по ря док сле до ва ния эле -
мен тов в ней за дан. Две упо ря до чен ные вы бор ки, раз ли чаю щие ся лишь
по ряд ком сле до ва ния эле мен тов, счи та ют ся раз лич ны ми.
Ес ли по ря док сле до ва ния эле мен тов в вы бор ке не яв ля ет ся су ще -
ст вен ным, то та кая вы бор ка на зы ва ет ся не упо ря до чен ной.
2) В вы бор ках мо гут до пус кать ся или не до пус кать ся по вто ре ния
эле мен тов. Упо ря до чен ная (n,m)-вы бор ка, в ко то рой эле мен ты мо гут
по вто рять ся, на зы ва ет ся (n , m )-раз ме ще ни ем с по вто ре ния ми. Ес ли эле -
мен ты упо ря до чен ной (n, m)-вы бор ки по пар но раз лич ны, то она на зы -
ва ет ся (n,m)-раз ме ще ни ем без по вто ре ний или про сто (n, m)-раз ме ще ни -
ем. Бу дем, кро ме то го (n,n)-раз ме ще ния без по вто ре ний на зы вать пе ре -
ста нов ка ми мно же ст ва X. Не упо ря до чен ная (n,m)-вы бор ка, в ко то рой
эле мен ты мо гут по вто рять ся, на зы ва ет ся (n,m)-со че та ни ем с по вто ре -
ния ми. Ес ли эле мен ты не упо ря до чен ной (n,m)-вы бор ки по пар но раз -
лич ны, то она на зы ва ет ся (n,m)-со че та ни ем без по вто ре ний или про сто
(n,m)-со че та ни ем. За ме тим, что лю бое (n,m)-со че та ние мож но рас смат -
ри вать как m-эле мент ное под мно же ст во n-эле мент но го мно же ст ва.
При мер: Пусть Х = {1, 2, 3}. То гда:
а) <1,1>, <1,2>, <1,3>, <2,1>, <2,2>, <2,3>, <3,1>, <3,2>, <3,3> —
это (3,2)-раз ме ще ния с по вто ре ния ми;
б) <1,2>, <1,3>, <2,1>, <2,3>, <3,1>, <3,2> — это <3,2>-раз ме -
ще ния;
в) {1,2}, {1,3}, {2,3} — это (3,2)-со че та ния.
Чис ло (n,m)-раз ме ще ний с по вто ре ния ми обо зна ча ем че рез
A
n
m
,
а без по вто ре ний — че рез
A
n
m
. Чис ло пе ре ста но вок n-эле мент но го мно -
же ст ва обо зна ча ем че рез P
n
(то есть P
n
=
A
n
n
). Чис ло (n,m)-со че та ний с
по вто ре ния ми обо зна ча ем че рез
C
n
m
, а без по вто ре ний — че рез
C
n
m
.
Ут вер жде ние 1:
A
n
m
= n
m
.
Дей ст ви тель но, ка ж дое (n,m)-раз ме ще ние с по вто ре ния ми яв ля -
ет ся упо ря до чен ной по сле до ва тель но стью дли ны m, при чем ка ж дый
43
      1.2.2 Размещения, сочетания и перестановки

      1) Набор элементов x1, x2, ..., xm из множества X = {x1, ..., xn} называ-
ется выборкой объема m из n элементов или, иначе, (n, m)-выборкой.
      Выборка называется упорядоченной, если порядок следования эле-
ментов в ней задан. Две упорядоченные выборки, различающиеся лишь
порядком следования элементов, считаются различными.
      Если порядок следования элементов в выборке не является суще-
ственным, то такая выборка называется неупорядоченной.

      2) В выборках могут допускаться или не допускаться повторения
элементов. Упорядоченная (n,m)-выборка, в которой элементы могут
повторяться, называется (n,m)-размещением с повторениями. Если эле-
менты упорядоченной (n, m)-выборки попарно различны, то она назы-
вается (n,m)-размещением без повторений или просто (n, m)-размещени-
ем. Будем, кроме того (n,n)-размещения без повторений называть пере-
становками множества X. Неупорядоченная (n,m)-выборка, в которой
элементы могут повторяться, называется (n,m)-сочетанием с повторе-
ниями. Если элементы неупорядоченной (n,m)-выборки попарно раз-
личны, то она называется (n,m)-сочетанием без повторений или просто
(n,m)-сочетанием. Заметим, что любое (n,m)-сочетание можно рассмат-
ривать как m-элементное подмножество n-элементного множества.

      Пример: Пусть Х = {1, 2, 3}. Тогда:
      а) <1,1>, <1,2>, <1,3>, <2,1>, <2,2>, <2,3>, <3,1>, <3,2>, <3,3> —
это (3,2)-размещения с повторениями;
      б) <1,2>, <1,3>, <2,1>, <2,3>, <3,1>, <3,2> — это <3,2>-разме-
щения;
      в) {1,2}, {1,3}, {2,3} — это (3,2)-сочетания.

      Число (n,m)-размещений с повторениями обозначаем через Anm ,
а без повторений — через Anm . Число перестановок n-элементного мно-
жества обозначаем через Pn (то есть Pn = Ann ). Число (n,m)-сочетаний с
повторениями обозначаем через C nm , а без повторений — через C nm .

      Утверждение 1: Anm = nm.
      Действительно, каждое (n,m)-размещение с повторениями явля-
ется упорядоченной последовательностью длины m, причем каждый
                                                                            43

Страницы