Литература 22 3 основные операции со множествами 4 Основные операции со множествами Определение

• Название: Литература 22 3 основные операции со множествами 4 Основные операции со множествами Определение
• Дата: 23.02.2023
• Размер: 154.25 Kb.
• Имя файла: korablev_lecture_combinatoric.pdf
• Тип: Литература; #951606
• страница: 3 из 4

k
1
, k
2
, . . . , k
n
) уравнения
n
∑
i=1
k
i
= k элемент из мно- жества
Z
n+k
−1 2
следующим образом:
(k
1
, k
2
, . . . , k
n
)
←→ (1, 1, . . . , 1
| {z }
k
1
, 0, 1, . . . , 1
| {z }
k
2
, 0, . . . , 0, 1, 1, . . . , 1
| {z }
k
n
).
Тогда число решений уравнения совпадает с числом наборов длины n + k
− 1,
содержащих ровно k единиц (и ровно n
− 1 ноль). Каждый такой набор можно по- строить, выбрав, на какие из n + k
− 1 мест надо поставить k единиц, а остальные места заполнить нулями. Следовательно число таких наборов равно C
k
n+k
−1

Замечание.
Число C
k
n
совпадает с числом способов разложить k одинаковых
шаров по n различным ящикам. В самом деле, каждое разложение шаров по ящикам
задается такой последовательностью из n чисел k
1
, k
2
, . . . , k
n
, что
n
∑
i=1
k
i
= k. Число
k
i
показывает, сколько шаров лежит в i-ом ящике. Из доказательства теоремы
следует, что число таких последовательностей в точности равно C
k
n
.
Определение.
Пусть X — множество мощности n. Число упорядоченных раз-
биений множества X на m подмножеств мощностей k
1
, . . . , k
m
называется поли- номиальным коэффициентом и обозначается C
k
1
,...,k
m
n
.
Пример.
1. Пусть m = n, и пусть k
1
= k
2
= . . . = k
m
= 1. Тогда упорядоченное
разбиение множества X мощности n на столько же подмножеств мощности 1
— это упорядочивание множества X. Следовательно C
1,...,1
n
= n!.
2. Пусть X =
{x
1
, . . . , x
n
}, и пусть m = 2. Тогда любое упорядоченное разбиение
множества X на два подмножества однозначно определяется выбором первого под-
множества разбиение. Второе подмножество разбиения сдержит все оставшиеся
элементы множества X. Следовательно C
k
1
,k
2
n
= C
k
1
,n
−k
1
n
= C
k
1
n
.
Замечание.
Полиномиальный коэффициент C
k
1
,...,k
m
n
совпадает с числом спосо-
бов разложить n различных шаров (элементов множества X) по m различным
ящикам (упорядоченым подмножествам разбиения) так, чтобы в i-ом ящике ле-
жало ровно k
i
шаров.
Теорема
3.7 (О числе упорядоченных мультимножеств).
Пусть X =
{x
1
, . . . , x
n
} — множество мощности n, и пусть (X, ν) — такое
мультимножество мощности k над множеством X, что ν(x
i
) = k
i
. Тогда число
таких упорядоченных мультимножеств равно C
k
1
,...,k
n
k
.
Доказательство.
Рассмотрим n различных ящиков, помеченных элементами множества X. Тогда каждое упорядоченное мультимножество мощности k над мно- жеством X задает раскладывание k различных шаров (помеченных числами 1, 2, . . . , k)
по этим ящикам. При этом если элемент x
i
множества X стоит на j-ом месте в упо- рядоченном мультимножестве, то шар с номером j лежит в ящике x
i
. Наоборот,

3. СВОЙСТВА КОМБИНАТОРНЫХ ЧИСЕЛ
14
каждому разложению шаров по ящикам можно сопоставить упорядоченное мульти- множество. Следовательно, число таких упорядоченных мультимножеств совпадает с числом способов разложить k различных шаров по n ящикам, то есть с величиной
C
k
1
,...,k
n
k

