Martynyuk_A_N_Diskretnaya_matematika
.pdf( & ' P
' & {A=( 1 , a2i, …, ani)| aj1i=aj2i=…=ajl i} @n1,…, An
$ A aj2i, aj3i, …, ajl i.
? 8 C @n + 5 , 6 8 4 + 5 ,
C 6 j1, …, jJ, + - , A + 5 j2, j3, …, jJ.
4 &.
D 491,92,91,93= |
0, a, 0, b |
1, b, 1, c |
|
1, b, 1, d |
|
0 & ` D 4 13(D 4)=G3, & G3: |
|
G391,92,93 = |
0, a, b |
1, b, c |
|
1, b, d |
|
D A l=2, j1=1, j2=2, 9 12(@n) : 5 (@n). < 4 + (@n)
9 8 8 5- 9 .
>. > & ` n 9 ' & $, 8 & % &'-
' (a, …, a) n.
4 &. 1 & ` - & '. S 8 1,2,…n(@n)-
& ` 9, 1,2,…n(@n) n. _ , & % &'- & ` @n n
' (@n)—1=@n.
>. + P & K(@n) &
& ` Dn+1=K(@n) & A, A1, A2, ..., An , 8 & @n( 1 j, a2 |
||||
j, |
..., |
an |
j) |
' |
D n+1(a, a1 j, a2 j, ..., an j) & % &'- .
C + @n 9 M 4 :
C Dn+1=K(@n) 4, 9 : 9 4
A=(a1i, a2i, …, ani) @n1,…,An 8 + 5 ( , 1 , a2i, …, ani) Dn+1A,A1,…,An,
A 6 9 M.
4 &. 0 A3 9={0,1} P
A39= 1, 0, 0 0, 1, 0
0, 0, 1
' P ( 9) &
A49= 0, 1, 0, 0 0, 0, 1, 0
0, 0, 0, 1 1, 1, 0, 0 1, 0, 1, 0 1, 0, 0, 1
K, , +: C 6.
31
6.2.:F * F, % % . C ,
9 6 C – & A.
-6 @n – C 9 6 M1, M2, … , Mn-1, A, a Cm C
9 6 A, An, An+1, … , An+m-2.
>. + & A & & ` ' @n Cm &
& ` Dn+m-2=@nLCm & 91, 92, …, 9n+m-2, , 8 Dn+m-2(a1 , a2 ,…, ain+m-2j)
' & ' &, "& ' , & ' @n(a1 , a2 , …,
an-1 , a) Cm(a, an , an+1 , …, an+m-2 ). |
|
|
|
|
|
||
4 &. An1,…,An= |
1, |
2, |
2, |
… |
n |
n+1 |
|
|
|
|
|
3, |
… |
||
|
|
|
…............................................................ |
|
|||
|
|
|
k-2n+2k-2n+3… |
k-n+1 |
|
||
:nAn, …, A1= |
n, |
|
n-1, |
… |
1 |
|
|
|
|
n+1, |
|
n, |
… |
2 |
|
|
|
|
…............................................................. |
|
|||
D 2n-2A1,…,An-1,An+1,…A1=1, |
k-n+1, k-n, |
… |
k-2n+2 |
|
|||
n, |
2, |
… n-1, |
n-1 … 2, |
1 |
|||
2, |
3, |
… |
n |
… 3 |
2 |
|
|
…........................................................................ |
|
|
|||||
k-2n+2, |
k-2n+3, … |
k-n, k-n, |
… k-2n+3, k-2n+2 |
|
|||
4 &. d P ALE % ( & ` ' A E ( 9={a, b, c} |
|||||||
B={0, 1, 2}=C P |
|
|
|
|
|
|
|
A9>= , 0 |
|
EBC= |
0, 1 |
|
|
|
|
b, 1 |
|
0, 2 |
|
|
|
|
|
c, 2 |
|
1, 2 |
|
|
|
|
|
2, 2 |
|
|
|
|
|
|
|
& |
|
(ALE)= |
a, 1 |
|
|
|
|
a, 2 |
|
|
|
|
|
|
|
b, 2 |
|
|
|
|
|
|
|
c, 2 |
|
|
|
|
|
|
|
4 , .
1.@nLCm CmL@n
2.(@nLCm)LD k= @nL(CmLD k)
> 5
3. (@nLCm)-1=(Cm)-1L(@n)-1
-6 @ - 8 C 9 6 M, 1, C - 8 C
9 6 1, >. <4 8 6 C 5 @ C : 5 6 5 + $.
8 6 C 5 : C 4 5 n-
.
4 &. E ( " L1, L2, L3 – , M M’ - & ` & & & L1 L2 L2 L3. .& M<=MLM- & ` ' M M’
& ` & L1 L3.
-6 @1m – C 9 6 M1,…,Mm-1, B1; @2m 9 6 M1,…,Mm-1, B2;…;@n-1m – 9 6 M1,…,Mm-1, Bn-1; Cn – 9 6 (1,…,1n-1, Am.
>. N$ & ` ' @1m,@2m,…,@n-1m,Cn ' m-& `
Dm=Cn(@1m,@2m,…,@n-1m) ( 91,A2,…,9m , 8 Dm( 1 , a2 ,…,ami) & ' &,
"& ' b1j B1, b2j B2,…,bn-1j Bn-1, & ( @sm( 1 , a2 ,…,am-1i,bsj % &'-
s=1, 2,…,n-1, , Cn(b1j, b2j, bn-1j, am ).
32
4 &. @13 = 0, 1, 1 |
@23 = 0, 0, 0 |
@33 = 0, 0, 1 |
C 4= 0, 0, 0, 0 |
|
1, 0, 0 |
0, 1, 0 |
0, 1, 1 |
1, 0, 1, 1 |
|
1, 1, 1 |
1, 1, 1 |
|
1, 1, 0 |
1, 1, 0, 0 |
D 3=C4(@13,@23,@33)= 0, 1, 1 |
1, 1, 1 |
|
|
1, 1, 1, 1 |
|
|
|
|
|
1, 1, 0 |
|
|
|
|
1, 1, 1
6 C 5 : 4 -* 4.
+H . % ,
1.Y $ & n-( & ` ' &
$'?
2.S $' % n- & `?
3.S ' & n- & `?
4. |
Y & $ & ` & ( & ` ' & ' ? |
5.S & $ ' & ` (?
6.0 ( & ` ' & A?
7.S & A?
8.Y $ & ` ' $
$ & A?
% +
+
1.E -.9. 0 & . – N4%.: 4, 2001. - N.33-38.
2._ 0., 1 " d. _'$ . – A.: E, 1990. - N.43-46.
3.d ` >.A., U " d.W., a8 W. . 9 %, b, .
–_.:E &, 1989. - N.35-44.
4.N " >.4. A " . – _.: .(, 1975. -
N.97-115.
5._` a.A. A b %. – A.: c-
&, 1987. - N.62, 63.
0 &
6.d % >.9. + b & " . – A.: >b `.`., 1986. - N.13-
20.
7.1 P d., 1 .. N & %. – A.: A, 1976. - N.42-
46.
0 ( '
8.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.14-16.
33
? 7. " " " " J
" %
( " & n-(
& ` '. , 8 & & & & ",
& ` '. ) % &,
" n-( & ` ' – P ', ', ',’', & ( % & `.
3 & & & :
7.1.3 & & ` '
7.2.N ' & ` '
7.1.% * + * K H
-6 @n - C 9 6 M1, M2, ..., Mn 4
@nA1, ..., An= |
a1i1, |
a2i1, |
... |
ani1 |
|
a1i2 |
a2i2, |
... |
ani2 |
|
|
................................. |
|
|
|
||
a1ir |
a2ir, |
... |
anir |
|
|
>. 4$ & ` @n 9j ( % &'- j=1, 2, ..., n),
' rj(@n)={aji1, aji2, ajir} Aj ( j- @n1, An, % & ` @n 9j – ' j-( (
& ` @n.
>. 4 ( ) S(j)a1 …,aj-1i,aj+1i,…,ani & ` @n (
a1 …,aj-1i,aj+1i,…,ani ' ( ajir Aj, & ( '
@n(a1 …,aj-1i,aji,aj+1i,…,ani), % S(j)a1 …,aj-1i,aj+1i,…,ani(@n)={ajir| @n(a1i,…,aj-1i,aj+1i,…,ani)}, & j=1, 2,…,n.
-6 Aj/@n={S(j) 1 …,aj-1i,aj+1i,…,ani(@n)}–9 . C @n 6
6 |
Mj-1× Aj+1× …× An. * 9 Aj/@n : 5 |
( 1 …,aj-1i,aj+1i,…,ani) |
|
M1× M2× …× |
-9 + Aj |
||
C + @n. < 5 : ( 1 …,aj-1i,aj+1i,…,ani) 9 |
4 6 + |
||
5 |
`={( 1ir…,aj-1ir,aj+1ir,…,anir)/r=1,2,…,k}... . |
S(j)X(@n) |
C |
` : 8': C @n 6 6, A 6 5 `:
S(j)X(@n)= r=1k (S(j) 1ir…,aj-1ir,aj+1ir,…,anir(@n)).
4 &. E ( " & ` A3 ( 9={a1, a2}, BB={b1, b2, b3} C={0,1}, 8
A3 9× B× C, &$
A3= a1, b1, 0 a1, b2, 0
a2, b1, 1 a2, b2, 1 a2, b2, 0,
& pr1(A3)=A, pr2(A3)={b1, b2}, pr3(A3)=C,
S(1)b2,0(A3)={a1,a2}, S(2)a1,0(A3)={b1,b2},
C/A3={S(3)a1,b1, S(3)a2,b1, S(3)a1,b2, S(3)a2,b2, S(3)a1,b3, S(3)a2,b3},
& X={(a1, b1),(a2, b1)} S(3)X(A3)=S(3)a1,b1 S(3)a2,b1=C.
>. > & ` Bn ( 91, 92,…,9n ' P '
& % " % & ` B2 ( (91× 92× …× 9n) 9n, 8 &
& ( 1 …,a2i,…,an-1i) 91× 92× …× 9n-1 S(n)a1 , a2i,…,an-1i(Bn)
' % '` & ani) 9n.
34
>. |
S 8 |
& |
% &'- |
& |
( 1 , |
a2i,…,an-1i) |
91× 92× …× An-1 S(n) 1 , a2i,…,an-1i(Bn)-", Bn |
' |
|
||||
& ` & % " % & ` B2 ( (91× |
92× …× An-1) |
|||||
9n. |
|
|
|
|
|
|
>. S 8 S(n)X(Bn) „=91× 92× …× 9n-1 &$
9n, Bn $ ’ & ` & % " % & ` B2
(
(91× 92× …× 9n-1) 9n.
>. S 8 & % &'-( & ( & " ( 1 , a2i,…,an-1i),( 1j,
a2j,…,an-1j) 91× 92× …× 9n-1 S(n) 1 , a2i,…,an-1i(Bn) S(n) 1j, a2j,…,an-1j(Bn)= ,
Bn ’ & ` & % " % & ` B2
( (91× 92× …× 9n-1) 9n.
1 C Bn : % 8 9 4 8 C B2
9 6 (M1× M2× …× Mn-1) Mn, A Bn 5 , 5, ’: +’: 8 9 4 8 C B2 9 6 (M1× M2× …× Mn-1)
Mn.
4 &. E ( " $' 9 = {a, b}, B = {1, 2}, C = {I, II, III}. .
& ` R3A,B,C = {(a, 1, II), (b, 2, I), (a, 2, III), (b, 1, I ))} & % ' % & ` R(A,B),C = {((a, 1), II), ((b, 2), I), ((a, 2), III), ((b, 1), I)}, 8 ' ,
$ ’ , P ', ’ , , , %.
>. E ( " Bn – P ' & ` ( 91,…,9n
& % " % & ` B2 ( (91× 92× …× 9n-1) 9n. -
FBn(x1,…,xn-1) ' ' $ & ` Bn, 8 ( "
9 , & =1, 2,…, n-1, FBn( 1, a2,…, an-1)=S(n) 1, a2,…, an-1(Bn) & % &'- % ( 1, a2,…, an-1) 91× A2× …× 9n-1.
4 &. E ( " & ` B3A,B,C = {(a, 2, II), (b, 1, I), (c, 1, III)} ( A = {a, b, c}, B = {1, 2}, C = {I, II, III} & % ' %
& ` B2(A,B),C = {((a, 2), II), ((b, 1), I), ((c, 1), III)} ( A× B = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)} C = {I, II,
II}. .& & ` B3 ’ P FB3(x1, x2), x1 A, x2 B, x3 C, FB3(a,2)=
S(3)a,2(B3)= II, FB3(b,1)= S(3)b,1(B3)= I, FB3(c,1)= S(3)c,1(B3)= III. 0 ` ( % A× B
P FB3(x1, x2) & .
D A C B1m, B2m,…, Bn-1m, Bn – 5 ' FB1m,
FB2m,…,FBn-1m,FBn |
, |
|
|
Bn(B1m, B2m,…,Bn-1m) 9 |
: 5 |
C. < :+ Bn(B1m, |
|
B2m,…,Bn-1m) |
' |
|
|
FBn(FB1m, FB2m,…,FBn-1m). |
|
|
|
A. E ) . ) / 9 2
. ) / 9.
-6 B - 8 C 9 6 M, 1.
>. > & ` B ' & % 9 >, 8 - P ' " ' , % & % &'- 9 4 Sa(B) – "
' & sa(B)=b B.
T b=(a)B (8 b=B(a)) : 5 % 9 B
8 9 B, – % b.
>. N ' ( 9 (, 8 ( )B=b, ' %
b 9 & % B.
>. > & % B 9 > ' & % 9 >, 8 & $ $ ’ .
35
4 &. E ( " A = {a, b, c}, B = {1, 2}, & ` B & '
P BA,B = {(a, 2), (b, 1), (c, 2)}. .& B & % A B, % b 1, % B(a)=1, % 2 $ {a, c}, % B-1(2)={a, c}.
A. + B – 2
(+ 2), 1 ’2.
<, : 8 9 M M : 4 5 C M,
A + 5 & % 9 %.
. + B 2- ( )
– /) / , / B°B#1= , B -1°B = !,
, ! - + .
; /. : 1 = , 9 B - 2 +
+ / , / B°B#1=B -1°B= .
4 &. > & % B A = {a, b, c}
B = {1, 2, 3} P BA,B ={(a, 3), (b, 1), (c, 2)} &, B°B#1= ={a, b, c}, B -1°B = ! ={1, 2, 3}.
7.2. % C +H + * K H
>. n-& ` @An 9 ':
# P , 8 & % &'- '
@An( , ,…, ), % n @ n;
#P , 8 , & ' @An( , ,…, ), % n @ n= ;
#P (P ), 8 & & (, & (
' @An( , ,…, ), % n @ n n @ n .
4 &. E ( " A = {a, b}. . & ` @1A3 = {(a,a,a), (b,b,b), (a,b,b), (b,a,b)}, @2An = {(a,b,b), (b,b,b), (a,b,a), (b,a,b)}, @3An = {(a,b,a), (b,b,b), (a,b,b), (b,a,b)}
& & P , P , P . |
|
|
||||
>. 1 & ` @A 9 ': |
|
|
||||
# |
P , |
8 |
& |
% &'- |
|
' |
@A( , ), % @ ;
#P , 8 , & ' @A( , ),
% @ = ;
# P (P ), 8 & & (, & (
' @A( , ), % @ @ .
4 &. E ( " A = {a, b}. 1 & ` @1A = {(a,a), (b,b), (a,b)},
@2A = {(a,b), (b,a)}, @3A = {(a,b), (b,b), (b,a)} & & P , P ,
P .
>. n-& ` @An 9 ':
#, 8 & @An( 1 , 2 ,…, n ) P @An
' |
|
% &'- |
|
|
( 1 , 2 ,…, n );
#, 8 & ( 1 , 2 ,…, n ), &
& @An( 1 , 2 ,…, n ), P @An ' ( % & ( 1 ,
2 ,…, n );
# , 8 , , % & & ( ' ' , & & (
– ' .
36
4 &. E ( " A = {a, b}. . & ` @1A3 = ={(a,a,b), (b,b,b), (a,b,a), (b,a,a)}, @2An = {(a,b,b), (b,b,b), (a,b,a)}, @3An = {(a,b,a), (b,b,b), (a,b,b), (b,a,b), (b,b,a)}
& & , , .
>. 1 & ` @A 9 ':
#, 8 & @A( 1, 2) P @A '
( 2, 1);
#, 8 & ( 1, 2), &
& @A( 1, 2), P @A ' ( 2, 1);
#, 8 , , % & & ( ' ' , & & (
–' .
4 &. E ( " A = {a, b, c}. 1 & ` @1A = ={(a,a), (b,a), (a,b)}, @2A = {(a,b), (b,b), (c,c)}, @3A = {(a,b), (b,b), (b,a), (c,a)} & & ,
, .
>. 1 & ` @A 9 ' , 8
& @A(a, b) @A(b, ) & ' @A( , ) & % &'-( a, b, c , ` & ` .
>. 1 & ` @A 9 ' ' , 8 & % &'-( a, b & @A(a, b) @A(b, ), ` & ` ' .
4 &. E ( " A = {a, b, c, d}. 1 & ` @1A = {(a,c), (b,a), (c,d), (b, c), (b, d), (a, d)}, @2A = {(a,b), (b,c), (c,d), (a,c)} & & .
4 &. E ( " A = {a, b, c, d}. . % & ` & '
& @1A = {(a,c), (b,a), (c,d), (b, c), (b, d), (a, d)}, @2A = {(a,b), (b,c), (c,d), (a,c)} & & ’ ' .
D A C @An 5 : 9 6 6 , 8
C (@An)-1 5 : + 9 5.
+H . % ,
1.Y $, , %’& P- $ & n-(
& ` '?
2.S n- & ` P ', ’ ?
3.S n- & ` ' , $ ’ ?
4.S P ' ' $ n- & ` Bn?
5.3 & % 9 > & %
9 >?
6.Y % % & & `, ' %
% n- & `?
7.3 P , P P
% (n- ) & `?
8.Y , % (n- ) & `?
9.Y ' ' & % ( & ` '?
10.S ’ $ "$ & % ( & ` '?
37
% +
+
1.E -.9. 0 & . – N4%.: 4, 2001. - N.35-38.
2._ 0., 1 " d. _'$ . – A.: E, 1990. - .43-46.
3.d ` >.A., U " d.W., a8 W. . 9 %, b, .
–_.:E. &, 1989. - N.35-50.
4.N " >.4. A " . – _.: .(, 1975. -
N.97-115.
5._` a.A. A b %. – A.: c &, 1987. - N.62, 63.
0 &
6.d % >.9. + b & " . – A.: >b `. `., 1986. - N.13-
20.
7.1 P d., 1 .. N & %. – A.: A, 1976. - N.42-
46.
0 ( '
8.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.15-17.
38
? 8. " " J
" %
' ( % ( & ` ', 8
$' ` `. ', " "
&, ', &, " ' ( & ` '. ) & , P &
' ( & ` '.
3 & & :
8.1.W '
8.2.4 &
8.3. . '
8.4._&
8.1. + H
>. 1 & ` @9 9, 8 & '
P , , ' & `
(N).
, A A @M - C 9 M, 8
C @M-1 9 : C 9.
1 C 9 M ' 8 : 9
9, A : 9 5 9 4 9 M
5 8.
-6 @M - C 9 M, A 9. 0 4 -9 M/@M={S (@M)| }.
>. 4 Sa(@A) ' & `$
@9.
A. G- /@ 9 3 / @ 2 + 3
/ Sa(@A)=A.
? A @M – , Sa(@ ) 9 4 4, ASa(@ ) Sb(@ ), : 5 @M b@ c, @ @Mb,
@ b Sa(@A)3Sb(@A), b@Aa Sb(@ )3Sa(@A), 8 Sa(@ )=Sb(@A), 9 + 5.
9 8 R(A)={A1, A2,..., Ak} 9 M : C
C 9 M, 9 4 8 4 + 5 8, 8 C b 5 , ,b , =1, 2,..., k.
. 5 9 3 / 2 2
+ R(A) 0 , , +-* + )
2 9 / .
<' C 5 8 9 9
5 4 , A 9, A 9
5 , 9. ( 5 9
: 9 5 (5 ), 8
6 9 : 5 - 9 6 4
.
-6 @ - C 9 M, A/@={Sa(@)/a } - -
9 9 M C + .
>. > & % 9 P- 9/@, 8
" Sa(@), ' , '
& & % 9 P- 9/@.
39
-6 B - 8 9 9 M 9 1. 1 8 9 + B :
C C 9 M. -6 1, 21C 2 5 , ( 1)B=( 2)B. . 9 b ! 4
4 8 8 9 B 6 5 :
8 9 P 9 1 -9 M/C, B°P 8 4 : 5
8 9 9 M -9 M/C.
1 , A 9 5 M 8 R={A1,..., An} 9 M,' C , A 9 6
: , 8 9 9 4 & ( ).
>. 4 & 9, 8 ' & ' &
9 & % ={A1, A2, ... , Ai,..., An} 9,
' $ & & & & ` .
4 &. ) E ( " 9 = { 1, 2, 3} B = {b1, b2, b3,b4 b5, b6, b7}. 1={ 1,
2, 3}, @9,1={< 1, a1>, <a1, a2>, <a1, a3>, <a2, a1>, <a2, a2>, <a2, a3>,<a3, a1>,<a3, a2>, <a3, a3>}; P2={{a1}, {a2}, {a3}}, @A,2={<a1, a1>, <a2, a2>, <a3, a3>}; PB={{b1, b2, b3}, {b4}, {b5, b6,
b7}}; @B={(b1, b1), (b1, b2), (b2, b1), (b2, b2), (b1, b3), (b3, b1), (b3, b3), (b2, b3), (b3, b2), (b4, b4), (b5, b5), (b5, b6), (b6, b5), (b6, b6), (b5, b7), (b7, b5), (b7, b7),
(b6, b7), (b7, b6)} |
|
|
|
%) |
|
. % 8.1. |
||
|
|
|
|
|
|
|||
@B |
|
b1 |
b2 |
B3 |
b4 |
b5 |
B6 |
b7 |
b1 |
|
1 |
1 |
1 |
|
|
|
|
b2 |
|
1 |
1 |
1 |
|
|
|
|
b3 |
|
1 |
1 |
1 |
1 |
|
|
|
b4 |
|
|
|
|
1 |
1 |
1 |
|
b5 |
|
|
|
|
|
|||
b6 |
|
|
|
|
|
1 |
1 |
1 |
b7 |
|
|
|
|
|
1 |
1 |
1 |
)
0. 8.1. 1 C @B
40