Дискретная математика

oPREDELENIE 3. eSLI f : X

! Y , g : Y ! Z | FUNKCII,

TO IH KOMPOZICIEJ NAZYWAETSQ FUNKCIQ (f g) :

X

! Z , KOTORAQ

WY^ISLQETSQ PO PRAWILU (f g)(x) = g(f(x)) DLQ L@BOGO x 2 X .

sWOJSTWO 1. pUSTX f : X ! Y , g : Y ! Z , TOGDA

A) ESLI f

I g c@R_EKTIWNY, TO f g

S@R_EKTIWNA,

B) ESLI f

I g IN_EKTIWNY, TO f g IN_EKTIWNA,

W) ESLI f

I g BIEKTIWNY, TO f

g

BIEKTIWNA.

dOKAZATELXSTWO. pUSTX f I

g

{ c@R_EKTIWNYE FUNKCII. dLQ

DOKAZATELXSTWA S@R_EKTIWNOSTI f

g

RASSMOTRIM PROIZWOLXNYJ

\LEMENT c 2 Z . wWIDU S@R_EKTIWNOSTI FUNKCII g : Y ! Z SU-

]ESTWUET \LEMENT b 2 Y TAKOJ, ^TO c = g(b) . pOSKOLXKU FUNKCIQ

f : X ! Y

TAKVE S@R_EKTIWNA,

TO MOVNO NAJTI \LEMENT a 2 X

TAKOJ, ^TO b = f(a) . iZ RAWENSTW c = g(b) I b = f(a) SLEDUET,

^TO

c = g(f(a)) , T.E.

c = (f g)(a) , A \TO I OZNA^AET S@R_EKTIWNOSTX

FUNKCII f

g .

pUSTX f

I g { IN_EKTIWNYE FUNKCII. dLQ DOKAZATELXSTWA IN_-

EKTIWNOSTI f g RASSMOTRIM PROIZWOLXNYE \LEMENTY x1; x2 2

X ,

x1 = x2 .

wWIDU IN_EKTIWNOSTI f

IMEEM, ^TO f(x1) = f(x2) .

pO-

6

TAKVE IN_EKTIWNA

TO

6

^TO

SKOLXKU FUNKCIQ

g

,

g(f(x1)) = g(f(x2)) ,

I OZNA^AET IN_EKTIWNOSTX KOMPOZICII

f g .

6

w ZAWER[ENIE DOKAZATELXSTWA ZAMETIM, ^TO UTWERVDENIE W) QW-

LQETSQ O^EWIDNYM SLEDSTWIEM UTWERVDENIJ A) I B).

oPREDELENIE 4. oBRATNOJ K FUNKCII f : X

! Y NAZYWAETSQ

FUNKCIQ

f;1 : Y

! X TAKAQ, ^TO y = f(x) () x

= f;1(y)

DLQ

L@BYH x

2 X I y 2 Y .

iZ OPREDELENIQ WYTEKAET, ^TO FUNKCII f I f;1

QWLQ@TSQ WZA-

IMNO OBRATNYMI, T.E. (f;1);1 = f .

sWOJSTWO 2. eSLI OTNO[ENIQ R X Y I R;1 Y X QWLQ@TSQ FUNKCIONALXNYMI, TO ONI OPREDELQ@T WZAIMNO OBRATNYE FUNKCII.

dOKAZATELXSTWO. pUSTX R = ;f , A R;1 = ;g , TOGDA y = f(x) ()

() (x; y) 2 R () (y; x) 2 R;1 () x = g(y) , A \TO I OZNA^AET, ^TO

g = f;1 I f = g;1 .

tEOREMA OB OBRATNOJ FUNKCII. eSLI FUNKCIQ f : X ! Y

BIEKTIWNA, TO SU]ESTWUET OBRATNAQ K NEJ FUNKCIQ f;1 , KOTORAQ

41

TAKVE QWLQETSQ BIEKTIWNOJ.

dOKAZATELXSTWO. iZ BIEKTIWNOSTI FUNKCII f :

