ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 893
Скачиваний: 9
16
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
Òàêèì îáðàçîì, îêîí÷àòåëüíî ïîëó÷àåì:
C
k
m
=
m
k
=
[
m
]
k
k
!
,
åñëè
k
6
= 0
, m
≥
k
;
1
,
åñëè
k
= 0
, m
≥
k
;
0
,
åñëè
m < k.
2 ñïîñîá.
Îïðåäåëèì ìíîæåñòâî
S
k
(èíîãäà îáîçíà÷àåìîå êàê-íèáóäü èíà÷å) êàê
ìíîæåñòâî âñåõ
k
-ýëåìåíòíûõ ïîäìíîæåñòâ (èëè
k
-ïîäìíîæåñòâ) ìíîæå-
ñòâà
S
è ïîëîæèì ïî îïðåäåëåíèþ
n
k
=
S
k
(èãíîðèðóÿ ïðî-
øëîå èñïîëüçîâàíèå ñèìâîëà
n
k
). Ïîäñ÷èòàåì äâóìÿ ñïîñîáàìè ÷èñëî
N
(
n, k
)
ñïîñîáîâ, êîòîðûìè ìîæíî âûáðàòü
k
-ïîäìîæåñòâî
T
ìíîæåñòâà
S
, à çàòåì ëèíåéíî óïîðÿäî÷èòü åãî ýëåìåíòû. Ìíîæåñòâî
T
ìû ìîæåì
âûáðàòü
n
k
ñïîñîáàìè, à çàòåì
k
ñïîñîáàìè âûáðàòü ïåðâûé ïî ïîðÿä-
êó ýëåìåíò ìíîæåñòâà
T
,
k
−
1
ñïîñîáîì âòîðîé ýëåìåíò
T
è òàê äàëåå.
Òàêèì îáðàçîì,
N
(
n, k
) =
n
k
k
!
.
Ñ äðóãîé ñòîðîíû, ìîæíî âçÿòü
n
ñïîñîáàìè ëþáîé ýëåìåíò ìíîæåñòâà
S
â
êà÷åñòâå ïåðâîãî,
n
−
1
ñïîñîáîì ëþáîé èç îñòàâøèõñÿ ýëåìåíòîâ â êà÷åñòâå
âòîðîãî è òàê äàëåå,
k
-ûé ýëåìåíò ìîæíî âûáðàòü èç îñòàâøèõñÿ
n
−
k
+ 1
ñïîñîáîì. Ñëåäîâàòåëüíî,
N
(
n, k
) =
n
(
n
−
1)
. . .
(
n
−
k
+ 1)
.
Èòàê, ìû äàëè êîìáèíàòîðíîå äîêàçàòåëüñòâî òîãî, ÷òî:
n
k
k
! =
n
(
n
−
1)(
n
−
2)
. . .
(
n
−
k
+ 1)
,
è, ñëåäîâàòåëüíî,
n
k
=
n
(
n
−
1)(
n
−
2)
. . .
(
n
−
k
+ 1)
k
!
.
Ïðåæäå, ÷åì äâèãàòüñÿ äàëüøå ñäåëàåì íåáîëüøîå îòñòóïëåíèå, ñâÿ-
çàííîå ñ ââåäåíèåì ïîíÿòèÿ ïðîèçâîäÿùèõ ôóíêöèé.
1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß
17
Ïðîèçâîäÿùèå ôóíêöèè
Ïðîèçâîäÿùèå ôóíêöèè íåèçìåííî è åñòåñòâåííî ïîÿâëÿþòñÿ âî âñåõ ðàç-
äåëàõ ïåðå÷èñëèòåëüíîãî êîìáèíàòîðíîãî àíàëèçà. Ìû áóäåì äåëàòü àê-
öåíò íà íàèáîëåå îðãàíè÷íîì ïðèìåíåíèè ïðîèçâîäÿùèõ ôóíêöèé äëÿ ïî-
ëó÷åíèÿ è ïðîâåðêè êîìáèíàòîðíûõ òîæäåñòâ, êîãäà äðóãèå ìåòîäû ìåíåå
åñòåñòâåííû èëè ìåíåå ýôôåêòèâíû. Ïðîèçâîäÿùèå ôóíêöèè ÷àñòî ïðè-
ìåíÿþòñÿ â êà÷åñòâå ìåòîäà, àëüòåðíàòèâíîãî ìåòîäó ðåêóððåíòíûõ ñîîò-
íîøåíèé, â ÷àñòíîñòè ñ èõ ïîìîùüþ âûâîäÿòñÿ âçàèìíî îáðàòíûå ñîîòíî-
øåíèÿ.
Îïðåäåëåíèå. Ïóòü çàäàíà ïîñëåäîâàòåëüíîñòü
a
1
, a
2
, . . . , a
n
, . . .
(íåâàæíî, êîíå÷íàÿ èëè áåñêîíå÷íàÿ). Ïðîèçâîäÿùåé ôóíêöèåé ïîñëåäîâà-
òåëüíîñòè
a
1
, a
2
, . . . , a
n
, . . .
íàçûâàåòñÿ ôóíêöèÿ
A
(
x
) =
∞
P
n
=0
a
n
x
n
Ïðè
ýòîì âñå ðàññìàòðèâàåìûå ðÿäû â ñëó÷àå áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè
ñ÷èòàþòñÿ ôîðìàëüíî ñõîäÿùèìèñÿ (åñëè ýòè ðÿäû ñõîäÿòñÿ â êàêîé-òî
îáëàñòè ê ôóíêöèè
f
(
x
)
), ïîñêîëüêó ìû èíòåðåñóåìñÿ íå îáëàñòüþ ñõîäè-
ìîñòè ñîîòâåòñòâóþùèõ ðÿäîâ, à ëèøü ñîîòíîøåíèÿìè ìåæäó êîýôôèöè-
åíòàìè òàêèõ ðÿäîâ.
Íàïðèìåð, èç ôîðìóëû:
1
1
−
x
= 1 +
x
+
x
2
+
x
3
+
. . .
+
x
n
+
. . .
âûòåêàåò, ÷òî ôóíêöèÿ
1
1
−
x
ÿâëÿåòñÿ ïðîèçâîäÿùåé ôóíêöèåé äëÿ ïîñëå-
äîâàòåëüíîñòè ÷èñåë
1
,
1
,
1
, . . . ,
1
, . . .
Âîçâîäÿ îáå ÷àñòè ïîñëåäíåãî ðàçëîæåíèÿ â êâàäðàò, ïîëó÷àåì:
1
(1
−
x
)
2
= 1 + 2
x
+ 3
x
2
+
. . .
+ (
n
+ 1)
x
n
+
. . . ,
îòêóäà ñëåäóåò, ÷òî äëÿ ïîñëåäîâàòåëüíîñòè
1
,
2
,
3
, . . . , n, . . .
ïðîèçâîäÿ-
ùåé ôóíêöèåé ÿâëÿåòñÿ ôóíêöèÿ
1
(1
−
x
)
2
.
Íàñ áóäóò èíòåðåñîâàòü ïðîèçâîäÿùèå ôóíêöèè äëÿ ïîñëåäîâàòåëüíî-
ñòåé
a
0
, a
1
, . . . , a
n
, . . .
, òàê èëè èíà÷å ñâÿçàííûõ ñ êîìáèíàòîðíûìè çàäà-
÷àìè. Ñ ïîìîùüþ ïðîèçâîäÿùèõ ôóíêöèé óäàåòñÿ ïîëó÷àòü è èññëåäîâàòü
ñàìûå ðàçíûå ñâîéñòâà ýòèõ ïîñëåäîâàòåëüíîñòåé.
Ïóñòü
B
(
x
) =
∞
P
n
=0
b
n
x
n
ïðîèçâîäÿùàÿ ôóíêöèÿ ïîñëåäîâàòåëüíîñòè
b
1
, b
2
, . . . , b
n
, . . .
è
C
(
x
) =
∞
P
n
=0
c
n
x
n
ïðîèçâîäÿùàÿ ôóíêöèÿ ïîñëåäîâà-
18
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
òåëüíîñòè
c
1
, c
2
, . . . , c
n
, . . .
. Òîãäà èç ðàâåíñòâà
C
(
x
) =
A
(
x
)
B
(
x
)
èìååì
c
0
=
a
0
b
0
;
c
1
=
a
1
b
0
+
a
0
b
1
;
c
2
=
a
2
b
0
+
a
1
b
1
+
a
0
b
2
èëè â îáùåì âèäå:
c
n
=
a
n
b
0
+
a
n
−
1
b
1
+
. . .
+
a
0
b
n
=
n
X
k
=0
a
n
−
k
b
k
.
 òàêîì ñëó÷àå ãîâîðÿò, ÷òî ïîñëåäîâàòåëüíîñòü êîýôôèöèåíòîâ