Теорема
3.8 (О полиномиальных коэффициентах).
C
k
1
,...,k
m
n
=
n!
k
1
!
· . . . · k
m
!
.
Доказательство.
Построение упорядоченного разбиения множества мощности
n на m подмножеств A
1
, . . . , A
m
мощностей k
1
, . . . , k
m
соответственно осуществляется за m шагов:
1-ый шаг: множество A
1
мощности k
1
можно выбрать C
k
1
n
различными способами;
2-ой шаг: множество A
2
мощности k
2
можно выбрать из оставшихся элементов множества X
\ A
1
различными C
k
2
n
−k
1
способами;
m-ый шаг: последнее множество A
m
мощности k
m
можно выбрать C
k
m
n
−k
1
−k
2
−...−k
m
−1
=
C
k
m
k
m
= 1 способом.
По правилу произведения получаем, что
C
k
1
,...,k
m
n
= C
k
1
n
· C
k
2
n
−k
1
· . . . · C
k
m
n
−k
1
−...−k
m
−1
=
=
n!
k
1
!(n
− k
1
)!
·
(n
− k
1
)!
k
2
!(n
− k
1
− k
2
)!
· . . . ·
(n
− k
1
− . . . − k
m
−1
)!
k
m
!0!
=
n!
k
1
! . . . k
m
!

Следствие
3.1 (О числе неупорядоченных разбиений).
Число неупорядоченных разбиений множества мощности n на m подмножеств
мощностей k
1
, . . . , k
m
равно
1
m!
· C
k
1
,...,k
m
n
.
Доказательство.
В самом деле, каждое неупорядоченное разбиение на m под- множеств задает m! упорядоченных разбиений.

Следствие
3.2 (О числах Стирлинга второго рода).
S
k
n
=
1
k!
·
∑
n
1
+...+n
k
=n
C
n
1
,...n
k
n
,
где суммирование ведется по всем натуральным n
1
, . . . , n
k
∈ N.
Доказательство.
Справедливость формулы следует из определения чисел Стир- линга 2-го рода: число S
k
n
равно числу неупорядоченных разбиений множества мощ- ности n на k подмножеств таких мощностей n
1
, . . . , n
k
, что n
1
+ n
2
+ . . . + n
k
= n.

Следствие
3.3 (О сумме полиномиальных коэффициентов).
∑
k
1
+...+k
m
=n
C
k
1
,...,k
m
n
= m
n
,

4. ПРИНЦИП ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ
15
где суммирование ведется по всем целым неотрицательным k
1
, . . . , k
m
∈ N ∪ {0}.
Доказательство.
В самом деле, величина C
k
1
,...,k
m
n
совпадает с числом способов разложить n различных шаров по m различным ящикам так, чтобы в них лежало
k
1
, . . . , k
m
шаров соответственно. С другой стороны, по правилу произведения, число
m
n
совпадает с общим числом способов разложить n различных шаров по m различ- ным ящикам. Теперь искомая формула следует из правила суммы.

Теорема
3.9 (Полиномиальная формула).
(x
1
+ . . . + x
m
)
n
=
∑
k
1
+...+k
m
=n
C
k
1
,...,k
m
n
· x
k
1 1
. . . x
k
m
m
,
где суммирование ведется по всем неотрицательным целым k
1
, . . . , k
m
∈ N ∪ {0}.
Доказательство.
Коэффициент при x
k
1 1
. . . x
k
m
m
в разложении (x
1
+ . . . + x
m
)
n
равен числу способов выбрать слагаемое x
1
ровно k
1
раз, слагаемое x
2
ровно k
2
раз и так далее. Таким образом этот коэффициент равен числу упорядоченных разбиений множества из n множителей на m подмножеств, то есть числу C
k
1
,...,k
m
n

4. Принцип включения-исключения
Теорема
4.1 (Формула включения-исключения).
Пусть X
1
, . . . , X
n
— подмножества множества X. Тогда
n
∪
i=1
X
i
=
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
k
∩
j=1
X
i
j
,
где суммирование берется по всем k = 1, 2, . . . , n и всем возможным непустым
подмножествам мощности k множества
{1, . . . , n}.
Замечание.
В развернутом виде формула включения-исключения имеет вид:
|X
1
∪ X
2
∪ . . . ∪ X
n
| =
n
∑
i=1
|X
i
| −
∑
1 6i6n
|X
i
∩ X
j
| +
∑
1 6i6n
|X
i
∩ X
j
∩ X
k
| − . . . +
(
−1)
n+1
|X
1
∩ X
2
∩ . . . ∩ X
n
|.
Доказательство.
Заметим, что:
1.
n
∏
i=1
(1
− a
i
) = (1
− a
1
)(1
− a
2
) . . . (1
− a
n
) = 1 +
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k
a
i
1
. . . a
i
k
2. Если Y =
n
∩
i=1
X
i
, то χ
Y
(x) =
n
∏
i=1
χ
X
i
(x) по теореме 1.2 (пункт 1) о свойствах характеристической функции.
3.
∑
x
∈X
χ
X
(x) =
|X| по теореме 1.2 (пункт 4) о свойствах характеристической функ- ции.
4. Так как
n
∪
i=1
X
i
=
n
∩
i=1
X
i
, то
n
∪
i=1
X
i
=
n
∩
i=1
X
i
Пусть b
X =
n
∪
i=1
X
i
. Вычислим функцию χ
b
X
(x):