X ! Y SLEDUET,

^TO 8y 2 Y 9! x 2 X (y = f(x)) =)1

8y 2 Y 9! x

2 X

(x; y) 2 ;f

=)

=

f

Y

! x

;

;;

, A \TO OZNA^AET,

^TO OTNO[E-

y

2

9

2

X (y; x)

2

) 8

f

;

NIE

;;1

QWLQETSQ FUNKCIONALXNYM I IZ SWOJSTWA 2

SLEDUET,

^TO

FUNKCIQ,

OPREDELQEMAQ ;;1

, QWLQETSQ OBRATNOJ K FUNKCII f .

f

pOSKOLXKU f

QWLQETSQ FUNKCIEJ, TO

8

x

2

X

9

! y

2

Y (y = f(x))

1

=) 8x

2 X 9! y 2 Y (x = f;

(y)) ,

A \TO OZNA^AET BIEKTIWNOSTX FUNK

-

CII

f;1 .

tEOREMA DOKAZANA.

42

g l a w a 3 kombinatorika

x1. pERESTANOWKI, RAZME]ENIQ I IH KOLI^ESTWO

pRINCIP KOMBINATORNOGO UMNOVENIQ. eSLI SOBYTIE A MOV-

NO OSU]ESTWITX m SPOSOBAMI, I NEZAWISIMO OT \TOGO, SOBYTIE B | n SPOSOBAMI, TO OBA SOBYTIQ (SOBYTIE AB ) MOVNO OSU]ESTWITX mn SPOSOBAMI.

pOD n -MNOVESTWOM BUDEM PONIMATX MNOVESTWO IZ n RAZLI^NYH \LEMENTOW, A (n) -NABOR POLU^AETSQ IZ n -MNOVESTWA RAZMNOVENIEM KAVDOGO EGO \LEMENTA W DOSTATO^NO BOLX[OM KOLI^ESTWE KOLI^ESTWE \KZEMPLQROW.

oPREDELENIE 1. pERESTANOWKOJ IZ n \LEMENTOW NAZYWAETSQ UPORQDO^ENNOE n -MNOVESTWO.

oPREDELENIE 2. rAZME]ENIEM IZ n PO k , GDE 0 < k 6 n , NAZYWAETSQ UPORQDO^ENNOE k -PODMNOVESTWO DANNOGO n -MNOVESTWA. rAZME]ENIE IZ n PO k MOVNO REALIZOWATX POSLEDOWATELXNOJ WYBORKOJ k [AROW IZ IME@]IHSQ W URNE n RAZLI^NYH [AROW, PO-

\TOMU k -PODMNOVESTWO ^ASTO NAZYWA@T k -WYBORKOJ.

tEOREMA 1. kOLI^ESTWO WSEH RAZME]ENIJ IZ n PO k NAHODITSQ

PO FORMULE Ak	=	n!	= n(n 1) : : : (n	k + 1) .
n		(n ; k)!	;	;

dOKAZATELXSTWO. pRIMENIM METOD KOMBINATORNOGO UMNOVENIQ. pERWYJ \LEMENT MOVNO WYBRATX n SPOSOBAMI, POSLE \TOGO WTOROJ \LEMENT MOVNO WYBRATX n ; 1 SPOSOBOM I T.D., POSLEDNIJ k -TYJ \LEMENT MOVNO WYBRATX n ; k + 1 SPOSOBOM. zNA^IT, POSLEDOWATELXNAQ WYBORKA OSU]ESTWIMA n(n ; 1) : : : (n ; k + 1) SPOSOBAMI. uMNOVIW I RAZDELIW \TO PROIZWEDENIE NA (n ; k)! , MY POLU^IM ISKOMU@ FORMULU. tEOREMA DOKAZANA.

43

n SPOSOBAMI, SPOSOBAMI I n SPOSOBAMI.

Ak(n) = nk .

