ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 872
Скачиваний: 9
1.5. ÏÐÈÍÖÈÏ ÂÊËÞ×ÅÍÈÉ-ÈÑÊËÞ×ÅÍÈÉ
31
Äîêàçàòåëüñòâî. Íàïîìíèì, ÷òî
S
(
n, m
) = 0
ïðè
m > n
.
Òîãäà èìååì ñëåäóþùóþ ïîñëåäîâàòåëüíîñòü î÷åâèäíûõ ðàâåíñòâ:
B
(
n
+ 1) =
n
+1
X
r
=1
S
(
n
+ 1
, r
) =
n
+1
X
r
=1
n
X
k
=0
n
k
S
(
k, r
−
1) =
=
n
X
k
=0
n
k
n
+1
X
r
=1
S
(
k, r
−
1)
!
=
n
X
k
=0
n
k
B
(
k
)
1.5 Ïðèíöèï âêëþ÷åíèé-èñêëþ÷åíèé
Ýòîò ðàçäåë ïîñâÿùåí âàæíîìó êîìáèíàòîðíîìó ìåòîäó ïðèíöèïó
âêëþ÷åíèé-èñêëþ÷åíèé, èçâåñòíîìó òàêæå ïîä íàçâàíèÿìè: ñèìâîëè÷åñêèé
ìåòîä, ïðèíöèï ïåðåêðåñòíîé êëàññèôèêàöèè, ìåòîä ðåøåòà. Ëîãè÷åñêèå
òîæäåñòâî, íà êîòîðîì îñíîâàíû âñå ýòè ìåòîäû, èçâåñòíû äàâíî. Åùå â
1713 ãîäó Ìîíìîð ýôôåêòèâíî èñïîëüçîâàë óïîìÿíóòûé ìåòîä â ðåøåíèè
çíàìåíèòîé çàäà÷è î âñòðå÷àõ (î ÷èñëå ïåðåñòàíîâîê èç
n
ýëåìåíòîâ, â
êîòîðûõ íè îäèí ýëåìåíò íå ñîõðàíÿåò ñâîåé ïîçèöèè).
Ïðèíöèï âêëþ÷åíèé-èñêëþ÷åíèé îäíî èç ôóíäàìåíòàëüíûõ ñðåäñòâ
ïåðå÷èñëèòåëüíîé êîìáèíàòîðèêè. Êðàñîòà ýòîãî ïðèíöèïà ëåæèò íå â ñà-
ìîì ðåçóëüòàòå, à â åãî øèðîêîé ïðèìåíèìîñòè.
Ïðèíöèï âêëþ÷åíèé-èñêëþ÷åíèé â ïåðå÷èñëèòåëüíîé êîìáèíàòîðèêå
åñòü ìåòîä îïðåäåëåíèÿ ìîùíîñòè ìíîæåñòâà S, êîòîðûé íà÷èíàåò ñ áîëü-
øåãî ìíîæåñòâà è êàêèì-ëèáî ïóòåì âû÷èòàåò èëè àííóëèðóåò íåæåëà-
òåëüíûå ýëåìåíòû. Ñíà÷àëà äàåòñÿ ïðèáëèçèòåëüíûé îòâåò, ñîäåðæàùèé
áîëüøåå ÷èñëî ýëåìåíòîâ, çàòåì âû÷èòàåòñÿ ÷èñëî ýëåìåíòîâ, áîëüøåå ÷åì
îøèáêà, ïîëó÷åííàÿ íà ïåðâîì øàãå, ïîêà ìû íå ïðèäåì ê ïðàâèëüíîìó
îòâåòó. Ýòî êîìáèíàòîðíàÿ ñóùíîñòü ïðèíöèïà âêëþ÷åíèÿ-èñêëþ÷åíèÿ.
Äëÿ ïðèìåðà ðàññìîòðèì ïðèíöèï âêëþ÷åíèé-èñêëþ÷åíèé â òåîðåòèêî-
ìíîæåñòâåííîé ôîðìå.
Ïóñòü äàíû äâà êîíå÷íûõ ìíîæåñòâà
A
è
B
.
Òîãäà:
|
A
∪
B
|
=
|
A
|
+
|
B
| − |
A
∩
B
|
.
×òîáû âû÷èñëèòü êîëè÷åñòâî ýëåìåíòîâ â îáúåäèíåíèè äâóõ ìíîæåñòâ,
ìû ñíà÷àëà âû÷èñëÿåì ñóììó èõ ìîùíîñòåé, íî ïðè ýòîì äâàæäû ó÷èòû-
âàåì êàæäûé ýëåìåíò, ïðèíàäëåæàùèé ïåðåñå÷åíèþ ìíîæåñòâ. Âû÷èòàÿ
ìîùíîñòü ïåðåñå÷åíèÿ, ïðèõîäèì ê ïðàâèëüíîìó îòâåòó.
32
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
Ñîâåðøåííî àíàëîãè÷íûå ðàññóæäåíèÿ ïîçâîëÿþò âûïèñàòü ôîðìóëó
äëÿ êîëè÷åñòâà ýëåìåíòîâ â îáúåäèíåíèè òðåõ ìíîæåñòâ
A
,
B
, è
C
:
|
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
| − |
A
∩
B
| − |
A
∩
C
| − |
B
∩
C
|
+
|
A
∩
B
∩
C
|
Âû÷èòàÿ äâàæäû ó÷òåííûå ýëåìåíòû ïîïàðíûõ ïåðåñå÷åíèé, ìû òðèæäû
âû÷ëè ýëåìåíòû, ïðèíàäëåæàùèå ïåðåñå÷åíèþ âñåõ òðåõ ìíîæåñòâ. Äîáàâ-
ëåíèå ìîùíîñòè ïåðåñå÷åíèÿ
A
∩
B
∩
C
ïðèâîäèò ê íóæíîìó ðåçóëüòàòó.
Ïóñòü èìååòñÿ
N
îáúåêòîâ è
n
ðàçëè÷íûõ ñâîéñòâ
α
1
, α
2
, . . . , α
n
.
Êàæäûé èç îáúåêòîâ ìîæåò îáëàäàòü ëþáûì èç ýòèõ ñâîéñòâ (â ëþáîì íà-
áîðå), ò.å. îáëàäàòü ëþáûì íàáîðîì ýòèõ ñâîéñòâ, èëè íå îáëàäàòü íèêàêèì
èç ñâîéñòâ.
Ïóñòü
N
(
α
1
)
÷èñëî îáúåêòîâ îáëàäàþùèõ ñâîéñòâîì
α
1
. Íåêîòîðûå
èç ýòèõ îáúåêòîâ ìîãóò îáëàäàòü è äðóãèìè ñâîéñòâàìè â äîïîëíåíèå ê
α
1
, íî ýòî íåâàæíî. (Íà ñàìîì äåëå â ýòîì è ñîñòîèò âñÿ èäåÿ ìåòîäà
âêëþ÷åíèé-èñêëþ÷åíèé). Ïóñòü òåïåðü
N
(
α
2
)
÷èñëî îáúåêòîâ, îáëàäàþ-
ùèõ ñâîéñòâîì
α
2
, è òàê äàëåå. Ñîîòâåòñòâåííî, ÷åðåç
N
(
α
1
, α
2
)
îáîçíà÷èì
êîëè÷åñòâî îáúåêòîâ, îáëàäàþùèõ äâóìÿ ñâîéñòâàìè: ñâîéñòâîì
α
1
è ñâîé-
ñòâîì
α
2
.
 îáùåì ñëó÷àå ïóñòü