c
n
åñòü
ñâåðòêà (ïðîèçâåäåíèå Êîøè) ïîñëåäîâàòåëüíîñòåé
a
n
è
b
n
.
Áèíîìèàëüíûå êîýôôèöèåíòû
Ñâî¼ íàçâàíèå áèíîìèàëüíûå êîýôôèöèåíòû ïîëó÷èëè îò ñîîòâåòñòâóþ-
ùåé èì ïðîèçâîäÿùåé ôóíêöèè, ÿâëÿþùåéñÿ ñòåïåíüþ áèíîìà:
(1 +
x
)
m
=
m
X
k
=0
m
k
x
k
.
(1
.
1)
Äëÿ äîêàçàòåëüñòâà ñïðàâåäëèâîñòè íàïèñàííîãî ñîîòíîøåíèÿ (1.1) äîñòà-
òî÷íî çàìåòèòü, ÷òî êîýôôèöèåíò ïðè
x
k
ðàâåí ÷èñëó ñïîñîáîâ, êîòîðûìè
èç
m
ñîìíîæèòåëåé
(1 +
x
)
. . .
(1 +
x
)
ìîæíî âûáðàòü
k
ñîìíîæèòåëåé.
Îòìåòèì íåêîòîðûå âàæíåéøèå ñîîòíîøåíèÿ äëÿ áèíîìèàëüíûõ êîýô-
ôèöèåíòîâ (÷èñåë ñî÷åòàíèé).
1.
C
k
n
=
C
n
−
k
n
(1
.
2)
Ýòî âàæíåéøåå ñîîòíîøåíèå ïðÿìîå ñëåäñòâèå òîãî ôàêòà, ÷òî êàæäîìó
k
-ýëåìåíòíîìó ïîäìíîæåñòâó
Y
⊆
X
îäíîçíà÷íî ñîîòâåòñòâóåò
(
n
−
k
)
-
ýëåìåíòíîå ïîäìíîæåñòâî
X
\
Y
ìíîæåñòâà
X
.
2.
C
k
n
=
C
k
n
−
1
+
C
k
−
1
n
−
1
(1
.
3)
Çàôèêñèðóåì íåêîòîðûé ýëåìåíò
x
èç
n
-ýëåìåíòíîãî ìíîæåñòâà
X
. Ìíî-
æåñòâî
T
âñåõ
k
-ýëåìåíòíûõ ïîäìíîæåñòâ ìíîæåñòâà
X
ðàñïàäàåòñÿ íà
äâà íåïåðåñåêàþùèõñÿ êëàññà:
T
=
T
1
∪
T
2
;
T
1
∩
T
2
=
∅
,
êëàññ
T
1
ïîäìíîæåñòâ, êîòîðûå íå ñîäåðæàò ýëåìåíò
x
, è êëàññ
T
2
ïîäìíî-
æåñòâ, êîòîðûå åãî ñîäåðæàò. Ìîùíîñòü ïåðâîãî êëàññà ñîñòàâëÿåò
C
k
n
−
1
,
à âòîðîãî
C
k
−
1
n
−
1
, òî åñòü ñòîëüêî, ñêîëüêî èìååòñÿ
(
k
−
1)
-ýëåìåíòíûõ
ïîäìíîæåñòâ ìíîæåñòâà
X
\{
x
}
.
1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß
19
Ïðîäåìîíñòðèðóåì ýôôåêòèâíîñòü èñïîëüçîâàíèÿ ïðîèçâîäÿùåé ôóíê-
öèè áèíîìèàëüíûõ êîýôôèöèåíòîâ äëÿ ïîëó÷åíèÿ êîìáèíàòîðíûõ ñîîòíî-
øåíèé, âêëþ÷àþùèõ ÷èñëî ñî÷åòàíèé.
3. Ïîëàãàÿ â (1.1)
x
= 1
ïîëó÷èì:
n
X
k
=0
C
k
n
= 2
n
Ýòà ôîðìóëà ñëåäóåò è èç òîãî, ÷òî ñóììà ñëåâà åñòü ÷èñëî âñåõ ïîäìíî-
æåñòâ n-ýëåìåíòíîãî ìíîæåñòâà.
4.
n
X
k
=0
kC
k
n
=
n
2
n
−
1
.
(1
.
4)
Äèôôåðåíöèðóÿ (1.1) è ïîëàãàÿ
x
=1, ïîëó÷àåì ñîîòíîøåíèå (1.4).
5.
m
+
n
k
=
k
X
s
=0
m
s
n
k
−
s
(1
.
5)
Ðàâåíñòâî
ëåãêî
ñëåäóåò
èç
ñëåäóþùåãî
ðàâåíñòâà
äëÿ
ïðîèçâîäÿùèõ ôóíêöèé:
(1 +
x
)
m
+
n
= (1 +
x
)
m
(1 +
x
)
n
.
Ïîëàãàÿ â (1.5)
m
=
k
=
n
, ïîëó÷èì:
C
n
2
n
=
n
X
r
=0
n
r
2
Îòìåòèì, ÷òî çàäà÷à ïðÿìîãî äîêàçàòåëüñòâà ïîñëåäíåãî ðàâåíñòâà áåç èñ-
ïîëüçîâàíèÿ ïðîèçâîäÿùåé ôóíêöèè äîñòàòî÷íî òðóäíà.
6. Ïîëàãàÿ â (1.1)
x
=
−
1
, ïîëó÷àåì
n
X
k
=0
(
−
1)
k
m
k
= 0
Îòñþäà ñëåäóåò, ÷òî
[
m/
2]
X
k
=0
m
2
k
=
[
m/
2]
X
k
=0
m
2
k
+ 1
= 2
m
−
1
,
ãäå ÷åðåç
[
m/
2]
îáîçíà÷åíà öåëàÿ ÷àñòü ÷èñëà
m/
2
.
20
ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ
Èñ÷èñëåíèå êîíå÷íûõ ðàçíîñòåé
Ïðèâåäåì ïðèìåð èñïîëüçîâàíèÿ áèíîìèàëüíûõ êîýôôèöèåíòîâ â âû÷èñ-
ëèòåëüíîé ìàòåìàòèêå.
Ïóñòü äàíà ôóíêöèÿ
ϕ
, îïðåäåëåííàÿ íà ìíîæåñòâå äåéñòâèòåëüíûõ
(âîçìîæíî öåëûõ) ÷èñåë è ïðèíèìàþùàÿ äåéñòâèòåëüíûå çíà÷åíèÿ. Îïðå-
äåëèì íîâóþ ôóíêöèþ
∆
ϕ
(
x
)
, íàçûâàåìóþ ïåðâîé ðàçíîñòüþ
ϕ
, ôîðìóëîé
∆
ϕ
(
x
) =
ϕ
(
x
+ 1)
−
ϕ
(
x
)
.
Îïåðàòîð
∆
íàçûâàåòñÿ ðàçíîñòíûì îïåðàòîðîì ïåðâîãî ïîðÿäêà; êðàòêî
è î÷åíü óïðîùåííî ìîæíî îïðåäåëèòü èñ÷èñëåíèå êîíå÷íûõ ðàçíîñòåé êàê
èññëåäîâàíèå îïåðàòîðà
∆
. Ìîæíî ïðèìåíèòü îïåðàòîð
∆
k
ðàç è ïîëó÷èòü
k
-ûé ðàçíîñòíûé îïåðàòîð
∆
k
ϕ
(
x
) = ∆(∆
k
−
1
ϕ
(
x
))
.
×èñëî
∆
k
(
x
)
íàçûâàåòñÿ
k
-îé ðàçíîñòüþ
ϕ
â òî÷êå
x
(
∆
k
ϕ
(0)
íàçûâàåòñÿ
k
-îé ðàçíîñòüþ
ϕ
â 0).
Îïðåäåëèì äðóãîé îïåðàòîð
E
, íàçûâàåìûé îïåðàòîðîì ñäâèãà, ôîð-
ìóëîé:
Eϕ
(
x
) =
ϕ
(
x
+ 1)
.
Òàêèì îáðàçîì,
∆ =
E
−
I
, ãäå
I
îçíà÷àåò åäèíè÷íûé îïåðàòîð:
Iϕ
(
x
) =
ϕ
(
x
)
.
Òîãäà ïåðâàÿ ðàçíîñòü ôóíêöèè ìîæåò áûòü çàïèñàíà â âèäå:
∆
ϕ
(
x
) =
ϕ
(
x
+ 1)
−
ϕ
(
x
) =
Eϕ
(
x
)
−
Iϕ
(
x
) = (
E
−
I
)
ϕ
(
x
)
Ðàçíîñòè áîëåå âûñîêèõ ïîðÿäêîâ îïðåäåëÿþòñÿ ðåêóððåíòíûì ñîîòíîøå-
íèåì:
∆
n
ϕ
(
x
) = ∆(∆
n
−
1
ϕ
(
x
)) = ∆
n
−
1
ϕ
(
x
+ 1)
−
∆
n
−
1
ϕ
(
x
) = (
E
−
I
)
((
E
−
I
)
n
−
1
ϕ
(
x
))
.
Îòêóäà ïîëó÷àåì âûðàæåíèå äëÿ
n
-îé ðàçíîñòè:
∆
n
ϕ
(
x
) = (
E
−
I
)
n
ϕ
(
x
) =
n
X
k
=0
(
−
1)
n
−
k
C
k
n
E
k
ϕ
(
x
) =
n
X
k
=0
(
−
1)
n
−
k
C
k
n
ϕ
(
x
+
k
)
 ÷àñòíîñòè,
∆
k
ϕ
(0) =
k
X
i
=0
(
−
1)
k
−
i
k
i
ϕ
(
i
)
(1
.
6)