Martynyuk_A_N_Diskretnaya_matematika

% +

+

1.N " >.4. A " . – _.: .(, 1975$ -

N.141-152.

2.d % >.9. + b & " . – A.: >b ` ` , 1986. -

N.6-47.

3.1 9.Œ., . N.1. 0 : 3 %. 0 . – A.: Œ &- Ad.3 . E.c. 1, 2001. - N.112-273.

4.E -.9. 0 & . – N4%.: 4, 2001. - N.51-78.

0 &

5.1 9.Œ., . N.1. 0 : 3 %. 0 . – A.: Œ &- Ad.3 . E.c. 1, 2001. - N.175-275.

6._ 0., 1 " d. _'$ . – A.: E, 1990. - N.134-195.

7.1 P d., 1 .. N & %. – A.: A, 1976. -

N.204-236, 258-346.

8.> 0 > & 1. . 9 % – A.: E, 1979. – N.20-80.

9.A ' 9.Œ. 9 % b – A.: E, 1970 . - N.42-138.

10._` 9.d. %8 " %. – A.: E, 1973. - N.33-107.

0 ( '

11. A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915. / +.A. A$ . – +&: +E43, 2005. – .2. – N.7-11.

61

# : II. B #

? 12. B #. B : "

" %

%.

% , & %. ) & % ( &

, , ( & ` ', % E'$ . 3 ` ' P:

12.1.> %

12.2.4 & %

12.3.4

12.4.N

12.5.& `

12.6.1 E'$

12.1. " G +$

>. > % r ' r- $, 8 ( '

& ( &, r- , 8 % ' & ' %

( &.

4 &. E ( ", &, & M = {a,b,c,d}. > % abc, acb, bac, bca, cab, cba 3- , ( ( . .

% $' %$ " 3- .

1 8 9 5 . . 8 6

+ 5 .

( C 8 : 5, A + 6 8 9

: 5

P$

{ n1 , n2

,......, nk

},

ni - 5 5 i-4 4. < 4 5 6 9

n= n1 + n2 + .... + nk , r-8 r , n. 9 9 4

, 4 9 + 5 + 5

. > 5 5 6 +: ’+

.

4 &. A & ' P$ {2,5,4}, n=2+5+4=11. 4 & a, b, c, '$ & '

{a,b,c}. .& % aabbbc, ababbc, baabbc 8 6- ;

% aabbbbbcccc aabbbccbccb – 11- . > % aabbbc, bbbbbc, abbccc $' & 6- ', 11- &: aabbbbbcccc.

8 9 8 r 9 : 8 5-

5, A A : 4 r. 1 6 9 9 4 , A : 5 6 , 8 4 +: 5

9.

62

12.2. + $ * G

-8 5C + 5 6 8 .

( / . : 1 +'2 a + + * p +, +'2 b - 9 q +, + “+ a, + b” + * * p+q +.

1 8 a b : + + 5 4. -86, A 8 8

8 8': a 8 4 D-8 5 8 8 8': b. . 6

8 4 5 +: p+q-k, k – 8 4.

( / +. : 1 +'2 a + + * p + / ?

+ +'2 b 3 ? + + * q +, + “a b”

* pq +.

. : 5 6, 8 a b 9.

		12.3.
1 r- n 6 8 5.
(.	( 9 *	/			+

n / n + – / 3, + ? ? /

* n-1 + / r-? /, : * + n-r+1

+.

< + 8, 9 :

p(n,r) = n (n-1)......(n – r + 1), n 4 r.

4 &. ) %’ 1, 2, 3, 4 12 ( 2- : 12, 13, 14, 23, 24, 34, 21, 31, 41, 32, 42, 43.

n- n 6 + 5 . .C r = n,

: p(n, n					) = pn = n(n-1)...2		*1 =	n!	1 +
C, 9 :
	n!		p(n, n)
p(n, r) =		=		.
	(n # r)!		p(n # r, n # r)
0 4						n	,			6
{ n1 , n2 ...nk },			n = n1 + n2		+ ... + nk .v	8 4	6			6

: 5 C 9 n! , A 6 4

+:.

( n /: Z/ j-? / 3

n j ! +, / ) 0 * 33 /,

/ + + n1!n2!...nk ! , 1 33

.

v 6 , A 6 5 n , 9 : 5

+

pn (n1 , n2 ,...nk ) = n1!n2n!!...nk !

4 &. 4 % & 10 % &, & ( 3 % & & , 5 - & 2 - ', & p10 (3,5,2) = 10! 3! 5! 2!= 2520 %.

D A 8': n 6 8 9, 9

r- 9 n 8. ? 8

r- % +: U(n, r) = nr . B

C, , : 5 5 6 r-6 , 6

+ n.

63

12.4. % +-,

1 r-5 n 6 .

r-/ n /: \ ? ? /

r!

,

/

r-/

n /

+

r!

9

/

r-

n /:

p(n, r)

n(n #1)...(n # r +1)

n!

C(n, r) =

=

=

!

!

r!(n # r)!

4 &. ) ' ( ( %' , 8 $' 1, 2, 3, 4,

` ' ' & (n=4, r=2): 12, 13, 14, 23, 24, 34.

j n g

r

v r-5 n 6 : 5 h

e

Cn . < r n-r

i r f

j n g

j n

g

: 9 C(n,r) = C(n, n-r) h

e

= h

e .

i r f

i n # r f

z

r-5

%

n 9 9 8.

r-/ + n /. 5 / 3

, * / ? /

), / / / 3 /

, 1 / -+ / *9/ /.

4 &. 0 abbce {a,b,c,d,e} % &

101101001, & bbbee – 011100011 .&.

, r- n 5 r

5 n-1 . ‹ r-5 8 4 : 5

8 9 r+n-1 :+ {r,n-1}

r- n 6 , A A. 9

		(r + n #1)!		j r + n #1g
	F(n, r) =			= h		e = C(r+n-1, r).
		r!(n #1)!			r
				i		f

4 &. o ' 2 4 , 8 $' 1, 2, 3, 4, &$ C(5,2)=10, 8 $$' %: 11, 12, 13, 14, 22, 23, 24, 33, 34, 44.

0 4 8 : 9 C + 9 +,

6 6 5 : , , 9, 6 : 6 9 6

.

12.5. # % * K ,

. 6 C 5 9 4 +

( & ` ', A 9 8.

^ 9. 6 r- n /

+ / , 1 ? ?

. ? / 0 , 9 ? / +'

) * /. 4, 9 * / / 2

P(n-1, r)- , ? * – r(n-1, r-1), 1 . * /

* r / * P(n-1, r-1) . \ / 2

. /

P(n, r) = P(n-1, r) + r(n-1, r-1)

> P(k, 0), A : 8 4 , 9 ++

. P(k, 1) = k 8 5-4 4 5 4 k P(k, s) = 0 k < s. B

C 9 5 9 4 C.

64

D A r = n, :: P(n, n) = P(n-1, n) + n(n-1, n-1) = n(n-1, n-1) = n(n-1) P(n-2, n-2) =

...	=
= n(n-1) ... 2× 1 = n!
4 &. & ` & r- ' n (
&
N(n, r) = C(n-1, r-1) + C(n-1, r), n 4 r,
& & " & & ( ,	8 ' P ,

` " – . d & ' & ` C(n, 0) = C(1, 1) = 1 C(k, s) = 0 k < s.

4 &. S 8 % r- '

n & ( &, & ( ' , 8

' P , ` – , 8 ' " , & & `

F(n, r) = f(n-1, r) + f(n, r-1)

4 ' n r % & ' ' %$ &$' n 4 r, n , r. d ' &

f(n, 1) = n; f(n, o) = f(1, r) = 1.

< 6 C 5 4 :

8 6 8 9. < 4 + 6

C 5 9 , C 5.

12.6. B$ H'

.

5

9 8': 9

{A1,A2 ,...,An } &

4 1+Ai x(i = 1,2,..., n) 9 6:

(1+A

x)(1+ A

2

x)

... (1+ A

n

x)

= 1+ a x + a

2

x2

+ ... + a

n

xn

1

1

: ar 8 4 : 8 + 8,

9 6 : r

n (r-c o5), 5 4 ar

: C(n, r) 6 8.

= A2 = ... = An

= 1,

; 3 + / . ) 2. : 1 / A1

j n g

+-: * + r-/ / 32 ) , ,

ar = C(n, r) = h

e ,

i r f

n

j n g j n g

j n g

2

j

n g

n#1

j n g

n

(1+x)

= h

e

+ h

ex + h

ex

+ ... + h

ex

+ h

ex

i 0 f i

1 f

i

2 f

i n

#1f

i n f

`

3

+

; 3,

r-/

n / C(n, r) 2 + / . ) 2.

A

D A -8 5 8 ar, 9 C(n, r). - ,

8

5

n

r = 0, 1, ... , n, 9 9 : (1+x) n .

< 4 + 8 -5+ 9 5.

4 &. 4 ` x = 1 x = -1,

n j n g

r

n

r j n g

kh

e = 2

; k(#1)

h

e = 0

r=0 i r f

r=0

i r f

4 ` ( P , , ' ' ( & & . S 8 & P$ % E'$ x x = -1, &

n

k

r=1

r(#1)	r j n g			= 0, n 4 1	,
	h		e
	i r f

65

8 & P$ k x, & k! x = 1,

" & & `
n	r jr gjng
k(#1)	h		eh		e	=0
r=k	ikfir f

+H .% ,

1.Y r- $?

2.Y r- ?

3.Y P " & ?

4.	3		& %?
%5.	Y		$' ?
6.	S	% $' $

?

7.Y % $' ?

8.S % $' $

?

9.S &$ (

& ` '?

10.Y % E'$ % ' P?

% +

+

1.	E -9. . 0 & ..: – N4% 4,

N2001. - .135-156.

2.N " >4. . A " . – _.: .(, 1975. -

N.169-174.

3.Π1E. . 0 . 9 b b: 3 %

%. – A.: % 1 b( ) " , 2001. - N.8-24, 49-53. 0 &

4.E >d. ., N 9>. . 4 & & -

(. 0 & ( (. – _.: 3 %-

& " % b ` % , 1992. - N.47-55.

5.d % >9. . + b & " . – A.: >b ``. ., 1986. - N.13-

20.

6.1 P d., 1 .. N & %. – A.: A, 1976. - N.25-

29.

0 ( '

7.A & & & ' ( %« & + & » & & P P ( 6.0804,

+	6.0915 / A.	. A$ . – +&: +E43N, 2001. – .21-23.
	8.	d d4. ., N 99. . N% & & " . –
	A.: E, 1973. - N.249-281.

66

? 13. B #. "

" %

& & % &. 4 &

' ( ( ( P ", 8 '$$' % E'$ ,

$ $ %. 3 & & :

13.1.4 ' P, 8 % $'

13.2.W P, 8 % $'

13.3.4 $ $

13.4.%

13.1.+$+H / C

2 8 (1+A1 x)(1+ A2 x)...(1+ An x) 9 : r- , 6 9

9 8': {A1 ,A2 ,...,An } 9 ' 8 5C 4 . , C 6

5 8 C 9.

D A 8': Ai 9 6 0, 1,...,k , 5 1+Ai x 8

9 1+Ai x + Ai

2 x2 + ... + Aik xk

( k=0 9 +: ). ?

A

1

= A

2

= ... = A

n

= 1 : a

r

8 4 A(x)=1+ a x + a

2

x2 + ... + a

n

xn + 5 8 +

1

r- n 6 .

4 &. 0 r- ' ( a, b, c P$ {3, 1, 2}

(1+x+x 2 +x 3 )(1+x)(1+x+x 2 )=1+3x+5x 2 + +6 x3 + 5x4 + 3x5 + x6 . . P xr

& ` r- '. . , 1- (aaa, aab, aac, abc, acc, bcc), '' 4-

' (aaab, aaac, aabc, aacc, abcc) .&.

( / /						. )	(b).	? /	?/
A(x) = a	0	+ a x + a	2	x2 + ... + a	n	xn + ... 3 / / 3 . ) 23, +
		1

3 ( ) / / a0 ,a1 ,..., an ,...

B 5 : r- n . 3 -5+ :

:+, A 8 : 8 . ? 8 , A x

9 : 5 8 . Π4 5

5 4, A 8 a0 ,a1 ,..., an ,... . 5

6 + 5

.

2 8 9 n 8 (1+6+A2 +... )n . 1 9 9 6 9 4

		1	= 1+ x + x2	+ ... = (1# x)#1
	1# x
	. 4 (1-6 )# n		8	-5+ ’: –n,
	5 9

(1# x)

2

= k

r=0

#n	2 j	# n g		r	2	# n(#n #1)...(#n # r +1)	(#x)	r	=
	= kh	r	e(# x)		= k	r!
	r=0 i		f		r=0

(n + r #1)..(n +1)n		r	2 j n + r #1g			r	2	r
	x		= kh		ex		= k f (n, r)x		,
r!				r
			r=0 i		f		r=0

A 8 4 : 5 5, 5. < 9 :

5 C

67

	j	# n g		j n + r #1g
	h		e	= h		e
		r			r
	i		f	i		f

D A 9, A 8 9 8': 6 8 9

, • (1 + x2 + x4 + ...)n

(1# x2)#n =	2 jn + r		#1g	,
	h		ex2r
	kh	r	e
	r=0i		f
8 r-5			r +: +,

2r-5 : 5 r-5 8 4 C 8 9. M 4 : 5 C 6 6 6. -6,

, 86 6 r-5

8 9 , A 8' 5 6 8 9 4 4. ?

(x + x2 + x3 + L)n = xn (1+ x + x2 + L)n = xn (1# x)#n =

= xn

2 jn + r #1g

=

2 jn

+ r #1g

=

.

h

exr

h

exn+r

kh

r

e

kh

r

e

r=0i

f

r=0i

f

2 j r #1g

2 j r #1g

=

kh

e

=

kh

e

h

exr

h

exr

ir # nf

in #1f

=n

=n

?

8

n

+ r

r

jng

j

n g

C h

e

= h

e 5. v C 6 5 +: + r < n.

h

e

h

e

i r f

in # r f

4 n .

+: C(r — 1, n — 1)

4 &. 0 ' ( , b, & 3- (abc), 4 c"

&$ N(3, 2) = 3 (aabc, abbc, abcc), 5- ' &$ N(4, 2) = 6 (aaabc, aabbc,

aabcc, abbbc, abbcc, abccc) .&.
	13.2. % / C
> C 5	9 +	9		r-5
r- 6 5, 9

(1	n jng
	+ x)n = khh eexr
	i r f
	r=0

	n		x	r
	= k p(n,	r)			,
			r!
	r=0

8 r- 6 : : xr r!

(1 + x) n . 2 5 4 5 C .

Z . ) 0. . ) 3 / r-

+ , 1 + U(n, r) = nr + / . ) 2 xr r!

1

2

x

r

2

x

r

2

(nx)

r

x

2

kU (n, r)

= knr

= k

= (1+ x +

+ L)n = enx ,

r!

r!

r!

r=0

r=0

r=0

2!

1+ x + x2 2!+ K,

1 2

/ 0 . ) 0,

* / U(n, r). ( + 3

. ). \ 0 3 ? 3 + /3 /

.
4 &.	S 8 r-	$$'
P$	{n1, n2 , K, nk },	n = n1 + n2 + L+ nk , &

68

&

1+ x + x2

2!+ K % '

xni n !,

,

,

&:

i

xn1

xn2

(1+ x +

x

2

+ L+

)(1

+ x +

x2

+ L+

)L

2!

n

!

2!

n

2

!

1

x2

xnk

n

xr

L(1+ x +

+ L+

) = kbr

.

2!

nk !

r!

r =0

4 &.

•

r-

% $'

' P b

(r = 0, 1, 2,K, n) . + "

xn1 xn2 Kxnk

=

n!

5

xn

= b

xn

n ! n

!Kn

!

n ! n

!Kn

!

n!

2

k

2

k

n n!

1

1

n

n

, %

bn = pn (n1 , n2 K, nk ) , 8

% '

',

` % &

.

13.3. C % +'-, +'-,

2 C 6 9, A 5 C 6 8 8': 9 , A + 5 6 + 5 5,

5 + 5. - C + 5 6, '

8':.

	-6 : N 8': 5 E = {A1A2A3 }. .
N (Ai )	, N (AiA j ) , N (AiA jAk ) . . 5 5 8':, A + 5
Ai ;Ai	A j ;Ai ,A j Ak . . , 6 8 5, 5 9 9

9 E, 8 2n ( 9 5 + +). D A 8 9 + 5 , A 6 + 5 8':, A + 5 + Ai , C 5 Ai . - , N (A2A3A2 ) : 8':, A + 5 A2 A2 + 5

5 A3 .

G / /3 /3. d / +'2, 1 3

/ * , 2 . / 3 /3 /3:

N (A1A2 KAn ) = N # kN (Ai ) + kN (AiA j ) #

i

i< j

#k(AiA jAk ) + L+ (#1)n N (A1A2 ,K,An ) .

i< j<k

2, N 8': Ai ( =1,2,..., ) 8':, A + 5

Ai Ai ( j), + 5 , 8 N (AiA j ) , AiA j

— E. M 5 6 + 5 8':, A + 5 , 9, 6 86 +, 8 6 N (AiA jAk ) ,

AiA jAk — n 5 6. B + +

9 : 5 5 4 N (A1A2 ,K,An ) , A : 8':

, 4 9 5 . - 9

: " &, ( P, & `, P %.

69

D A Ai =1#Ai 4 5 A1A2 KAn

4 8 8, + + 9

4.

4 &. 0 n = 3 '

N[(1#A1 )(1#A2 )(1#A3 )] = N [1#A1 #A2 #A3 +

+A1A2 + A1A3 + A2A3 #A1A2A3 ] = N (1) # N (A1 ) #

# N (A2 ) # N (A3 ) + N (A1A2 ) + N (A1A3 ) + N (A2A3 ) # N (A1A2A3 ) ,

" ', 8 N(1) = N.

< D 9 8':, A + 5

+ 5 :

N (A1A2 A3A4 ) = N[A1 (1#A2 )(1#A3 )A4 ] = N[A1A4 #A1A2A4 #

#A1A3A4 + A1A2A3A4 ] = N (A1A4 ) # N (A1A2A4 ) # N (A1A3A4 ) + .

+ N (A1A2A3A4 )

4 &. E ( " & `: A1 - , A2 - , A3 — P,

N (A1 ) = 13; N(A2 ) = 10; N(A3 ) =14; N (A1A2 ) == 4; N (A1A3 ) = 5; N (A2A3 ) = 3 N (A1A2A3 ) = 1. S 8 ' N = 38 `, ( (, 8 $' &

( ", % & N (A1A2 A3 ) =38 — (13 + 10 + + 14) + (4 + 5 + 3) — 1 = 12. o (, ( P ( ` &$ :

N(A1A2 A3 ) = N [A1 (1#A2 )(1#A3 )] = N (A1 ) # N (A1A2 ) # N (A1A3 ) +

+ N(A1A2A3 ) = 13 # 4 # 5 +1 = 5

. + + + : 5 4 + 1, A

4 4 . 13.1.

. 13.1. 0 > & , 8 ($' '

70