N
(
α
i
1
, α
i
2
, . . . , α
i
s
)
÷èñëî îáúåêòîâ, îáëàäà-
þùèõ ñâîéñòâàìè
α
i
1
, α
i
2
, . . . , α
i
s
(è, áûòü ìîæåò, íåêîòîðûìè äðóãèìè).
Ïóñòü
N
0
÷èñëî ïðåäìåòîâ, íå îáëàäàþùèõ íè îäíèì èç ñâîéñòâ
α
1
, . . . , α
n
.
Ïóñòü
N
(
α
1
)
÷èñëî îáúåêòîâ, íå îáëàäàþùèõ ñâîéñòâîì
α
1
. ×åð-
òîé íàä ñèìâîëîì ñâîéñòâà áóäåì óêàçûâàòü, ÷òî ðå÷ü èäåò îá îáúåêòàõ,
íå îáëàäàþùèõ òàêèì ñâîéñòâîì. Òîãäà â ïðèíÿòîì îáîçíà÷åíèè
N
0
=
N
(
α
1
, α
2
, . . . , α
n
)
.
Òåîðåìà 1.13 (Ôîðìóëà âêëþ÷åíèé-èñêëþ÷åíèé).
N
0
=
N
−
X
i
N
(
α
i
) +
X
1
≤
i<j
≤
n
N
(
α
i
, α
j
)
−
−
X
1
≤
i<j<k
≤
n
N
(
α
i
, α
j
, α
k
) +
. . .
+ (
−
1)
n
N
(
α
1
, . . . , α
n
)
(1
.
16)
Ïðåæäå, ÷åì ïåðåõîäèòü ê äîêàçàòåëüñòâó, âåðíåìñÿ ê ðàíåå ðàññìîò-
ðåííîìó ïðèìåðó ñ òðåìÿ ìíîæåñòâàìè
A, B, C
. Ïóñòü ñâîéñòâîì
α
1
îá-
ëàäàþò âñå ýëåìåíòû ìíîæåñòâà
A
, ñâîéñòâîì
α
2
îáëàäàþò âñå ýëåìåíòû
ìíîæåñòâà
B
, ñâîéñòâîì
α
3
âñå ýëåìåíòû, ïðèíàäëåæàùèå ìíîæåñòâó
C
. Òîãäà î÷åâèäíî, ÷òî êîëè÷åñòâî ýëåìåíòîâ, íå îáëàäàþùèõ íè îäíèì èç
1.5. ÏÐÈÍÖÈÏ ÂÊËÞ×ÅÍÈÉ-ÈÑÊËÞ×ÅÍÈÉ
33
ñâîéñòâ
α
1
, α
2
, α
3
ðàâíî 0 (êàæäûé ýëåìåíò ïðèíàäëåæèò õîòÿ áû îäíîìó
èç ìíîæåñòâ), è â ñîîòâåòñòâèè ñ ôîðìóëîé (1.16) èìååì:
N
0
= 0 =
|
A
∪
B
∪
C
| − |
A
| − |
B
| − |
C
|
+
|
A
∩
B
|
+
|
B
∩
C
|
+
|
A
∩
C
| − |
A
∩
B
∩
C
|
.
Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ïðîâîäèòñÿ èíäóêöèåé ïî
n
÷èñëó ñâîéñòâ.
Ïðè îäíîì ñâîéñòâå
α
ôîðìóëà î÷åâèäíà. Êàæäûé îáúåêò ëèáî îáëàäàåò
ýòèì ñâîéñòâîì, ëèáî íå îáëàäàåò èì. Ïîýòîìó
N
0
=
N
−
N
(
α
)
.
Ïðåäïîëîæèì òåïåðü, ÷òî äëÿ ñëó÷àÿ, êîãäà ÷èñëî ñâîéñòâ ðàâíî
n
−
1
,
ôîðìóëà äîêàçàíà:
N
0
=
N
−
N
(
α
1
)
−
. . .
−
N
(
α
n
−
1
) +
N
(
α
1
, α
2
) +
. . .
+
N
(
α
n
−
2
, α
n
−
1
) + (
−
1)
n
−
1
N
(
α
1
, α
2
, . . . , α
n
−
1
)
.
(1
.
17)
Îòìåòèì î÷åâèäíîå ñîîòíîøåíèå:
N
(
α
1
, α
2
, . . . , α
n
) =
N
(
α
1
, . . . , α
n
−
1
)
−
N
(
α
1
, . . . , α
n
−
1
, α
n
)
(1
.
18)
Ôîðìóëà (1.17) ïî ïðåäïîëîæåíèþ ñïðàâåäëèâà äëÿ ëþáîé ñîâîêóïíî-
ñòè îáúåêòîâ.  ÷àñòíîñòè îíà âåðíà äëÿ ñîâîêóïíîñòè
N
(
α
n
)
ýëåìåíòîâ,
îáëàäàþùèõ ñâîéñòâîì
α
n
. Ïðèìåíèì èíäóêòèâíîå ïðåäïîëîæåíèå ê ñî-
âîêóïíîñòè
N
(
α
n
)
äëÿ âû÷èñëåíèÿ
N
(
α
1
, . . . , α
n
−
1
, α
n
)
:
N
(
α
1
, . . . , α
n
−
1
, α
n
) =
N
(
α
n
)
−
X
1
≤
i
≤
n
−
1
N
(
α
i
, α
n
)+
+
X
1
≤
i<j
≤
n
−
1
N
(
α
i
, α
j
, α
n
) +
. . .
+ (
−
1)
n
−
1
N
(
α
1
, α
2
, . . . , α
n
)
(1
.
19)
Âû÷òåì ðàâåíñòâî (1.19) èç (1.17).  ïðàâîé ÷àñòè ïîëó÷èì òî, ÷òî íóæ-
íî ïðàâóþ ÷àñòü ôîðìóëû âêëþ÷åíèÿ-èñêëþ÷åíèÿ, à â ëåâîé ÷àñòè
ïîëó÷èì ðàçíîñòü (1.18). Òåì ñàìûì ôîðìóëà (1.16) äîêàçàíà.
Äëÿ òîãî, ÷òîáû îáëåã÷èòü âñåñòîðîííåå èñïîëüçîâàíèå ýòîé ôîðìóëû,
ñäåëàåì ñëåäóþùèå çàìå÷àíèÿ. Âî-ïåðâûõ, ëó÷øå âñåãî îíà çàïîìèíàåòñÿ
â ñëåäóþùåé ¾ñèìâîëè÷åñêîé çàïèñè¿:
N
(
α
1
, α
2
, α
3
, . . .
) =
N
[(1
−
α
1
)(1
−
α
2
)(1
−
α
3
)
. . .
]
Ñíà÷àëà âû÷èñëÿåòñÿ ñîäåðæèìîå êâàäðàòíûõ ñêîáîê, à çàòåì çíàê ôóíê-
öèè
N
ïðèìåíÿåòñÿ ê ñëàãàåìûì:
N
[
α
+
β
] =
N
(
α
) +
N
(
β
)
,
N
[
−
α
] =
−
N
[
α
]
,
N
[1] =
N,
N
[(1
−
α
)(1
−
β
)] =
N
(1
−
α
−
β
+
αβ
) =
N
−
N
(
α
)
−
N
(
β
) +
N
(
α, β
)
.
34
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
Äàëåå, êàê âèäíî èç äîêàçàòåëüñòâà ôîðìóëû âêëþ÷åíèé-èñêëþ÷åíèé, ñî-
âîêóïíîñòè îáúåêòîâ, ê êîòîðûì ïðèìåíèìà òåîðåìà, íå îáÿçàíà áûòü ñî-
âîêóïíîñòüþ N âñåõ îáúåêòîâ. Ïîýòîìó:
N
(
α
1
α
2
α
3
α
4
) =
N
[
α
1
(1
−
α
2
)
α
3
(1
−
α
4
)] =
N
(
α
1
α
3
)
−
N
(
α
1
α
2
α
3
)
−
−
N
(
α
1
α
3
α
4
) +
N
(
α
1
α
2
α
3
α
4
)
Âîîáùå, åñëè
n
ðàçëè÷íûõ ñâîéñòâ
α
1
, . . . , α
n
îáúåêòîâ èç ñîâîêóïíîñòè
N
îáúåêòîâ îáîçíà÷èòü
b
1
, b
2
, . . . , b
k
, c
1
, c
2
, . . . , c
n
−
k
, òî
N
[
b
1
b
2
. . . b
k
c
1
c
2
. . . c
n
−
k
] =
N
[
b
1
b
2
. . . b
k
(1
−
c
1
)
. . .
(1
−
c
n
−
k
)]
Ðàññìîòðèì ïðèíöèï âêëþ÷åíèé-èñêëþ÷åíèé â íåñêîëüêî áîëåå îáùåé ôîð-
ìå. Ïóñòü
S
ìíîæåñòâî ñâîéñòâ, êîòîðûìè ýëåìåíòû äàííîãî ìíîæåñòâà
A
ìîãóò îáëàäàòü, à ìîãóò íå îáëàäàòü. Äëÿ ëþáîãî ïîäìíîæåñòâà
T
ìíî-
æåñòâà
S
,
T
⊆
S
, ïóñòü
N
=
(
T
)
÷èñëî îáúåêòîâ ìíîæåñòâà
A
, êîòîðûå
îáëàäàþò â òî÷íîñòè ñâîéñòâàìè èç
T
(òàê ÷òî îíè íå îáëàäàþò íèêàêèìè
äðóãèìè ñâîéñòâàìè èç
T
=
S
\
T
). Ïóñòü
N
≥
(
T
)
÷èñëî îáúåêòîâ ìíî-
æåñòâà
A
, îáëàäàþùèõ ïî ìåíüøåé ìåðå ñâîéñòâàìè èç
T
(è, âîçìîæíî,
êàêèìè-òî äðóãèìè ñâîéñòâàìè).
ßñíî, ÷òî òîãäà:
N
≥
(
T
) =
X
Y
⊇
T
N
=
(
Y
)
,
(1
.
20)
N
=
(
T
) =
X
Y
⊇
T
(
−
1)
|
Y
\
T
|
N
≥
(
Y
)
(1
.
21)
N
=
(
∅
) =
X
Y
(
−
1)
|
Y
|
N
≥
(
Y
)
,
ãäå
Y
ïðîáåãàåò âñå ïîäìíîæåñòâà ìíîæåñòâà
S
.
 òèïè÷íûõ ïðèëîæåíèÿõ ïðèíöèïà âêëþ÷åíèé-èñêëþ÷åíèé îòíîñè-