sLEDSTWIE. kOLI^ESTWO WSEH RAZLI^NYH PERESTANOWOK DANNOGO n -MNOVESTWA ZADAETSQ FORMULOJ Pn = Ann = n! .

oPREDELENIE 3. uPORQDO^ENNAQ k -WYBORKA DANNOGO (n) -NABORA NAZYWAETSQ RAZME]ENIEM IZ n PO k S POWTORENIQMI.

rAZME]ENIQ IZ n PO k S POWTORENIQMI MOVNO REALIZOWATX, WYNIMAQ k RAZ PO ODNOMU [ARU IZ IME@]IHSQ W URNE n RAZLI^NYH [AROW S POSLEDU@]IM WOZWRA]ENIEM EGO W URNU.

tEOREMA 2. kOLI^ESTWO WSEH RAZME]ENIJ IZ n PO k S POWTORENIQMI ZADAETSQ FORMULOJ

dOKAZATELXSTWO. pERWYJ \LEMENT MOVNO WYBRATX POSLE \TOGO WTOROJ \LEMENT MOVNO WYBRATX TOVE n T.D., POSLEDNIJ k -TYJ \LEMENT MOVNO WYBRATX TAKVE

zNA^IT, POSLEDOWATELXNAQ WYBORKA OSU]ESTWIMA nk SPOSOBAMI PO PRINCIPU KOMBINATORNOGO UMNOVENIQ. tEOREMA DOKAZANA.

pERESTANOWKI S POWTORENIQMI

(n1; n2; : : : ; nk) -NABOR MOVNO POLU^ITX IZ DANNOGO k -MNOVESTWA M = fa1; a2 ; : : : ; akg RAZMNOVENIEM \LEMENTA ai W ni \KZEMPLQRAH,

GDE ni > 0 , i = 1;2; : : : ; k .

oPREDELENIE 1. uPORQDO^ENNYJ (n1; n2; : : : ; nk) -NABOR NAZYWAETSQ PERESTANOWKOJ S POWTORENIQMI.

tEOREMA 1. kOLI^ESTWO WSEH RAZLI^NYH PERESTANOWOK S POWTORENIQMI (n1; n2; : : : ; nk) -NABORA ZADAETSQ FORMULOJ

P (n1; n2; : : : ; nk) = (n1 + n2 + : : : + nk)! : n1!n2! : : : nk!

dOKAZATELXSTWO. wOZXMEM L@BU@ PERESTANOWKU S POWTORENIQMI DANNOGO NABORA I ZAMENIM W NEJ n1 \KZEMPLQROW \LEMENTA a1 NA RAZNYE \LEMENTY a11 ; a12; : : : ; a1n1 . pERESTAWLQQ IH MEVDU SOBOJ, MY POLU^IM n1! PERESTANOWOK, W KOTORYH NET POWTORENIQ \LEMENTOW a1 , NO E]E OSTALISX POWTORENIQ \LEMENTOW a2; a3; : : : ; ak . zAMENQQ IH TAKIM VE OBRAZOM I PERESTAWLQQ MEVDU SOBOJ, POLU^IM OKON^ATELXNO RAZMNOVENIE W n1!n2! : : : nk! RAZ. wSEGO W ITOGE POLU- ^IM (n1 + n2 + : : : + nk)! OBY^NYH PERESTANOWOK (BEZ POWTORENIJ)

44

I, ZNA^IT, P(n1 ; n2; : : : ; nk) n1!n2! : : : nk! = (n1 + n2 + : : : + nk)! .

oTS@DA SLEDUET ISKOMAQ FORMULA. tEOREMA DOKAZANA.

zADA^A O RAZBIENII MNOVESTWA NA PODMNOVESTWA S ZA-

DANNYM ^ISLOM \LEMENTOW. mNOVESTWO M , SOSTOQ]EE IZ n \LEMENTOW, MOVNO RAZBITX P (n1; n2; : : : ; nk) SPOSOBAMI NA NEPERESEKA- @]IESQ PODMNOVESTWA M1; M2; : : : ; Mk , S ZADANNYM KOLI^ESTWOM

