ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 870
Скачиваний: 9
26
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
Óòâåðæäåíèå 1.10. Ïðîèçâîäÿùàÿ ôóíêöèÿ äëÿ ïîëèíîìèàëüíûõ êîýô-
ôèöèåíòîâ èìååò ñëåäóþùèé âèä:
(
x
1
+
x
2
+
. . .
+
x
n
)
n
=
X
n
1
, n
2
, ..., n
p
≥
0
n
1
+
n
2
+
...
+
n
p
=
n
n
n
1
, n
2
, . . . , n
p
x
n
1
1
x
n
2
2
. . . x
n
p
p
(1
.
10)
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà ñïðàâåäëèâîñòè ðàâåíñòâà (1.10) äî-
ñòàòî÷íî çàìåòèòü, ÷òî êîýôôèöèåíò ïðè
x
n
1
1
x
n
2
2
. . . x
n
p
p
ðàâåí ÷èñëó ñïîñî-
áîâ âûáðàòü èç
n
ñîìíîæèòåëåé
n
1
ñîìíîæèòåëåé, èç êîòîðûõ â ïðîèçâå-
äåíèå âîéäåò ïåðåìåííàÿ
x
1
,
n
2
ñîìíîæèòåëåé, èç êîòîðûõ â ïðîèçâåäåíèå
âîéäåò ïåðåìåííàÿ
x
2
, è òàê äàëåå.
Ñëåäñòâèå 1.
n
n
1
, n
2
, . . . , n
p
=
X
j
n
j
6
=0
n
−
1
n
1
, n
2
, . . . , n
j
−
1
, n
j
−
1
, n
j
+1
, . . . , n
p
(1
.
11)
Äëÿ äîêàçàòåëüñòâà ñëåäñòâèÿ 1 äîñòàòî÷íî çàìåòèòü, ÷òî
(
x
1
+
x
2
+
. . .
+
x
n
)
n
= (
x
1
+
x
2
+
. . .
+
x
n
)
n
−
1
(
x
1
+
x
2
+
. . .
+
x
n
)
.
Îòñþäà ñëåäóåò ðàâåíñòâî êîýôôèöèåíòîâ ïðè ñîîòâåòñòâóþùèõ ñòåïåíÿõ
â ëåâîé è ïðàâîé ÷àñòÿõ ïîñëåäíåãî ðàâåíñòâà:
x
n
1
1
. . . x
n
p
p
n
n
1
, . . . , n
p
=
=
P
j
n
j
6
=0
x
j
n
−
1
n
1
, . . . , n
j
−
1
, n
j
−
1
, n
j
+1
, . . . , n
p
x
n
1
1
x
n
2
2
. . . x
n
j
−
1
j
. . . x
n
p
n
.
Ñëåäñòâèå 2
m
+
q
n
1
, n
2
, . . . , n
p
=
P
(
k
1
,k
2
, ..., k
p
)
≤
(
n
1
,n
2
, ..., n
p
)
k
1
+
k
2
+
...
=
m
m
k
1
, . . . , k
p
·
·
q
n
1
−
k
1
, n
2
−
k
2
, . . . , n
p
Óêàçàííîå ðàâåíñòâî åñòü íåïîñðåäñòâåííîå ñëåäñòâèå ñëåäóþùåãî ñî-
îòíîøåíèÿ äëÿ ïðîèçâîäÿùèõ ôóíêöèé:
(
x
1
+
. . .
+
x
p
)
m
+
q
= (
x
1
+
. . .
+
x
p
)
m
(
x
1
+
. . .
+
x
p
)
q
.
1.4. ÐÀÇÁÈÅÍÈß
27
Ñëåäñòâèå 3
X
n
n
1
, . . . , n
p
(
−
1)
n
2
+
n
4
+
n
6
+
...
=
1
−
(
−
1)
p
2
Ðàâåíñòâî ñëåäñòâèÿ 3 íåïîñðåäñòâåííî âûòåêàåò èç âèäà ïðîèçâîäÿùåé
ôóíêöèè äëÿ ïîëèíîìèàëüíûõ êîýôôèöèåíòîâ, åñëè â (1.10) ïîëîæèòü:
x
1
=
x
3
=
x
5
=
. . .
= +1
x
2
=
x
4
=
x
6
=
. . .
=
−
1
1.4 Ðàçáèåíèÿ
1.4.1 ×èñëî ðàçáèåíèé
Îïðåäåëåíèå. Ðàçáèåíèå êîíå÷íîãî ìíîæåñòâà
X
,
|
X
|
=
n
, åñòü íåóïîðÿ-
äî÷åííûé íàáîð
π
=
{
B
1
, B
2
, . . . , B
k
}
ïîäìíîæåñòâ ìíîæåñòâà
X
òàêèõ,
÷òî
B
i
6
=
∅
äëÿ âñåõ
i
îò 1 äî
k
;
B
i
∩
B
j
=
∅
,
åñëè
i
6
=
j
B
1
∪
B
2
∪
. . .
∪
B
k
=
X
Ìû íàçûâàåì
B
i
êëàññîì (áëîêîì) ðàçáèåíèÿ
π
è ãîâîðèì, ÷òî
π
èìååò
k
êëàññîâ. Ïóñòü
S
(
n, k
)
÷èñëî ðàçáèåíèé
n
- ìíîæåñòâà íà
k
êëàññîâ.
S
(
n, k
)
íàçûâàåòñÿ òàêæå ÷èñëîì Ñòèðëèíãà âòîðîãî ðîäà.
Ðàçáèåíèÿ ñîîòâåòñòâóþò ðàçìåùåíèÿì
n
ðàçëè÷íûõ îáúåêòîâ ïî
k
îäè-
íàêîâûì ÿùèêàì ïðè óñëîâèè, ÷òî êàæäûé ÿùèê íå ïóñò.
Ïðèìåð
S
(4
,
2) = 7
. Äåéñòâèòåëüíî, ÷åòûðå îáúåêòà
{
1
,
2
,
3
,
4
}
ìîæíî ñëåäó-
þùèì îáðàçîì ðàçáèòü íà äâà êëàññà:
{
1
} ∪ {
2
,
3
,
4
}
;
{
3
} ∪ {
1
,
2
,
4
}
{
1
,
2
} ∪ {
3
,
4
}
{
1
,
4
} ∪ {
2
,
3
}
{
2
} ∪ {
1
,
3
,
4
}
{
4
} ∪ {
1
,
2
,
3
}
{
1
,
3
} ∪ {
2
,
4
}
Óñëîâèìñÿ ïîëàãàòü, ÷òî
S
(0
,
0) = 1
.
×èòàòåëü äîëæåí óáåäèòüñÿ, ÷òî äëÿ
n
≥
1
èìåþò ìåñòî ñîîòíîøåíèÿ:
S
(0
, k
) = 0
, ïðè
k >
0
,
S
(
n, k
) = 0
, ïðè
k > n
,
S
(
n,
0) = 0
,
S
(
n,
1) = 1
,
S
(
n,
2) = 2
n
−
1
−
1
,
S
(
n, n
) = 1
,
S
(
n, n
−
1) =
n
2
.
28
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
Óòâåðæäåíèå 1.11. ×èñëà Còèðëèíãà âòîðîãî ðîäà óäîâëåòâîðÿþò ñëå-
äóþùåìó îñíîâíîìó ðåêóððåíòíîìó ñîîòíîøåíèþ:
S
(
n
+ 1
, k
) =
S
(
n, k
−
1) +
kS
(
n, k
)
.
(1
.
12)
Äîêàçàòåëüñòâî. Ðàññìîòðèì òàáëèöó ðàçáèåíèé
n
+ 1
îáúåêòà íà
k
êëàñ-
ñîâ.
1. Äëÿ íåêîòîðûõ ðàçáèåíèé
(
n
+ 1)
-ûé îáúåêò åñòü åäèíñòâåííûé ýëå-
ìåíò â êëàññå. ×èñëî òàêèõ ðàçáèåíèé åñòü
S
(
n, k
−
1)
.
2. Äëÿ äðóãèõ ðàçáèåíèé
(
n
+ 1)
-ûé îáúåêò íå ÿâëÿåòñÿ åäèíñòâåííûì
ýëåìåíòîì êëàññà íè äëÿ êàêîãî êëàññà. Ñëåäîâàòåëüíî, ñóùåñòâóåò
kS
(
n, k
)
òàêèõ ðàçáèåíèé, òàê êàê êàæäîìó ðàçáèåíèþ ìíîæåñòâà
{
1
, . . . , n
}
íà
k
êëàññîâ ñîîòâåòñòâóåò â òî÷íîñòè
k
ðàçáèåíèé, îáðà-
çîâàííûõ äîáàâëåíèåì ýëåìåíòà
n
+ 1
ïîî÷åðåäíî ê êàæäîìó êëàññó.
Òàêèì îáðàçîì, ìû ïðåäñòàâèëè âñå ðàçáèåíèÿ
n
+1
ýëåìåíòà íà
k
êëàñ-
ñîâ â âèäå îáúåäèíåíèÿ íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâ ðàçáèåíèé äâóõ
ïåðå÷èñëåííûõ òèïîâ. Ïîýòîìó
S
(
n
+ 1
, k
) =
S
(
n, k
−
1) +
kS
(
n, k
)
.
Óòâåðæäåíèå 1.12. ×èñëî ñþðúåêòèâíûõ îòîáðàæåíèé ìíîæåñòâà
X
,
|
X
|
=
n
, íà ìíîæåñòâî
Y
(
|
Y
|
=
m
)
ðàâíî
m
!
S
(
n, m
)
.
Äîêàçàòåëüñòâî. Êàæäîå ñþðúåêòèâíîå îòîáðàæåíèå
X
=
{
1
,
2
, . . . , n
}
íà
Y
=
{
y
1
, y
2
, . . . , y
m
}
èíäóöèðóåò ðàçáèåíèå
X
íà
m
ðàçëè÷íûõ êëàñ-
ñîâ
1
,
2
, . . . , m
(â êëàññ
i
ïîïàäàþò âñå òàêèå
x
, ÷òî
f
(
x
) =
y
i
)
; íàîáîðîò,
êàæäîìó ðàçáèåíèþ
X
íà
m
êëàññîâ ñîîòâåòñòâóåò
m
!
ñþðúåêòèâíûõ îòîá-
ðàæåíèé
X
íà
Y
. Äåéñòâèòåëüíî, âûðàæåíèå
m
!
S
(
n, m
)
äàåò ÷èñëî ñïîñî-
áîâ ðàçáèòü
X
íà
m
êëàññîâ, à çàòåì ëèíåéíî óïîðÿäî÷èòü êëàññû, ñêàæåì,
(
B
1
, B
2
, . . . , B
m
)
. Ñâÿæåì ïîñëåäîâàòåëüíîñòü
(
B
1
, B
2
, . . . , B
m
)
ñ ñþðú-
åêòèâíîé ôóíêöèåé
f
, îïðåäåëåííîé ôîðìóëîé
f
(
i
) =
y
j
, åñëè
i
∈
B
j
. Ýòî
óñòàíàâëèâàåò òðåáóåìîå ñîîòâåòñòâèå ìåæäó êîëè÷åñòâîì ñþðúåêòèâíûõ
îòîáðàæåíèé è ÷èñëîì ðàçáèåíèé.
Íèæå ïðèâîäèòñÿ ñïèñîê íåêîòîðûõ îñíîâíûõ ôîðìóë äëÿ êîëè÷åñòâà
ðàçáèåíèé ìíîæåñòâà èç
n
ýëåìåíòîâ íà
k
êëàññîâ
S
(
n, k
)
.
1.4. ÐÀÇÁÈÅÍÈß
29
1. Ôîðìóëà 1.
x
n
=
n
X
k
=0
S
(
n, k
)[
x
]
k
(1
.
13)
×èñëà
S
(
n, k
)
èãðàþò îáðàòíóþ ðîëü ïî îòíîøåíèþ ê ÷èñëàì
s
(
n, k
)
ïîçâîëÿþò ïåðåéòè îò áàçèñà
1
, x, x
2
, . . .
ê áàçèñó
[
x
]
1
,
[
x
]
2
, . . .
Äîêàçàòåëüñòâî. Ðàññìîòðèì âñåâîçìîæíûå îòîáðàæåíèÿ ìíîæåñòâà
X
èç
n
ýëåìåíòîâ
(
|
X
|
=
n
)
âî ìíîæåñòâî
Y
èç
m
ýëåìåíòîâ
(
|
Y
|
=
m
)
. Ñ îä-
íîé ñòîðîíû, ïî óòâåðæäåíèþ 1.1 êîëè÷åñòâî òàêèõ îòîáðàæåíèé åñòü
m
n
.
Ñ äðóãîé ñòîðîíû, êàæäîå òàêîå îòîáðàæåíèå åñòü ñþðúåêòèâíîå îòîáðà-
æåíèå ìíîæåñòâà
X
íà ïîäìíîæåñòâî
B
⊆
Y
. Äëÿ ïðîèçâîëüíîãî ïîäìíî-
æåñòâà
B
⊆
Y
, ãäå
|
B
|
=
k
≤
n
÷èñëî ñþðúåêòèâíûõ ôóíêöèé
f
:
X
→
B
â
ñîîòâåòñòâèè ñ óòâåðæäåíèåì 1.12 ðàâíî
k
!
S
(
n, k
)
. Ó÷èòûâàÿ, ÷òî ïîäìíî-
æåñòâî
B
ìîùíîñòè
k
ìîæíî âûáðàòü
C
k
m
ñïîñîáàìè ïîëó÷àåì ôîðìóëó:
m
n
=
m
X
k
=1
C
k
m
k
!
S
(
n, k
) =
C
1
m
1!
S
(
n,
1) +
. . .
+
C
n
m
n
!
S
(
n, n
)
(1
.
14)
Ðàâåíñòâî (1.14) ìîæíî ðàññìàòðèâàòü êàê ðàâåíñòâî äâóõ ìíîãî÷ëåíîâ
ïåðåìåííîé
x
ïðè âñåõ öåëûõ ïîëîæèòåëüíûõ çíà÷åíèÿõ
x
=
m
. Ñëåäî-
âàòåëüíî, ýòè ìíîãî÷ëåíû òîæäåñòâåííî ðàâíû ìåæäó ñîáîé, òàê êàê èõ
ðàçíîñòü ìîæåò áûòü ëèáî òîæäåñòâåííûì íóëåì, ëèáî äîëæíà èìåòü áåñ-
êîíå÷íîå ÷èñëî íóëåé, ÷òî íåâîçìîæíî. Ñïðàâåäëèâîñòü ôîðìóëû (1.13)
äîêàçàíà.
2. Ôîðìóëà 2.
S
(
n
+ 1
, m
) =
n
X
k
=0
n
k
S
(
k, m
−
1) =
n
X
k
=
m
−
1
n
k
S
(
k, m
−
1)
Äîêàçàòåëüñòâî. Ðàññìîòðèì ìíîæåñòâî âñåõ ðàçáèåíèé ìíîæåñòâà
X
=
{
1
,
2
, . . . , n
+ 1
}
íà
m
êëàññîâ. Êîëè÷åñòâî òàêèõ ðàçáèåíèé åñòü
S
(
n
+ 1
, m
)
. Âñå ðàçáèåíèÿ ðàñïàäàþòñÿ íà ðàçëè÷íûå òèïû, ñîîòâåòñòâó-
þùèå ðàçíûì ïîäìíîæåñòâàì ìíîæåñòâà
X
, ñîäåðæàùèì ýëåìåíò
n
+ 1
.
Äëÿ êàæäîãî
k
-ýëåìåíòíîãî ïîäìíîæåñòâà
B
⊂
X
, ñîäåðæàùåãî ýëåìåíò
n
+ 1
, ñóùåñòâóåò â òî÷íîñòè
S
(
n
+ 1
−
k, m
−
1)
ðàçáèåíèé ìíîæåñòâà
X
íà
m
−
1
êëàññ, ñîäåðæàùèõ
B
â êà÷åñòâå êëàññà. Äåéñòâèòåëüíî, êàæäîå
òàêîå ðàçáèåíèå îäíîçíà÷íî ñîîòâåòñòâóåò ðàçáèåíèþ ìíîæåñòâà
X
\
B
íà
30
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
m
−
1
êëàññ.
k
-ýëåìåíòíîå ïîäìíîæåñòâî
B
⊂
X
, ñîäåðæàùåå ýëåìåíò
n
+ 1
ìîæíî âûáðàòü
n
k
−
1
ñïîñîáàìè. Òàêèì îáðàçîì, èìååì:
S
(
n
+ 1
, m
) =
1+
n
−
(
m
−
1)
X
k
=1
n
k
−
1
S
(
n
+ 1
−
k, m
−
1) =
=
1+
n
−
(
m
−
1)
X
k
=1
n
n
−
k
−
1
S
(
n
+ 1
−
k, m
−
1) =
=
n
X
r
=
m
−
1
n
r
S
(
r, m
−
1) =
n
X
k
=0
n
r
S
(
k, m
−
1)
3. Âåðíåìñÿ åùå ðàç ê ñâÿçè êîìáèíàòîðíûõ îáúåêòîâ ñ èñ÷èñëåíèåì
êîíå÷íûõ ðàçíîñòåé. Èç ôîðìóëû (1.13) ñëåäóåò, ÷òî, íàïðèìåð,
n
4
=
4
X
k
=0
k
!
S
(4
, k
)
n
k
,
(1
.
15)
îòêóäà çàêëþ÷àåì íà îñíîâàíèè ðàçëîæåíèÿ (1.8):
1!
S
(4
,
1) = 1
,
2!
S
(4
,
2) = 14
,
3!
S
(4
,
3) = 36
,
4!
S
(4
,
4) = 24
.
Óêàçàííàÿ ñâÿçü äàåò àëüòåðíàòèâíûé ñïîñîá âû÷èñëåíèÿ ïîñëåäîâàòåëü-
íîñòè
S
(
n, k
)
.
1.4.2 ×èñëà Áåëëà
Îïðåäåëåíèå. Îáùåå ÷èñëî ðàçáèåíèé ìíîæåñòâà
X,
|
X
|
=
n
íà ïðîèç-
âîëüíûå êëàññû íàçûâàåòñÿ ÷èñëîì Áåëëà è îáîçíà÷àåòñÿ
B
(
n
)
. Òàêèì îá-
ðàçîì ïî îïðåäåëåíèþ:
B
(
n
) =
n
X
k
=1
S
(
n, k
)
, n
≥
1
.
Ïîëîæèì ïî îïðåäåëåíèþ
B
(0) = 1
.
Ôîðìóëà 3.
B
(
n
+ 1) =
n
X
k
=0
n
k
B
(
k
)
.