òåëüíî ëåãêî âû÷èñëèòü
N
≥
(
Y
)
äëÿ
Y
⊆
S
, òàê ÷òî íàìè ïîëó÷åíà îêîí-
÷àòåëüíàÿ ôîðìóëà äëÿ
N
=
(
T
)
.
Ðàñïðîñòðàíåííûì ÷àñòíûì ñëó÷àåì ïðèíöèïà âêëþ÷åíèÿ-èñêëþ÷åíèÿ
ÿâëÿåòñÿ âûïîëíåíèå óñëîâèÿ
N
=
(
T
) =
N
=
(
T
◦
)
, êàê òîëüêî
|
T
|
=
|
T
◦
|
.
 ðàññìàòðèâàåìîì ÷àñòíîì ñëó÷àå êîëè÷åñòâî îáúåêòîâ, îáëàäàþùèõ â
òî÷íîñòè çàäàííûì ìíîæåñòâîì ñâîéñòâ, çàâèñèò íå îò êîíêðåòíîãî íàáî-
ðà ñâîéñòâ, à òîëüêî îò ÷èñëà ðàññìàòðèâàåìûõ ñâîéñòâ. Òàêèì îáðàçîì,
N
≥
(
T
)
çàâèñèò òàêæå òîëüêî îò
|
T
|
è ìû ïîëàãàåì
a
(
n
−
i
) =
N
=
(
T
)
(1
.
22)
1.5. ÏÐÈÍÖÈÏ ÂÊËÞ×ÅÍÈÉ-ÈÑÊËÞ×ÅÍÈÉ
35
è
b
(
n
−
i
) =
N
≥
(
T
)
,
(1
.
23)
åñëè
|
T
|
=
i
.
Èç ôîðìóë (1.20) è (1.21) ïîëó÷àåì, ÷òî ôîðìóëû
b
(
m
) =
m
X
k
=0
m
k
a
(
k
)
,
0
≤
m
≥
n
(1
.
24)
è
a
(
m
) =
m
X
k
=0
m
k
(
−
1)
m
−
k
b
(
k
)
,
0
≤
m
≤
n,
(1
.
25)
ýêâèâàëåíòíû. Ýòî åùå îäíî îòðàæåíèå êîìáèíàòîðíûõ ñîîòíîøåíèé âçà-
èìíîñòè.
1.5.1 Çàäà÷à î ÷èñëå áåñïîðÿäêîâ (Çàäà÷à î âñòðå÷àõ)
 êà÷åñòâå êàíîíè÷åñêîãî ïðèìåðà âîçìîæíîãî ïðèëîæåíèÿ âûâåäåííîé