4. ПРИНЦИП ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ
16
χ
b
X
(x) = χ
n
∩
i=1
X
i
(x) = 1
− χ
n
∩
i=1
X
i
(x) = 1
−
n
∏
i=1
χ
X
i
(x) = 1
−
n
∏
i=1
(1
− χ
X
i
(x)) =
=
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
· χ
X
i1
(x)
· . . . · χ
X
ik
(x) =
=
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
· χ
X
i1
∩...∩X
ik
(x).
Тогда
| b
X
| =
∑
x
∈X
χ
b
X
(x) =
∑
x
∈X
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
· χ
X
i1
∩...∩X
ik
(x) =
=
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
∑
x
∈X
χ
X
i1
∩...∩X
ik
(x) =
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
k
∩
j=1
X
i
j
.

Определение.
Перестановка σ
∈ S
n
называется беспорядком, если для
∀i ∈
{1, 2, . . . , n} выполняется σ(i) ̸= i.
Пример.
Перестановка
(
1 2 3 4 2 1 4 3
)
является беспорядком, а перестановка
(
1 2 3 4 2 3 1 4
)
— нет.
Теорема
4.2 (О числе беспорядков).
Число беспорядков d
n
в S
n
равно n!
·
n
∑
k=0
(
−1)
k
k!
.
Доказательство.
Для каждого i = 1, . . . , n положим X
i
=
{σ ∈ S
n
|σ(i) = i} ⊆
S
n
. Тогда
d
n
=
|S
n
| −
n
∪
i=1
X
i
= n!
−
n
∪
i=1
X
i
= n!
−


∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
k
∩
j=1
X
i
j

 .
Заметим, что
k
∩
j=1
X
i
j
=
{σ ∈ S
n
|σ(i
j
) = i
j
,
∀j = 1, . . . , k}. Следовательно
k
∩
j=1
X
i
j
= (n
− k)!
Тогда
n
∪
i=1
X
i
=
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
· (n − k)! =
n
∑
k=1
(
−1)
k+1
· C
k
n
· (n − k)!

4. ПРИНЦИП ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ
17
Следовательно
d
n
= n!
−
n
∑
k=1
(
−1)
k+1
· C
k
n
· (n − k)! = n! −
n
∑
k=1
(
−1)
k+1
·
n!
k!(n
− k)!
· (n − k)! =
= n!(1
−
n
∑
k=1
(
−1)
k+1
·
1
k!
) = n!
·
n
∑
k=0
(
−1)
k
k!
.

Теорема
4.3 (О числе сюръекций).
Пусть X, Y — множества,
|X| = n, |Y | = m. Тогда число различных сюръектив-
ных отображений X
→ Y равно
D
m
n
=
m
∑
k=0
(
−1)
k
· (m − k)
n
· C
k
m
.
Замечание.
Число D
m
n
называется числом Стирлинга первого рода.
Доказательство.
Число сюръекций совпадает с числом разложений n различ- ных шаров по m различным ящикам так, чтобы ни один ящик не был пустым. Обо- значим F — множество всех разложений n различных шаров по m ящикам, и F
i
— множество всех разложений, при которых i-ый ящик пуст. Тогда искомое число сюръекций равно
|F | −
m
∪
i=1
F
i
.
По формуле включения-исключения
m
∪
i=1
F
i
=
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
k
∩
j=1
F
i
j
.
Множество
k
∩
j=1
F
i
j
состоит из таких разложений шаров, при которых ящики с но- мерами i
1
, . . . , i
k
пусты, а остальные разложены произвольным образом. Получаем
k
∩
j=1
F
i
j
= (m
− k)!
Тогда
|F | −
m
∪
i=1
F
i
= m
n
−
∑
{i
1
,...,i
k
}⊆{1,...,n}
(
−1)
k+1
· (m − k)
n
=
= m