ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 869
Скачиваний: 9
1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß
21
÷òî äà¼ò ÿâíóþ ôîðìóëó äëÿ
k
-îé ðàçíîñòè â òåðìèíàõ çíà÷åíèé
ϕ
(0)
, ϕ
(1)
, . . . , ϕ
(
k
)
.
Íåòðóäíî îáðàòèòü ôîðìóëó (1.6) è âûðàçèòü
ϕ
(
n
)
÷åðåç
∆
i
ϕ
(0)
. Èìåííî,
ϕ
(
n
) =
E
n
ϕ
(0) = (∆ + 1)
n
ϕ
(0) =
n
X
k
=0
n
k
ϕ
(0)
(1
.
7)
Íàïèøåì òåïåðü â ñòðîêó çíà÷åíèÿ:
. . . ϕ
(
−
2)
ϕ
(
−
1)
ϕ
(0)
ϕ
(1)
ϕ
(2)
. . .
Åñëè âíèçó íàïèñàòü ìåæäó êàæäîé ïàðîé ïîñëåäîâàòåëüíûõ ÷ëåíîâ
ϕ
(
i
)
, ϕ
(
i
+ 1)
èõ ðàçíîñòü
ϕ
(
i
+ 1)
−
ϕ
(
i
) = ∆
ϕ
(
i
)
, òî ïîëó÷èì ïîñëåäîâà-
òåëüíîñòü:
. . .
∆
ϕ
(
−
2) ∆
ϕ
(
−
1) ∆
ϕ
(0) ∆
ϕ
(1) ∆
ϕ
(2)
. . .
Ïîâòîðåíèå ýòîé ïðîöåäóðû ïðèâîäèò ê òàáëèöå ðàçíîñòåé ôóíêöèè
ϕ
,
k
-
àÿ ñòðîêà êîòîðîé ñîñòîèò èç çíà÷åíèé
∆
k
ϕ
(
n
)
. Äèàãîíàëü, íà÷èíàþùàÿñÿ
â
ϕ
(0)
è èäóùàÿ íàïðàâî âíèç, ñîñòîèò èç ðàçíîñòåé
∆
k
ϕ
(0)
â 0. Íàïðèìåð,
ïóñòü
ϕ
(
n
) =
n
4
. Òàáëèöà ðàçíîñòåé (íà÷èíàþùàÿñÿ ñ
ϕ
(0)
) âûãëÿäèò òàê:
0
1
16
81
256
625
. . .
1
15
65
175
369
14
50
110
194
36
60
84
24
24
0
Èç ôîðìóëû (1.7) ñëåäóåò, ÷òî:
n
4
=
n
1
+ 14
n
2
+ 36
n
3
+ 24
n
4
+ 0
n
5
+
. . .
(1
.
8)
 ýòîì ñëó÷àå, òàê êàê