ôîðìóëû âêëþ÷åíèé-èñêëþ÷åíèé ðàññìîòðèì çíàìåíèòóþ çàäà÷ó î ÷èñëå
áåñïîðÿäêîâ èëè èíâåðñèé.
Ïóñòü ìû õîòèì íàéòè ÷èñëî òàêèõ ïåðåñòàíîâîê
π
∈
σ
n
, êîòîðûå íå
èìåþò íåïîäâèæíûõ òî÷åê, òî åñòü íè îäèí ýëåìåíò íå ñòîèò íà ñâîåì
ìåñòå:
π
(
i
)
6
=
i
äëÿ âñåõ
i
∈ {
1
,
2
, . . . , n
}
. Òàêèì îáðàçîì, ìû èùåì
÷èñëî ïåðåñòàíîâîê
a
1
a
2
. . . a
n
n
÷èñåë
{
1
,
2
, . . . , n
}
, òàêèõ, ÷òî
a
i
6
=
i
,
i
=
1
,
2
, . . . , n
. Òàêèå ïåðåñòàíîâêè áóäåì íàçûâàòü áåñïîðÿäêàìè. Îáîçíà÷èì
èõ ÷èñëî
D
(
n
)
. Òîãäà
D
(0) = 1
, D
(1) = 0
, D
(2) = 1
, D
(3) = 2
.
Ðàññìîòðèì ìíîæåñòâî
σ
n
âñåõ
n
!
ïåðåñòàíîâîê
b
1
b
2
. . . b
n
, è ïóñòü ñâîé-
ñòâî
α
i
ïåðåñòàíîâêè
π
ñîñòîèò â òîì, ÷òî
b
i
=
i
. Òîãäà
N
(
α
i
1
, . . . , α
i
s
) =
(
n
−
s
)!
,
i
1
< . . . < i
s
, ïîñêîëüêó îíè ÿâëÿþòñÿ ïåðåñòàíîâêàìè, â êî-
òîðûõ
s
îáúåêòîâ çàêðåïëåíû íà ñâîèõ ïîçèöèÿõ, à îñòàëüíûå îáúåêòû
ñâîáîäíû. ×èñëî áåñïîðÿäêîâ åñòü
N
0
è ïðèìåíåíèå ôîðìóëû âêëþ÷åíèé-
èñêëþ÷åíèé äàåò ðàâåíñòâî
N
0
=
D
(
n
) =
n
!
−
n
1
(
n
−
1)! +
n
2
(
n
−
2)! +
. . .
. . .
+ (
−
1)
k
n
k
(
n
−
k
)! +
. . . ,
òàê êàê ÷èñëî ñïîñîáîâ âûáîðà
k
íåïîäâèæíûõ òî÷åê èç
n
-ýëåìåíòíîãî
ìíîæåñòâà åñòü
n
k
.