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

UptoLike

ВУЗ: 

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

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

Рубрика: 

7
Пример 3. Даны два конечных множества
1
A и
2
A с числом элементов nAN
=
)(
1
и
mAN =)(
2
соответственно. Требуется определить число элементов прямого про-
изведения этих множеств, т.е. ).(
21
AAN
×
Решение. Из определения прямого или декартова произведения двух множеств
следует, что любой элемент множества
2
1
AA × может быть получен в результате
выполнения действия из двух этапов. Первый этап - выбрать произвольный элемент
множества
1
A и поместить его на первое место в упорядоченной паре, ясно, что
;
1
nn =
второй этап - выбрать произвольный элемент множества
2
A
и поместить его
на второе место в паре, .
2
mn = Теперь, согласно принципу умножения, получаем
.)(
2121
mnnnAAN
⋅
=
⋅
=
×
(5)
Следствие - обобщение. Аналогично, или используя метод математической индук-
ции, можно доказать, что если даны конечные множества
),...,2,1( kiA
i
=
с
,)(
ii
nAN = то
....)...(
2121 kk
nnnAAAN
⋅
⋅
⋅
=
×
×
× (6)
В частности, если
−
A
конечное множество с ,)( n
A
N
=
то
.)(
kk
nAN =
(7)
Замечание. По определению прямого произведения множеств элементами множе-
ства AAAA
k
×××= ... (справа
k
символов
A
разделены 1−
k
знаками прямо-
го произведения множеств) являются упорядоченные последовательности (кортежи)
длины ,
k
составленные из возможно повторяющихся элементов множества
A
. В
комбинаторике такие соединения (комбинации) из элементов множества
A
называ-
ют размещениями из n элементов по
k
элементов с повторениями. Они отлича-
ются друг от друга или порядком элементов, или составом; их число обозначают
).,(
k
n
A
Значит из формулы (7) следует, что .)(),(
kk
nANknA ==
Пример 4. Пусть даны множество
{
}
kXNxxxX
k
=
=
)(,,...,,
21
и множество
{}
;)(,,...,,
21
lYNyyyY
l
==
и пусть на множестве
с областью значений
Y
за-
дана функция .:
Y
X
f
→ Спрашивается: сколько всего имеется различных функ-
ций указанного вида ?
Решение.
Каждую функцию
Y
X
f
→: можно задать таблицей 1
Таблица 1.
1
x
2
x
. . . . . . . .
s
x
. . . . . . .
k
x
1
i
y
2
i
y
. . . . . . . .
s
i
y
. . . . . . .
k
i
y
Где −
s
i
y это тот элемент множества ,
Y
который поставлен в соответствие
.Xx
s
∈
Нижняя строка таблицы 1 ),...,(
1 k
ii
yy есть кортеж длины
k
, составленный
из элементов множества ,
Y
т.е. элемент множества
.
k
Y
Так как число различных
элементов множества ,
k
Y согласно формуле (7), равно ,
k
l то имеется ровно
k
l
различных функций с областью определения X и областью значений .
Y
Следствие. Пусть
{}
{
}
,1;0,1;0 == YX
m
тогда число различных функций вида
Y
X
f
→: равно ,2
2
m
ибо .2)(,2)( == YNXN
m
Другими словами: число

Страницы