n
4
ìíîãî÷ëåí ÷åòâåðòîé ñòåïåíè è
n
k
ïðè
ôèêñèðîâàííîì
k
åñòü ìíîãî÷ëåí ñòåïåíè
k
, íàïèñàííîå âûøå ðàçëîæåíèå
îáðûâàåòñÿ ïîñëå ÷ëåíà
24
n
4
, òî åñòü
∆
k
0
4
= 0
, åñëè
k >
4
(èëè, áîëåå
îáùèì îáðàçîì,
∆
k
n
k
= 0
, åñëè
k >
4
).
Ïðåäûäóùåå ðàññóæäåíèå, êîíå÷íî, íå îòíîñèòñÿ ëèøü ê ôóíêöèè
n
4
.
Ïîäîáíûå ðàññóæäåíèÿ ïðèâîäÿò ê ñëåäóþùèì ðåçóëüòàòàì.
22
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
1. Ôóíêöèÿ
ϕ
ïîëèíîì ñòåïåíè, íå ïðåâîñõîäÿùåé
d
, òîãäà è òîëüêî
òîãäà, êîãäà
∆
d
+1
ϕ
(
n
) = 0
(èëè
∆
d
ϕ
(
n
)
ïîñòîÿííàÿ).
2. Åñëè ìíîãî÷ëåí
ϕ
(
n
)
ñòåïåíè, íå ïðåâîñõîäÿùåé
d
, ðàçëîæåí â ðÿä
ïî áàçèñó
n
k
,
0
≤
k
≤
d
, òî êîýôôèöèåíòû ðàçëîæåíèÿ åñòü
∆
k
ϕ
(0)
, òî åñòü
ϕ
(
n
) =
n
X
k
=0
∆
k
ϕ
(0)
n
k
.
Åùå îäíà ñâÿçü êîìáèíàòîðíûõ îáúåêòîâ ñ èñ÷èñëåíèåì êîíå÷íûõ ðàçíî-
ñòåé äàåòñÿ ôîðìóëîé (1.15).
Ðàçëîæåíèÿ
Ñóùåñòâóåò òåñíàÿ ñâÿçü ìåæäó ïîäìíîæåñòâàìè ìíîæåñòâ è ðàçëîæåíè-
ÿìè öåëîãî ÷èñëà.
Îïðåäåëåíèå. Ðàçëîæåíèå
n
åñòü ïðåäñòàâëåíèå ÷èñëà
n
â âèäå óïî-
ðÿäî÷åííîé ñóììû ïîëîæèòåëüíûõ öåëûõ. Íàïðèìåð, ñóùåñòâóåò âîñåìü
ðàçëîæåíèé ÷èñëà 4, à èìåííî:
1 + 1 + 1 + 1
3 + 1
2 + 1 + 1
1 + 3
1 + 2 + 1
2 + 2
1 + 1 + 2
4
Åñëè ðàçëîæåíèå
σ
ñîäåðæèò â òî÷íîñòè
k
ñëàãàåìûõ, òî ãîâîðÿò, ÷òî
σ
èìååò
k
÷àñòåé è íàçûâàåòñÿ
k
-ðàçëîæåíèåì. Åñëè
a
1
+
a
2
+
. . .
+
a
k
k
-ðàçëîæåíèå
σ
÷èñëà
n
, îïðåäåëèì
(
k
−
1)
-ýëåìåíòíîå ïîäìíîæåñòâî
Θ(
σ
)
(èëè
(
k
−
1)
-ïîäìíîæåñòâî) ìíîæåñòâà
{
1
,
2
, . . . , n
−
1
}
ôîðìóëîé:
Θ(
σ
) =
{
a
1
, a
1
+
a
2
, . . . , a
1
+
a
2
+
. . .
+
a
k
−
1
}
.
Ýòà ôîðìóëà óñòàíàâëèâàåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå (áèåêöèþ)
ìåæäó âñåìè
k
-ðàçëîæåíèÿìè è
(
k
−
1)
-ïîäìíîæåñòâàìè
Θ(
σ
)
ìíîæåñòâà
{
1
,
2
, . . . , n
−
1
}
. Ñëåäîâàòåëüíî, ñóùåñòâóåò
n
−
1
k
−
1
k
-ðàçëîæåíèé
n
è
2
n
−
1
ðàçëîæåíèé
n
. Ðàçëîæåíèå ÷àñòî ñõåìàòè÷íî ïðåäñòàâëÿþò, ðè-
ñóÿ â ñòðîêó
n
òî÷åê è
k
−
1
ðàçäåëÿþùóþ âåðòèêàëüíóþ ÷åðòó. Òî÷êè
ðàçäåëÿþòñÿ ïî
k
ëèíåéíî óïîðÿäî÷åííûì ¾îòäåëåíèÿì¿, ÷èñëà òî÷åê â
1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß
23
îòäåëåíèÿõ äàþò
k
-ðàçëîæåíèå ÷èñëà
n
. Íàïðèìåð, ïîñëåäîâàòåëüíîñòü
• | •• | • | • | • • • | ••
ñîîòâåòñòâóåò ðàçëîæåíèþ
1 + 2 + 1 + 1 + 3 + 2
.
Äðóãàÿ ïðîáëåìà, òåñíî ñâÿçàííàÿ ñ ðàçëîæåíèÿìè, åñòü çàäà÷à ïîäñ÷å-
òà ÷èñëà
N
(
n, k
)
ðåøåíèé óðàâíåíèÿ
x
1
+
x
2
+
. . .
+
x
k
=
n
â íåîòðèöàòåëüíûõ öåëûõ ÷èñëàõ. Ðåøåíèå òàêîãî óðàâíåíèÿ íàçûâàåòñÿ
ñëàáûì ðàçëîæåíèåì
n
íà
k
÷àñòåé, èëè ñëàáûì
k
-ðàçëîæåíèåì ÷èñëà
n
.
(Ðåøåíèå â ïîëîæèòåëüíûõ öåëûõ ÷èñëàõ åñòü ïðîñòî
k
-ðàçëîæåíèå
n
.)
Åñëè ìû ïîëîæèì
y
1
=
x
1
+ 1
, y
2
=
x
2
+ 1
, . . . , y
k
=
x
k
+ 1
, òî ïîëó÷èì,
÷òî
N
(
n, k
)
åñòü êîëè÷åñòâî ðåøåíèé â ïîëîæèòåëüíûõ ÷èñëàõ óðàâíåíèÿ
y
1
+
y
2
+
. . .
+
y
k
=
n
+
k,
òî åñòü ÷èñëî
k
-ðàçëîæåíèé ÷èñëà
n
+
k
.
Òàêèì îáðàçîì,
N
(
n, k
) =
n
+
k
−
1
k
−
1
.
Ïîäîáíûì æå ïðèåìîì (íàéòè åãî ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ) äîêàçû-
âàåòñÿ, ÷òî ÷èñëî ðåøåíèé íåðàâåíñòâà
x
1
+
x
2
+
. . .
+
x
k
≤
n
â íåîòðèöà-
òåëüíûõ öåëûõ ÷èñëàõ åñòü
n
+
k
k
.
k
-ïîäìíîæåñòâî
T n
ìíîæåñòâà
S
èíîãäà íàçûâàþò
k
-ñî÷åòàíèåì èç
S
áåç ïîâòîðåíèé. Òàê âîçíèêàåò çàäà÷à ïîäñ÷åòà ÷èñëà
k
-ñî÷åòàíèé èç
S
ñ ïîâòîðåíèÿìè; òî åñòü ìû âûáèðàåì
k
ýëåìåíòîâ èç ìíîæåñòâà
S
, íå
âçèðàÿ íà èõ ïîðÿäîê è äîïóñêàÿ ïîâòîðÿþùèåñÿ ýëåìåíòû. Îáîçíà÷èì
÷èñëî òàêèõ ñïîñîáîâ
n
+
k
k
.
Íàïðèìåð,
3
2
= 6
.
Åñëè
S
=
{
1
,
2
,
3
}
, òî ïîäõîäÿùèå ñî÷åòàíèÿ åñòü
11
,
22
,
33
,
12
,
13
è
23
.
Ýêâèâàëåíòíîå, íî áîëåå òî÷íîå îïðåäåëåíèå è èññëåäîâàíèå ñî÷åòàíèé ñ
ïîâòîðåíèÿìè ìîæåò áûòü ïðîâåäåíî, åñëè ââåñòè ïîíÿòèå ìóëüòèìíîæå-
ñòâà. Íà èíòóèòèâíîì óðîâíå ìóëüòèìíîæåñòâî åñòü ìíîæåñòâî ñ ïîâòî-
ðÿþùèìèñÿ ýëåìåíòàìè, íàïðèìåð
{
1
,
1
,
2
,
5
,
5
}
. Áîëåå òî÷íî, êîíå÷íîå
ìóëüòèìíîæåñòâî
M
íà ìíîæåñòâå
S
åñòü ôóíêöèÿ
ν
:
S
→
N
(
N
- ìíî-
æåñòâî íàòóðàëüíûõ ÷èñåë), òàêàÿ, ÷òî
P
x
∈
S
ν
(
x
)
<
∞
ðàññìàòðèâàåòñÿ êàê
÷èñëî ïîâòîðåíèé ýëåìåíòà
x
. Öåëîå ÷èñëî
P
x
∈
S
ν
(
x
)
íàçûâàþò ìîùíîñòüþ
èëè ÷èñëîì ýëåìåíòîâ
M
è îáîçíà÷àþò
|
M
|
. Åñëè
S
=
{
x
1
, x
2
, . . . , x
n
}
,
24
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
è
ν
(
x
i
) =
a
i
, òî ìû ïèøåì
M
=
{
x
a
i
i
, . . . , x
a
n
n
}
. Ìíîæåñòâî âñåõ
k
-
ìóëüòèìíîæåñòâ íà
S
îáîçíà÷àåòñÿ ñèìâîëîì
S
k
.
Åñëè
S
=
{
y
1
, . . . , y
n
}
è ìû ïîëîæèì
x
i
=
ν
(
y
i
)
, òî óâèäèì, ÷òî
n
k
.
åñòü ÷èñëî ðåøåíèé â íåîòðèöàòåëüíûõ öåëûõ ÷èñëàõ óðàâ-
íåíèÿ
x
1
+
x
2
+
. . .
+
x
n
=
k.
Ýòî ÷èñëî, êàê ìû âèäåëè, åñòü
n
+
k
−
1
n
−
1
.
(1
.
9)
Ïðÿìîå êîìáèíàòîðíîå äîêàçàòåëüñòâî óòâåðæäåíèÿ (1.9) òàêîâî. Ïóñòü
{
a
1
, a
2
, . . . , a
k
}
,
1
≤
a
1
< a
2
< . . . < a
k
≤
n
+
k
−
1
, åñòü
k
-ïîäìíîæåñòâî
ìíîæåñòâà
[
n
+
k
−
1] =
{
1
,
2
, . . . , n
+
k
−
1
}
. Ïîëîæèì
b
i
=
a
i
−
i
+ 1
.
Òîãäà
{
b
1
, b
2
, . . . , b
n
}
k
-ìóëüòèìíîæåñòâî íà ìíîæåñòâå
[
n
]
.
Îáðàòíî, åñëè äàíî
k
-ìóëüòèìíîæåñòâî
1
≤
b
1
≤
b
2
≤
b
k
≤
n
íà
[
n
]
,
òî îïðåäåëèâ
a
i
ôîðìóëîé
a
i
=
b
i
+
i
−
1
, âèäèì, ÷òî
{
a
1
, a
2
, . . . , a
}
åñòü
k
-ïîäìíîæåñòâî ìíîæåñòâà
[
n
+
k
−
1]
. Ñëåäîâàòåëüíî, ìû îïðåäåëèëè
âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó
[
n
]
k
è
[
n
+
k
−
1]
k
,
÷òî è òðåáîâàëîñü äîêàçàòü.
Ïîó÷èòåëåí ïîäõîä ê ìóëüòèìíîæåñòâàì ñ òî÷êè çðåíèÿ ïðîèçâîäÿùèõ
ôóíêöèé. Cîâåðøåííî àíàëîãè÷íî ïðîâåäåííîìó èññëåäîâàíèþ ïîäìíî-
æåñòâ ìíîæåñòâà
S
=
{
x
1
, x
2
, . . . , x
n
}
èìååì
(1 +
x
1
+
x
2
1
+
. . .
)(1 +
x
2
+
x
2
2
+
. . .
)
. . .
(1 +
x
n
+
x
2
n
+
. . .
) =
X
ν
:
S
→
N
Y
x
i
∈
S
x
ν
(
x
i
)
i
Ïîëîæèì
x
i
=
x
. Òîãäà
(1 +
x
+
x
2
+
. . .
)
n
=
X
ν
x
ν
(
x
1
)+
...
+
ν
(
x
n
)
=
X
Ì íà S
x
|
M
|
=
X
k
≥
0
n
k
x
k
.
Íî,
(1 +
x
+
x
2
+
. . .
)
n
= (1
−
x
)
−
n
=
X
k
≥
0
−
n
k
(
−
1)
k
x
k
,
òàê ÷òî
n
k
= (
−
1)
k
−
n
k
=
n
+
k
−
1
k
1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß
25
Ïîÿâëåíèå ýëåãàíòíîé ôîðìóëû
n
k
= (
−
1)
k
−
n
k
íå ñëó÷àéíî. Ýòî ïðîñòåéøèé ïðèìåð êîìáèíàòîðíîé òåîðèè âçàèìíîñòè.
1.3.5 Ïîëèíîìèàëüíûå êîýôôèöèåíòû
Óòâåðæäåíèå 1.9. Ïóñòü
X
ìíîæåñòâî
n
ðàçëè÷íûõ îáúåêòîâ è ïóñòü
n
1
, n
2
, . . . , n
p
íåîòðèöàòåëüíûå öåëûå ÷èñëà, óäîâëåòâîðÿþùèå óñëîâèþ
n
1
+
n
2
+
. . .
+
n
p
=
n
; êîëè÷åñòâî ðàçìåùåíèé
n
îáúåêòîâ ïî ÿ÷åéêàì
Y
1
, . . . , Y
p
, ïðè êîòîðûõ êàæäàÿ ÿ÷åéêà ñîäåðæèò
n
1
, n
2
, . . . , n
p
îáúåê-
òîâ ñîîòâåòñòâåííî, åñòü
n
n
1
, n
2
, . . . , n
p
=
n
!
n
1
!
n
2
!
. . . n
p
!
,
åñëè
n
1
+
n
2
+
. . .
+
n
p
=
n,
0
,
åñëè
n
1
+
n
2
+
. . .
+
n
p
6
=
n.
Äîêàçàòåëüñòâî. Ïóñòü
n
1
+
n
2
+
. . .
+
n
p
=
n
. ßùèê
Y
1
ìîæíî íàïîë-
íèòü
n
n
1
ðàçëè÷íûìè ñïîñîáàìè, ïîñëå ÷åãî ÿùèê
Y
2
ìîæíî íàïîë-
íèòü
n
−
n
1
n
2
ñïîñîáàìè è òàê äàëåå.
Ñëåäîâàòåëüíî, èñêîìîå ÷èñëî ðàçìåùåíèé ðàâíî:
n
n
1
, n
2
, . . . , n
p
=
n
n
1
n
−
n
1
n
2
n
−
n
1
−
n
2
n
3
. . .
n
p
n
p
=
=
n
!
n
1
!(
n
−
n
1
)!
·
(
n
−
n
1
)!
n
2
!(
n
−
n
1
−
n
2
)!
·
·
(
n
−
n
1
−
n
2
)!
n
3
!(
n
−
n
1
−
n
2
−
n
3
)!
·
. . .
·
n
p
!
n
p
!
=
=
n
!
n
1
!
n
2
!
n
3
!
. . . n
p
!
.