\LEMENTOW n1; n2; : : : ; nk , PRI^EM n1 + n2 + : : : + nk = n .

rE[ENIE. kAVDOE RAZBIENIE MNOVESTWA M NA UKAZANNYE PODMNOVESTWA MOVNO ODNOZNA^NO ZAKODIROWATX POSLEDOWATELXNOSTX@ IZ n ^ISEL, ZAPISAW NA i -TOM MESTE \TOJ POSLEDOWATELXNOSTI NOMER TOGO PODMNOVESTWA, W KOTOROE POPAL i -TYJ \LEMENT MNOVESTWA M . w REZULXTATE MY POLU^IM PERESTANOWKU S POWTORENIQMI IZ n1 \KZEMPLQROW ^ISLA 1, n2 \KZEMPLQROW ^ISLA 2 I T.D., nk \KZEMPLQROW ^ISLA k . pOSKOLXKU KOLI^ESTWO TAKIH PERESTANOWOK S POWTORENIQMI RAWNO P (n1; n2; : : : ; nk) , TO STOLXKO VE BUDET I ISKOMYH RAZBIENIJ. zADA^A RE[ENA.

x3. pOLINOMIALXNAQ FORMULA

tEOREMA 1. iMEET MESTO SLEDU@]AQ POLINOMIALXNAQ FORMULA:

(x1 + x2 + : : : + xk)n = PP (n1; n2 ; : : : ; nk)xn1 1 xn2 2 : : : xnkk ,

W KOTOROJ INDEKSY n1 ; n2; : : : ; nk MENQ@TSQ OT 0 DO n S SOBL@DENI-

EM USLOWIQ n1 + n2 + : : : + nk = n .

dOKAZATELXSTWO. lEWAQ ^ASTX POLINOMIALXNOJ FORMULY PREDSTAWLQETSQ W WIDE PROIZWEDENIQ n SKOBOK: (x1 + x2 + : : : + xk)n =

= (x1 +x2 + : : :+xk) (x1 +x2 +: : :+xk) : : : (x1 +x2 + : : :+xk) . pOSLE

RASKRYTIQ SKOBOK PO PRAWILU UMNOVENIQ MNOGO^LENOW, MY POLU^IM SUMMU ODNO^LENOW WIDA xn1 1 xn2 2 : : : xnkk , PRI^EM n1 +n2 +: : :+nk = n . tAKOMU ODNO^LENU SOOTWETSTWUET RAZBIENIE MNOVESTWA IZ n SKOBOK NA k PODMNOVESTW: W i -TOE PODMNOVESTWO BEREM TE SKOBKI, IZ KOTORYH WZQT MNOVITELX xi , i = 1; 2; : : : ; n . zNA^IT, UKAZANNYJ ODNO^LEN WSTRE^AETSQ W KOLI^ESTWE, RAWNOM ^ISLU RAZBIENIJ MNOVESTWA IZ n SKOBOK NA k PODMNOVESTW S ^ISLOM \LEMENTOW n1; n2; : : : ; nk . sOGLASNO PREDYDU]EJ ZADA^E \TO KOLI^ESTWO RAWNO P (n1; n2; : : : ; nk) , ^TO I ZAWER[AET DOKAZATELXSTWO POLINOMIALXNOJ FORMULY.

45

x4. sO^ETANIQ I IH SWOJSTWA

oPREDELENIE 1. sO^ETANIEM IZ n PO k NAZYWAETSQ NEUPORQDO^ENNOE k -PODMNOVESTWO DANNOGO n -MNOVESTWA.

tEOREMA 1. kOLI^ESTWO WSEH SO^ETANIJ IZ n PO k WY^ISLQETSQ

PO FORMULE Ck

=

n!

;

0 6 k 6 n .

n

k!(n ; k)!

dOKAZATELXSTWO. iZ KAVDOGO k -\LEMENTNOGO PODMNOVESTWA MOV-

NO POLU^ITX k!

RAZME]ENIJ, PO\TOMU Cnk k! = Ank . oTS@DA POLU-

