nasyrov_a_z_nasyrov_z_h_diskretnaya_matematika
.pdfuPRAVNENIQ PO TEORII MNOVESTW
31. wYRAZITE ^EREZ p = (x 2 A) I q = (x 2 B) SLEDU@]IE PREDIKATY:
A) x |
2 |
|
[ |
B , |
2 |
[ |
|
, |
B) x |
2 |
|
\ |
B , |
|
2 |
A |
n |
x = A |
n |
|
B |
2 |
A |
4 |
|||||
W) x |
|
B , |
2 |
B , |
|
G) x |
|
B , |
||||||
|
A |
|
x = A |
|
|
|
A |
|
32. dOKAVITE, ^TO
A) A [ (B \ C) = (A [ B) \ (A [ C) , B) A n (B [ C) = (A n B) \ (A n C) ,
W) (A [ B) n C = (A n C) [ (B n C) , G)o A n (B \ C) = (A n B) [ (A n C) , D)o (A \ B) n C = (A n C) \ (B n C) ,
E) A n B 6= B n A , WOOB]E GOWORQ.
33. dOKAVITE, ^TO
x2= A \ B , x 2= A4B .
A) A4B = A n B , B A ,
B) A4B = A [ B , A \ B = ? ,
W) A B , B A ,
o
G)o A \ B C , A B [ C , D) A n B C , A B [ C .
34. nAJDITE P(M) , ESLI A) M = fa; bg , B)o M = fa; b; cg .
o dOKAVITE, ^TO ( ) = ( ) ( ) .
35. P A \ B P A \ P B
36. ~TO OZNA^AET x 2 A B , x 2= A B ?
37. pRI KAKIH USLOWIQH A B = C D ?
38. dOKAVITE, ^TO
A) A (B [ C) = (A B) [ (A C) , B)o A (B \ C) = (A B) \ (A C) , W)o A (B n C) = (A B) n (A C) , G)o A (B4C) = (A B)4(A C) .
39. nAJDITE DR , |
VR , R , R;1 DLQ SLEDU@]IH BINARNYH OTNO[E- |
|
NIJ R : |
|
|
A) |
R = f(x; y) j x; y |
2 f1; 2; 3; 4g; x < yg , |
B) |
R = f(x; y) j x 2 |
[0; 3]; y 2 [;1; 2]; x2 + 4y2 6 4g . |
|
|
31 |
o |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
nAJDITE DR , VR , R , R;1 DLQ SLEDU@]IH BINARNYH OTNO- |
||||||||||||||||||||
40. |
||||||||||||||||||||
[ENIJ R : |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
A) R = f(x; y) j x 2 f1; 2; 3; 4; 5g; y 2 f12; 16g; y . xg , |
|
|
||||||||||||||||||
B) R = f(a; b) j a; b 2 P (M); a bg , GDE M = fx; yg . |
|
|
||||||||||||||||||
41. dOKAVITE, ^TO |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
A) (R1 |
[ |
R2);1 |
= R;1 |
[ |
R;1 |
, |
B) R1 |
[ |
R2 = R1 |
\ |
R2 . |
|||||||||
o |
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
||||||
dOKAVITE, ^TO |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
42. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
= R;1 |
|
R;1 |
|
|
|
|
|
|
|
|
|
|
|
||||
A) (R1 |
\ |
R2);1 |
\ |
, |
B) R1 |
\ |
R2 = R1 |
[ |
R2 . |
|||||||||||
|
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
||||||
43. nAJDITE KOMPOZICI@ R1 |
R2 , ESLI |
|
|
|
|
|
|
|
||||||||||||
A |
|
|
|
|
(b; y)g fa; bg fx; y; zg , |
|
|
|
||||||||||||
) R1 = f(a; x);(a; y); |
|
|
|
|||||||||||||||||
R2 = f(x; p); (x; q); (z; q)g fx; y; zg fp; qg , |
|
|
|
|||||||||||||||||
B) R1 = f(x; y) j y > x2g R R , |
|
|
|
|
|
|
|
|
||||||||||||
R2 = f(y; z) j z > 2yg R R . |
|
|
|
|
|
|
|
|
||||||||||||
o |
nAJDITE KOMPOZICI@ R1 |
R2 , ESLI |
|
|
|
|
|
|
|
|||||||||||
44. |
|
|
|
|
|
|
|
|||||||||||||
A) R1 = f(x; y) j y > x2g R R , |
|
|
|
|
|
|
|
|
||||||||||||
R2 = f(y; z) j z 6 2y; g R |
R , |
|
|
|
|
|
|
|
|
|||||||||||
B) R1 = f(x; y) j 0 6 x 6 1; 0 |
6 y 6 1 ; xg R R , |
|
|
|||||||||||||||||
R2 = f(y; z) j 0 6 y 6 1; 1 ; y 6 z 6 1g R R . |
|
|
45. pOSTROJTE BINARNOE OTNO[ENIE NA M = fa; b; cg , KOTOROE A) REFLEKSIWNO, SIMMETRI^NO, NO NE TRANZITIWNO,
B) ANTISIMMETRI^NO, TRANZITIWNO, NO NE REFLEKSIWNO.
o pOSTROJTE BINARNOE OTNO[ENIE NA = , KOTOROE
46. M fa; b; cg
A) REFLEKSIWNO, TRANZITIWNO, NO NE SIMMETRI^NO,
B) SIMMETRI^NO, TRANZITIWNO, NO NE REFLEKSIWNO.
47. dOKAVITE, ^TO SLEDU@]IE OTNO[ENIQ R QWLQ@TSQ OTNO[ENIQMI \KWIWALENTNOSTI, NAJDITE RAZBIENIE UKAZANNOGO MNOVESTWA NA KLASSY \KWIWALENTNOSTI:
A) R = (a; a); (b; b); (c; c); (a; b); (b; a) NA a; b; c ,
o |
f |
j |
(x + 2y) . 3 |
g |
|
g f g |
B) |
R = f(x; y) |
|
|
NA Z , |
W) R = f(x; y) j y ; x 2 Zg , x; y 2 (;1; +1) .
48. dOKAVITE, ^TO OTNO[ENIE DELIMOSTI NA MNOVESTWE NATURALXNYH ^ISEL QWLQETSQ ^ASTI^NYM PORQDKOM. qWLQETSQ LI OTNO[ENIE DELIMOSTI ^ASTI^NYM PORQDKOM NA Z ?
32
49. dOKAVITE, ^TO PERESE^ENIE DWUH ^ASTI^NYH PORQDKOW NA DANNOM MNOVESTWE SNOWA QWLQETSQ ^ASTI^NYM PORQDKOM.
o pRIWEDITE PRIMER ^ASTI^NYH PORQDKOW NA = , OB_-
50. M fa; b; cg
EDINENIE KOTORYH NE QWLQETSQ ^ASTI^NYM PORQDKOM.
51. pUSTX A I B | UPORQDO^ENNYE MNOVESTWA. dOKAVITE, ^TO OTNO[ENIE (a; b) 6 (a0; b0) , (a < a0) _ (a = a0 ^ b 6 b0) ZADAET PORQDOK NA A B .
52. pUSTX A I B | NEPERESEKA@]IESQ LINEJNO UPORQDO^ENNYE MNOVESTWA. dOKAVITE, ^TO BINARNOE OTNO[ENIE x 6 y ()
(x 2 A ^ y 2 B) _ (x 2 A ^ y 2 A ^ x 6 y) _ (x 2 B ^ y 2 B ^ x 6 y)
ZADAET LINEJNYJ PORQDOK NA A [ B .
o pRIWEDITE PRIMER LINEJNOGO PORQDKA NA .
53. N N
54. wYQSNITE IN_EKTIWNOSTX, S@R_EKTIWNOSTX I BIEKTIWNOSTX SLEDU@]IH FUNKCIJ:
A) f : [;1; 2] ! [0; 5] , f(x) = x2 , B) f : [;1; 2] ! [0; 4] , f(x) = x2 , W) f : [;2; ;1] ! [1; 4] , f(x) = x2 .
pRIWEDITE PRIMER OTOBRAVENIQ f : N ! N , KOTOROE A) S@R_EKTIWNO, NO NE IN_EKTIWNO,
B) IN_EKTIWNO, NO NE S@R_EKTIWNO.
56. nAJDITE p = f g I q = g f , ESLI
A) f : R ! R , f(x) = x2 , g : R ! R , g(x) = x + 1 ;
B) f : N0 ! N0 , f(n) = n + 1 , g : N0 ! N0 , g(n) = jn ; 1j ,
W)o f : Z Z ! Z , f(m; n) = m + n , g : Z ! Z Z , g(n) = (n; n) .
33
g l a w a 3 kombinatorika
x1. pERESTANOWKI, RAZME]ENIQ I IH KOLI^ESTWO
pRINCIP KOMBINATORNOGO UMNOVENIQ. eSLI SOBYTIE A MOVNO 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.
34
sLEDSTWIE. kOLI^ESTWO WSEH RAZLI^NYH PERESTANOWOK DANNOGO n -MNOVESTWA ZADAETSQ FORMULOJ
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.
x2. 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)
35
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 ZADANNYM ^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.
tEOREMA 2. iMEET MESTO SLEDU@]AQ POLINOMIALXNAQ FORMULA:
(x1 + x2 + : : : + xk)n = PP (n1; n2 ; : : : ; nk)x1n1 x2n2 : : : xnkk ,
W KOTOROJ INDEKSY n1; n2; : : : ; nk MENQ@TSQ OT 0 DO n S SOBL@DENIEM 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 xn11 xn22 : : : 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.
36
x3. 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. 16 |
|
|||||||||||||||||||||||||
PREDYDU]EJ STROKE (SM. RIS. 16). |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
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 |
n |
. |
|
|||||||||
|
; |
|
|
1 |
2 |
|
|
|
n1! n2! |
|
|
k! |
(n ; k)! |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
w REZULXTATE ZAMENY MY POLU^IM ISKOMU@ FORMULU BINOMA |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
k=n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
nX@TONA: (x + y)n = |
P Cnkxkyn;k . |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
k=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
37 |
|
|
|
|
|
|
|
|
|
|
|
|
x4. 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 POWTORENI- k = (n + k ; 1)! .
C(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
(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.
x5. 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.
38
tEOREMA 2. iMEET MESTO SLEDU@]AQ FORMULA WKL@^ENIJ I IS-
KL@^ENIJ: |
|
|
|
|
|
|
n |
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
N(P 1 P2 : : :P n) = N ; |
i=1 |
N(Pi) + |
N(PiPj); |
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i<j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
; |
P |
|
|
|
|
|
|
|
|
+ (;1)nN(P1P2 : : : Pn) . |
||||||||||||||
|
|
|
|
|
|
|
|
|
N(PiPj Pk) + : : : |
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
i<j<k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
pRIMER |
|
|
|
|
|
|
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
2. fORMULA WKL@^ENIJ I ISKL@^ENIJ DLQ n = 3 WYGLQ- |
||||||||||||||||||||||||||||||
DIT TAK |
|
|
|
|
|
|
|
|
; N(P1) ; N(P2) |
; N(P3)+ |
|
|
|
||||||||||||||||||
(P 1P 2 P3) = N |
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
: N |
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
+N(P1P2) + N(P1P3) + N(P2 P3) |
; N(P1P2P3) . |
|||||||||||||||||||
|
|TU FORMULU MOVNO PROILL@STRIROWATX S POMO]X@ RISUNKA, |
||||||||||||||||||||||||||||||
SM. RIS. 17, NA KOTOROM KRUGI WYDELQ@T \LEMENTY, UDOWLETWORQ- |
|||||||||||||||||||||||||||||||
@]IE USLOWIQM P1 , P2 I |
P3 , A WSE MNOVESTWO M IZOBRAVENO W |
||||||||||||||||||||||||||||||
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 |
|
|
|
|
|
P2 |
|
|||||||||||||||||||||||
MER |
2 OZNA^AET ^TO UKAZANNYE \LEMENTY |
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
2 |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
## |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
1 |
|
||||||
DOBAWLQ@TSQ I I UDALQ@TSQ 2 RAZA. mY WI- |
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
2 |
|
|
DIM, ^TO OSTA@TSQ \LEMENTY, POME^ENNYE |
|
|
|
|
|
# |
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
^ISLOM |
+1 , |
|
KOTORYE SOOTWETSTWU@T \LE |
- |
|
|
P3 |
|
|
|
1 |
|
+1 |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
MENTAM, NE UDOWLETWORQ@]IM NI ODNOMU IZ |
|
|
|
|
|
""!! |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
DANNYH SWOJSTW. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rIS. 17 |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"! |
|||
|
oPREDELENIE 2. bESPORQDKOM NAZYWAETSQ TAKAQ PERESTANOWKA ^I- |
||||||||||||||||||||||||||||||
SEL 1; 2; : : : ; n , W KOTOROJ NI ODNO ^ISLO |
|
i |
NE NAHODITSQ NA i -TOM |
||||||||||||||||||||||||||||
MESTE. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
pRIMER 3. sREDI PERESTANOWOK ^ISEL 1; 2; 3 |
IMEETSQ DWA BESPO- |
|||||||||||||||||||||||||||||
RQDKA: |
|
3 1 2 |
|
I 2 3 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
tEOREMA 3. kOLI^ESTWO WSEH BESPORQDKOW n SREDI PERESTANOWOK |
||||||||||||||||||||||||||||||
^ISEL 1; 2; : : : ; n WY^ISLQETSQ PO FORMULE |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
n = n! |
1 |
1 |
|
|
( |
|
1)n |
. |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
; |
|
|
+ : : : + |
|
|
;n! |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
2! |
3! |
|
|
|
|
|
|
|
|
|
||||||||||
|
sLEDSTWIE. lim n |
= |
1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
n!1 n! |
|
e |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
oPREDELENIE 3. lATINSKIM PRQMOUGOLXNIKOM NAZYWAETSQ MAT- |
||||||||||||||||||||||||||||||
RICA m n , SOSTAWLENNAQ IZ ^ISEL 1;2; : : : ; n |
TAK, ^TO NI W ODNOJ |
STROKE, NI W ODNOM STOLBCE \TOJ MATRICY ^ISLA NE POWTORQ@TSQ.
39
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 .
x6. pROIZWODQ]IE FUNKCII
oPREDELENIE 1. oBY^NOJ PROIZWODQ]EJ FUNKCIEJ DLQ POSLEDOWATELXNOSTI u0; u1; : : : ; uk; : : : NAZYWAETSQ STEPENNOJ RQD
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
A(t) = u0 + u1t + u2t2 + |
: : : + uktk + : : : = 1 uktk , |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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! |
|
n |
|
|
||||||||||||||||||
|
|
|
|
|
|
t |
|
|
|
|
0 |
2 |
|
|
|
|
|
||||||||||
|
|
|
|
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 |
. |
||||||||||||||||||||
|
|
|
|
||||||||||||||||||||||||
|
|
(1 ; t)n |
|||||||||||||||||||||||||
(n) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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-
40