^AEM, ^TO Cnk =

1

Ank =

n!

. tEOREMA DOKAZANA.

k!

k!(n ; k)!

sO^ETANIE IZ n PO k MOVNO REALIZOWATX ODNOWREMENNOJ WYBOR-

KOJ k [AROW IZ IME@]IHSQ W URNE n RAZLI^NYH [AROW.

sWOJSTWO 1. C0

= Cn

= 1 .

n

n

sWOJSTWO 2. Cnn;k = Cnk | SIMMETRI^NOSTX.

sWOJSTWO 3. Ck + Ck+1 = Ck+1 .

n

n

n+1

dOKAZATELXSTWO SWOJSTW 1 { 3 MOVNO PROWESTI, ISPOLXZUQ FOR-

MULU DLQ ^ISLA SO^ETANIJ.

s POMO]X@ SWOJSTW 1,2,3 MOVNO WY-

1

1

STROITX TAK NAZYWAEMYJ TREUGOLXNIK pAS-

1

2

1

KALQ, W n -NOJ STROKE KOTOROGO RASPOLOVE-

1

3

3

1

NY Cn0 ; Cn1; : : : ; Cnn

I KAVDOE ^ISLO WNUT-

1

4

6

4

1

RI \TOGO TREUGOLXNIKA PO SWOJSTWU 3

RAW-

NO SUMME DWUH ^ISEL, STOQ]IH NAD NIM W

rIS. 19

PREDYDU]EJ STROKE (SM. RIS. 19).

tEOREMA 2. iMEET MESTO SLEDU@]AQ FORMULA, NAZYWAEMAQ FOR-

n

MULOJ BINOMA nX@TONA:

(x + y)n =

Cnkxkyn;k:

k=0

P

dOKAZATELXSTWO. pRIMENIW POLINOMIALXNU@ FORMULU POLU^IM

(x + y)n =

P (n1; n2)xn1 yn2 . sDELAEM ZAMENU: n1 = k , TOGDA

n1+n2

=n

= n k I

P

(n1

+ n2)!

n!

k

n

2

P (n ; n

) =

=

= C

.

;

1

2

n1! n2!

k!

(n ; k)!

n

w REZULXTATE ZAMENY MY POLU^IM ISKOMU@ FORMULU BINOMA

k=n

nX@TONA: (x + y)n =

P Cnkxkyn;k .

k=0

46

x5. sO^ETANIQ S POWTORENIQMI

oPREDELENIE 1. sO^ETANIEM IZ n PO k S POWTORENIQMI NAZYWAETSQ ODNOWREMENNAQ (NEUPORQDO^ENNAQ) k -WYBORKA IZ (n) -NABORA. pRIMER 1. iMEETSQ 5 SO^ETANIJ IZ 2 \LEMENTOW a I b PO 4 S

POWTORENIQMI: aaaa , aaab , aabb , abbb , bbbb .

tEOREMA 1. kOLI^ESTWO WSEH SO^ETANIJ IZ n PO k S POWTORE-

NIQMI ZADAETSQ FORMULOJ Ck = (n + k ; 1)! .

(n) k!(n ; 1)!

dOKAZATELXSTWO. kAVDOE SO^ETANIE IZ n \LEMENTOW a1; a2 ; : : : ; an PO k S POWTORENIQMI MOVNO ZAKODIROWATX PERESTANOWKOJ IZ k ^I- SEL 1 I n ; 1 ^ISLA 0 SLEDU@]IM OBRAZOM. pI[EM STOLXKO RAZ 1, SKOLXKO WZQTO \LEMENTA a1 , ZATEM 0; DALEE PI[EM STOLXKO RAZ 1, SKOLXKO IMEETSQ a2 , ZATEM SNOWA 0 I T.D.; W KONCE PI[EM STOLXKO

RAZ 1, SKOLXKO RAZ WSTRE^AETSQ W SO^ETANII \LEMENT			an . pOSKOLX-
KU KOLI^ESTWO PERESTANOWOK IZ k ^ISEL 1 I n ; 1			^ISLA 0 RAWNO
P (k; n	;	1) = (n + k ; 1)! , TO STOLXKO VE BUDET I SO^ETANIJ S PO-
		k!(n ; 1)!
WTORENIQMI. tEOREMA DOKAZANA.

zADA^A O RAZDA^E PODARKOW. kOLI^ESTWO RE[ENIJ W NEOTRICATELXNYH CELYH ^ISLAH DIOFANTOWA URAWNENIQ x1+x2+: : :+xn = k

RAWNO C(kn) .

rE[ENIE. kAVDOMU RE[ENI@ \TOGO URAWNENIQ ODNOZNA^NO SOOTWETSTWUET SO^ETANIE IZ n \LEMENTOW a1; a2; : : : ; an PO k S POWTORENIQMI, W KOTOROM \LEMENT ai WSTRE^AETSQ xi RAZ, i = 1; 2; : : : n . pO\TOMU ISKOMOE KOLI^ESTWO RE[ENIJ DANNOGO DIOFANTOWA URAWNENIQ RAWNO ^ISLU SO^ETANIJ C(kn) . zADA^A RE[ENA.

x6. fORMULA WKL@^ENIJ I ISKL@^ENIJ

pUSTX DANO MNOVESTWO M IZ N \LEMENTOW I NA \TOM MNOVESTWE OPREDELENY PREDIKATY P1(x) , P2(x); : : : ; Pn(x) . oBOZNA^IM ^EREZ N(Pi) KOLI^ESTWO \LEMENTOW, DLQ KOTORYH Pi(x) ISTINNO, ^EREZ N(P i) { KOLI^ESTWO \LEMENTOW, DLQ KOTORYH Pi(x) LOVNO, ^EREZ N(PiPj) { KOLI^ESTWO \LEMENTOW, DLQ KOTORYH Pi(x) ^ Pj(x) ISTINNO I T.D.

47

tEOREMA O WKL@^ENIQH I ISKL@^ENIQH. iMEET MESTO SLE-

DU@]AQ FORMULA WKL@^ENIJ I ISKL@^ENIJ:

								n	n
								P	P
N(P 1 P2 : : :P n) = N ; i=1 N(Pi) + i<j										N(PiPj);
							n
;							P	N(PiPjPk) + : : :		+ (;1)nN(P1P2 : : : Pn) . (1)
							i<j<k

dOKAZATELXSTWO PROWEDEM INDUKCIEJ PO ^ISLU n .

bAZA INDUKCII. eSLI n = 1 , TO FORMULA WKL@^ENIJ I ISKL@-

^ENIJ WYGLQDIT TAK: N(P1) = N

; N(P1) , ^TO O^EWIDNO.

iNDUKCIONNOE PREDPOLOVENIE. pUSTX FORMULA WKL@^ENIJ I IS-

KL@^ENIJ WERNA DLQ n SWOJSTW.

{AG INDUKCII. dOKAVEM (1) DLQ n + 1 SWOJSTWA. pOSKOLXKU

N(P 1P 2 : : :P kPn+1) = N(P1P 2 : : : Pn) ; N(P 1P2 : : : P nPn+1) ,

(2)

A PO INDUKCIONNOMU PREDPOLOVENI@ IZ FORMULY (1) SLEDUET, ^TO

n

n

N(P 1P 2 : : :P nPn+1) = N(Pn+1);

i=1

N(Pi Pn+1)+ N(PiPjPn+1);

i<j

n

P

P

;

i<j<k

N(PiPjPkPn+1) + : : : + (;1)nN(P1P2 : : : PnPn+1) ,

(3)

P

PRAWYE ^ASTI FORMUL (1) I (3), POLU-

TO, PODSTAWLQQ W FORMULU (2)

^AEM POSLE PRIWEDENIQ PODOBNYH ^LENOW SLEDU@]EE RAWENSTWO:

n+1

n+1

N(P 1P 2 : : :P nP n+1) = N ;

i=1

N(Pi) +

i<j

N(PiPj);

n+1

P

P

N(PiPjPk) + : : : + (;1)n+1N(P1P2 : : : PnPn+1) .

;

i<j<k

P

{AG INDUKCII PRODELAN, T.K. MY POLU^ILI FORMULU (1) DLQ n+1 SWOJSTWA. tEOREMA DOKAZANA.

pRIMER 1. fORMULA WKL@^ENIJ I ISKL@^ENIJ DLQ n = 3 WYGLQ-

DIT TAK: N(P 1P 2 P3) = N ; N(P1) ; N(P2) ; N(P3)+

+N(P1P2) + N(P1P3) + N(P2 P3) ; N(P1P2P3) .

|TU FORMULU MOVNO PROILL@STRIROWATX S POMO]X@ RISUNKA, SM. RIS. 20, NA KOTOROM KRUGI WYDELQ@T \LEMENTY, UDOWLETWORQ- @]IE USLOWIQM P1 , P2 I P3 , A WSE MNOVESTWO M IZOBRAVENO W

48

WIDE PRQMOUGOLXNIKA. ~ISLA NA \TOM RISUNKE POKAZYWA@T SKOLXKO

##

RAZ DANNYE \LEMENTY DOBAWLQ@TSQ I UDALQ@TSQ W PRAWOJ ^ASTI

FORMULY WKL@^ENIJ I ISKL@^ENIJ, NAPRI-

P1

#

MER

2 OZNA^AET ^TO UKAZANNYE \LEMENTY

P2

2

1

3

1

DOBAWLQ@TSQ I I UDALQ@TSQ 2

RAZA. mY WI-

DIM, ^TO OSTA@TSQ \LEMENTY, POME^ENNYE

2

2

!

^ISLOM

+1 ,

KOTORYE SOOTWETSTWU@T \LE

-

"

P3

1

MENTAM, NE UDOWLETWORQ@]IM NI ODNOMU IZ

""!!

DANNYH SWOJSTW.

rIS. 20

x7. bESPORQDKI, LATINSKIE PRQMOUGOLXNIKI

oPREDELENIE 1. bESPORQDKOM NAZYWAETSQ TAKAQ PERESTANOWKA ^ISEL 1; 2; : : : ; n , W KOTOROJ NI ODNO ^ISLO i NE NAHODITSQ NA i -TOM MESTE.

pRIMER 1. sREDI PERESTANOWOK ^ISEL 1; 2; 3								IMEETSQ DWA BESPO-
RQDKA: 3 1 2 I 2 3 1 .
tEOREMA O BESPORQDKAH. kOLI^ESTWO WSEH BESPORQDKOW n SRE-
DI PERESTANOWOK ^ISEL 1; 2; : : : ; n					WY^ISLQETSQ PO FORMULE
1		1				(	1)n
n = n!		;			+ : : : +		;n!	.
	2!		3!

dOKAZATELXSTWO. oBOZNA^IM ^EREZ Pi(x) SWOJSTWO OZNA^A@]EE, ^TO W PERESTANOWKE x NA i -TOM MESTE NAHODITSQ ^ISLO i . tOGDA

ISKOMOE KOLI^ESTWO BESPORQDKOW n RAWNO N(P 1 P2 : : :P n) , DLQ NAHOVDENIQ KOTOROGO PRIMENIM FORMULU WKL@^ENIJ I ISKL@^ENIJ. pOSKOLXKU KOLI^ESTWO N WSEH PERESTANOWOK RAWNO n! , A TAKVE

N(Pi) = (n ; 1)! , N(Pi Pj) = (n ; 2)! , : : : , N(P1P2 : : : Pn) = 1 , TO

n = n! ; Cn1(n ; 1)! + Cn2(n ; 2)! ; Cn3(n ; 3)! + : : : + (;1)n Cnn 0! = = n! 1 ; 1 + 2!1 ; 3!1 + : : : + (;n1)! n .

sLEDSTWIE. dOLQ BESPORQDKOW SREDI WSEH PERESTANOWOK STRE-

MITSQ K ^ISLU 1=e PRI n ! 1 , T.E. lim n = 1 . n!1 n! e

oPREDELENIE 2. lATINSKIM PRQMOUGOLXNIKOM NAZYWAETSQ MATRICA m n , SOSTAWLENNAQ IZ ^ISEL 1;2; : : : ; n TAK, ^TO NI W ODNOJ STROKE, NI W ODNOM STOLBCE \TOJ MATRICY ^ISLA NE POWTORQ@TSQ.

49

eSLI m RAWEN SWOEMU MAKSIMALXNO WOZMOVNOMU ZNA^ENI@ n , TO GOWORQT O LATINSKOM KWADRATE. iMEETSQ TEOREMA, ^TO L@BOJ LATINSKIJ PRQMOUGOLXNIK MOVNO DOPOLNITX DO LATINSKOGO KWADRATA. eSLI W PERWOJ STROKE LATINSKOGO PRQMOUGOLXNIKA m n ^ISLA 1; 2; : : : ; n RASPOLOVENY W PORQDKE WOZRASTANIQ, TO OSTALXNYE STRO^KI QWLQ@TSQ BESPORQDKAMI, PO\TOMU KOLI^ESTWO LATINSKIH

PRQMOUGOLXNIKOW 2 n RAWNO n .

x8. pROIZWODQ]IE FUNKCII

oPREDELENIE 1. oBY^NOJ PROIZWODQ]EJ FUNKCIEJ DLQ POSLEDOWATELXNOSTI u0; u1; : : : ; uk; : : : NAZYWAETSQ STEPENNOJ RQD

A(t) = u0 + u1t + u2t2 + : : : + uktk + : : : =

1 uktk ,

P

k=0

A \KSPONENCIALXNOJ PROIZWODQ]EJ FUNKCIEJ NAZYWA@T RQD

u2

2

uk

k

1

uk

k

E(t) = u0 + u1t +

2!

t + : : : +

k!

t + : : : =

X

k!

t .

k=0

pRIMER 1. dLQ POSLEDOWATELXNOSTI 1; 1; : : : ;1; : : :

IMEEM

1

1

1

tk

A(t) =

X

tk =

;

E(t) =

X1

= et .

1

;

k!

t

0

2

n

k=0

k=0

pRIMER 2. dLQ POSLEDOWATELXNOSTI

Cn; Cn; Cn; : : : ; Cn ;0; 0; : : :

OBY^NAQ PROIZWODQ]AQ FUNKCIQ OPREDELQETSQ PO FORMULE BINOMA

n

nX@TONA: A(t) =

P

Cktk

= (1 + t)n .

n

k=0

pRIMER 3. oBY^NOJ PROIZWODQ]EJ FUNKCIEJ DLQ POSLEDOWATELX-

NOSTI Ck

, GDE k = 0; 1; 2; : : : QWLQETSQ FUNKCIQ

A(t) =

1

.

(n)

n

(1 ; t)n

rE[ENIE. rAZLOVIM FUNKCI@ A(t) = (1 ; t);

W STEPENNOJ RQD

PO FORMULE, DOKAZYWAEMOJ W KURSE MATEMATI^ESKOGO ANALIZA.

A(t) = (1 ; t);n =

1

(;n)(;n ; 1) k: :!: (;n ; k + 1) (;t)k =

X

k=0

= 1

n(n + 1) : : : (n + k ; 1) tk =

1

Ck tk:

X

k!

X

(n)

k=0

k=0

pRI NAHOVDENII FORMUL DLQ SUMM OBY^NO PYTA@TSQ IH WYRAZITX ^EREZ IZWESTNYE PROIZWODQ]IE FUNKCII, PODSTAWLQQ KONKRET-

50