Лупаренко_ Комбинаторика

10!

10!

3 >

5

k !(10 −k )!

(k −1)!(10 −k +1)!

10!

10!

5 >

3

k !(10 −k )!

(k +1)!(10 −k −1)!

+3)<33

k ( 5

+3)>30 − 5

k ( 5

5,302 <k <6, 302 k = 6;

5.Из данной пропорции найти x и Cxy+1 : Cxy : Cxy−1 = 2 : 2 :1.

3

5

>

30 −3k +3

>k 5

k 10 −k +1

5

3

5k + 5

>30 −3k

>

k +1

10 −k

30

− 5

<k <

33

5 +3

5 +3

4 =3827250 .

t

6

=C6 36

5

10

y .

Решение. Запишем отдельно отношение первого члена пропорции ко второму и второго к третьему, получим после сокращения.

	y+1		: C	y	= 2 : 2
C	x			x
	y		y−1
					= 2 :1
Cx		: Cx

	x!					x!
			:					=1
(y +1)!(x −y −1)! y!(x − y)!
				(y −1)!(x −y +1)!
	x!
			:					= 2.
						x!
y!(x −y)!
Получим:
						= y +1
				x −y				x −2 y
						+1 = 2 y
				x −y				x −3y
						y = 2;		x =5 .

x − y

=1

y +1

x − y +1 = 2

y

−1 =0

.

+1 =0

21

ЛЕКЦИЯ 4.

СВОЙСТВА БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ. СВОЙСТВА СОЧЕТАНИЙ.

1. Свойство симметрии.
Теорема 4.1. Cnk =Cnn−k .
	Доказательство.
C k =	n!	=			n!					=C n−k	,
					n −k ! n −		n −k
n	k !(n −k )!		(					))	! n
					) (	(

что и требовалось доказать.

Это свойство известно как свойство симметрии биномиальных коэффициентов. Его особенность заключается в том, что не имеет значения, как выбирать элементы: из n по k , или из n по n −k . В обоих случаях число подмножеств – одинаково.

Геометрическая интерпретация свойства симметрии.

Рассмотрим прямоугольную сетку квадратов размерами m×n («шахматный город», состоящий из m×n прямоугольных кварталов, разделенных n −1 «горизонтальными» и m −1 «вертикальными» улицами). Каково число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла (точки (0;0)) в правый верхний угол (точку ( m; n ))?

Решение.

Каждый кратчайший путь из точки (0; 0) в точку (m; n) состоит из

m +n отрезков: m -горизонтальных и n -вертикальных. Разные пути отличаются лишь порядком чередования горизонтальных и вертикальных отрезков.

Поэтому общее число путей равно числу способов, которыми из m +n отрезков можно выбрать n вертикальных отрезков равно Cmn +n (или m -

горизонтальных: Cmm+n ). Значит Cmn +n =Cmm+n .

22

2. Свойство сложения.

Теорема 4.2. C k

=C k−1

+C k

.

n

n−1 n−1

Доказательство.

(

n −1 !

(

n −1 !

C k −1

+C k

=

)

+

)

=

n−1

n−1

(k −1)!(n −k )! k !(n −k −1)!

(n −1)! k

n!(n −k )

=

+

=

(k −1)!(n −k )!

(k −1)!(n −k )!

(

n −1 !

n

n −1 !

n!

=

)

(k +n −k )=

(

)

=

=Cnk ,

k !(n −k )!

k !(n −k )!

(n −k )! k !

что и требовалось доказать.

Доказательство данной теоремы можно также получить, если исходить из следующих соображений.

Число Cnk определяет число тех подмножеств из k элементов, которые могут быть выбраны из множества, содержащего n элементов. Выбираем один из этих элементов, например, x и разложим исходное множество с Cnk

множествами на 2 класса, один из которых содержит в своем составе x , а другой – нет.

В первом классе элемент x присутствует во всех без исключения подмножествах. Это значит, что он просто присоединяется к k −1 элементам, которые выбираются не из n элементов, как это было до разложения на 2 класса, а из n −1 (элемент x во время их выбора - отсутствует). Поэтому количество подмножеств в первом классе равна Cnk−−11 .

Так как элемент x во втором классе отсутствует, то подмножества к нему принадлежащие, не содержат ни одного элемента x , хотя и без него им принадлежат k элементов, но выбираются они не из n элементов, а из n −1 .

Поэтому количество подмножеств во втором классе равно Cnk−1 . Соответственно сумма подмножеств первого и второго класса равна

Cnk−1 +Cnk−−11 =Cnk .

Геометрическая интерпретация свойства симметрии.

Рассмотрим число кратчайших путей из точки O(0; 0) в точку

A(k, n −k ): Ckk+n−k =Cnk .

23

Все такие пути можно разделить на 2 группы: пути, проходящие через точку

1 (	)	и
A	k; n −k −1

A2 (k −1; n −k ) .

Путей первой группы

Cnk−k−1+k	=Cnk−1 .
Путей второй группы
Ckk−−11+n−k	=Cnk−1 .

Следовательно, Cnk =Cnk−−11 +Cnk−1 .

Свойство сложения (теорема 4.2) известно в математике как правило Паскаля: оно выражает, согласно правилам рекурсии один биномиальный коэффициент не равный единице, через два других. При помощи этого правила можно построить треугольник Паскаля, как числовой, так и символический.

Числовой треугольник Паскаля

					1						n = 0
				1		1					n = 1
			1		2		1				n = 2
		1		3		3		1			n = 3
	1		4		6		4		1		n = 4
1		5		10		10		5		1	n = 5

Символический треугольник Паскаля

					0						n = 0
					C0
				0		1					n = 1
				C1		C1
			0		1		2				n = 2
			C2		C2		C2
		0		1		2		3			n = 3
		C3		C3		C3		C3
	0		1		2		3		4		n = 4
	C4		C4		C4		C4		C4
0		1		2		3		4		5	n = 5
C5		C5		C5		C5		C5		C5

24

Свойства треугольника Паскаля.

В строке n, n = 0,1, 2,... треугольника Паскаля стоят коэффициенты

Cnk , k =0, n кроме того, каждый коэффициент, кроме двух крайних, которые

равны 1, равны сумме двух коэффициентов предыдущей строки, которые стоят над ними.

Сумма биномиальных коэффициентов одной строки равна 2n . Сумма биномиальных коэффициентов, которые стоят на нечетных местах равна

сумме коэффициентов на четных и равна 2n−1 .

Например.
(a +b)7 : n =6 :	1 6 15	20 15	6 1
n =7 :	1 7 21 35	35 21	7	1

(a +b)7 = a7 +7a6b +21a5b2 +35a4b3 +35a3b4 +21a2b5 +7ab6 +b7 .

Рассмотрим еще несколько основных свойств биномиальных коэффициентов.

Теорема 4.3.

Cn0 +Cn1 +Cn2 +...+Cnn = 2n

				Доказательство.
	n
(a +b)n = ∑Cnk an−k bk , a =b =1.
	k =0
Теорема 4.4.
C0	−C1	+C 2	−...+ −1	n C n =0
n	n	n	( )	n
				Доказательство.
	n
(a −b)n = ∑(−1)k Cnk an−k bk , a =1, b =−1.
	k =0
Теорема 4.5.
				n−k
Cnk	=Cnk−−11 +Cnk−−21 +...+Ckk−−11 = ∑Ckk+−i1−1.
				i=0
				Доказательство.

На основании теоремы 4.2 запишем равенства:

Cnk =Cnk−−11 +Cnk−1 ;

Cnk−1 =Cnk−−21 +Cnk−2 ;

Ckk+2 =Ckk+1 +Ckk+−11;

Ckk+1 =Ckk +Ckk −1 .

25

Поскольку Ckk =1, Ckk−−11 =1 , то после подстановки выражения для

Ck	в выражение для Ck	имеем
k +1	k +2

Ckk+2 =Ckk +Ckk−1 +Ckk+−11 =Ckk+−11 +Ckk−1 +Ckk−−11 .

Подставляя Ckk+2 в предыдущее равенство получим:

Ckk+3 =Ckk+2 +Ckk+−12 =Ckk+−11 +Ckk −1 +Ckk−−11 +Ckk+−12 .

Выполняя такую же операцию для остальных коэффициентов

непосредственно до Ck− получим в результате необходимое равенство.

n 1

Теорема доказана.

Теорема 4.6.

k

Cnk =Cnk−1 +Cnk−−21 +...+Cn2−k +1 +Cn1−k +Cn0−k −1 = ∑Cni −k +i−1. i=0

Доказательство.

На основании равенства

Cnk =Cnk−1 +Cnk−−11 и Cn0−k−1 =Cn0−k =1 .

Имеем

C1− +C0− =C1− + . n k n k n k 1

Далее

C 2− + +C1− + =C 2− + . n k 1 n k 1 n k 2

И т.д. до получения в итоге в сумме необходимый результат.

Свойства вынесения за скобки.

Теорема 4.7. При k ≠0,

n ≠0

C k =

n

C k−1 .

n

k

n−1

Доказательство.

n!

n

n −1 !

n

Cnk =

=

(

)

=

Cnk−−11

k (k −1)!(n −k )

k !(n −k )!

k

Следствие 1.

k C k

= n C k −1 .

n

n−1

Следствие 2.

1

C k =

1

C k −1 .

n

n

k

n−1

Теорема 4.8. При k ≠0,

n ≠0

C k =

n

C k

.

n

n −k

n−1

Доказательство.

Из теоремы 4.7 следует

26

C n−k

=

n

C n−k −1 .

n

n −k

n−1

Из теоремы 4.1 следует: C n−k −1

=C k

.

n−1

n−1

Таким образом C n−k =

n

C k

или

n

n −k

n−1

C k

=

n

C k

ч.т.д.

n

n −k

n−1

Например. Вычислить сумму:

а). C1

+3C2

+5C3

+...+

(

2n +3 Cn+2

(

n ≥−1 .

n+2

n+2

n+2

)

n+2

)

Обозначим искомую сумму через S . Тогда

S −1 =−1 C 0

+C1

+3C

2

+5C3

+...+

2n +3 C n+2 .

n+2

n+2

n+2

n+2

(

) n+2

Учитывая свойство: Cnk

=Cnn−k

, последнее равенство запишем в виде:

S −1 =−C n+2

+C n+1

+3C n

+5C n−1

+...+

2n +1 C1

+

2n +3 C 0

.

(*)

n+2

n+2

n+2

n+2

(

)

n+2

(

) n+2

S −1 =

(

2n +3 C 0

+

2n +1 C1

+...+5C n−1

+3C n

+C n+1

−C n+2 .

(**)

)

n+2

(

)

n+2

n+2

n+2

n+2

n+2

Складываем равенства (*) и (**) почленно, получим:

2S −2 =(2n +2)Cn0+2 +(2n +2)Cn1+2 +...+(2n +2)Cnn++21 +(2n +2)Cnn++22 .

Откуда:

2(S −1)=(2n +2)(Cn0+2 +Cn1+2 +...+Cnn++21 +Cnn++22 )=(2n +2) 2n+2 .

Получим: S −1 =(n +1) 2n+2 .

S =(n +1) 22n+2 +1 .

б). Доказать тождества:

0

1

1

+...+

1

n

2n+1 −1

Cn

+

Cn

Cn =

.

2

n +1

n +1

Так как C k +1

=

n +1

C k , то C k

=

k +1

C k +1 .

n+1

k +1

n

n

n +1 n+1

C0

+

1

C1

+...+

1

C n =

1

C1

+

1

2

C 2

+...+

1

C n+1

n +1

=

n +1

n +1

n

2

n

n +1 n

n +1 n+1

2 n +1 n+1

n+1

1

1

2

n+1

1

n+1

0

2n+1 −1

=

(Cn+1

+Cn+1 +...+Cn+1 )=

(2

−Cn+1 )=

.

n +1

n +1

n +1

в). Доказать тождество:

Cn1 +2Cn2 +3Cn3 +...+nCnn = n 2n−1 .

Используем равенство: k Ckk = n Cnk−−11 .

Cn1 +2Cn2 +3Cn3 +...+nCnn = n Cn0−1 +n Cn1−1 +n Cn2−1 +...+nCnn−−11 = n(2n−1 ).

27

г) Доказать тождество:

Cn1 −2Cn2 +...+(−1)n−1 nCnn = 0 .

Используем равенство: k Cnk = n Cnk−−11 , получим:

n Cn0−1 −n Cn1−1 +...+(−1)n−1 nCnn−−11 = n 0 =0 .

Полиномиальная теорема.

Полиномиальная

теорема

–

это

обобщение

формулы

бинома

Ньютона на случай k слагаемых, т.е. вычисление выражения вида:

(a1 +a2 +...+ak )n .

Полиномиальная теорема.

Выражение (a1 +a2 +...+ak )n равно

сумме возможных слагаемых вида

n!

ar1 ar2 ... ark

, где r +r +...+r = n , т.е.

r !r ! ... r !

1

2

k

1

2

k

1

2

k

n

∑

n!

a1r1 a2r2

... akrk .

(a1 +a2 +

...+ak )

=

r !r ! ... r !

r1 +r2 +...+rk =n

1

2

k

r1 >0,r2 >0,...,rk >0

Доказательство.

Перемножим последовательно

a1 +a2 +...+ak

n

раз.

Тогда получим

k n слагаемых вида d d

...d

i =

равен или a ,

2

k

, где каждый множитель d

i

,

1, k

1

1

или a2 ,…,

или ak . Обозначим

B(r1 , r2 ,..., rk )

- совокупность тех слагаемых,

где a1

встречается r1 раз,

a2 −r2 раз,…,

ak −rk

раз. Число таких слагаемых

равно

числу

перестановок с

повторением

из

n элементов

с

составом

(r1 , r2 ,..., rk ),

т.е. Pn (r1 , r2 ,..., rk ),

причем

r1 +r2 +...+rk

= n . Во 2-ой лекции

было показано, что

Pn (r1 , r2 ,..., rk )=

n!

.

r1 !r2 ! ... rk !

Следовательно,

n

∑

n!

a1r1 a2r2

... akrk

(a1 +a2 +...+ak ) =

r !r ! ... r !

r1 ≥0,r2 ≥0

1 2

k

r1 +r2 +...+rk =n

n

n!

При

k = 2

получим:

(a1 +a2 )n = ∑

a1n−k a2k

-

формула

!(n −k)!

n=0 k

бинома Ньютона.

28

Например.

1. Вычислить (x + y +z)3 .

Можно последовательно раскрывать скобки, производя умножение многочлена и приводя подобные слагаемые. Получим:

(x + y +z)(x + y +z)(x + y +z)=(x2 +xy +xz + yx + y2 + yz +zx +zy +z2 )(x + y +z)=

= x3 + y3 +z3 +3x2 y +3x2 z +3 y2 x +3 y2 z +3z2 x +3z2 y +6xyz .

Всего в выражении 27 членов.

Этот результат легко найти по полиномиальной теореме при n =3 и k =3 . Система условий суммирования здесь имеет вид:

r1 ≥0, r2 ≥0, r3 ≥0
	+r2	+r3	=3
r1

Различных числовых коэффициентов здесь тоже 3:

3!	=3;	3!	=1;		3!	=6 .
0!1!2!		3!0!0!		1!1!1!

(x + y +z)3 =1 (x3 + y3 +z3 )+3(x2 y +x2 z + y2 x + y2 z +z2 x +z2 y)+6xyz

2. Найти коэффициент при tk в разложении:

(2 +t4 +t7 )15 , k =17 .

Решение. Представим искомое выражение в виде:

(2 +t4 +t7 )15 = (t4		+t7 )+2		15	=(A +2)15	=	15	C15k	215−k Ak ,
							∑
	(		)
							k =0
где A =t 4 +t7	= t4 (1+t3 ).
k -ый член Ak	равен Ak : C k			Ak 215−k , причем в A входят от t4k до t7 k .
		15

Значит, степень 17 может входить в A3 и в A4 степени. Значит, проверяем только эти члены:

A3 = t 4 (1+t3 )3		=t12 (1+t3 )3	3	3
			=t12 ∑C3k (t3 )1 =t12	∑C3k t3k .
			k =0	k =0
17 не делится на 3, значит здесь члена t17 нет. Аналогично,
4
A4 =t16 ∑C4k t3k ,	3k ≠1 t17 нет.
k =0
Коэффициент при t17		= 0 .

29

ЛЕКЦИЯ 5.

МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ

Содержание комбинаторного анализа не исчерпывается подсчетом числа решений соответствующих задач. Не менее важное место в нём занимают проблемы возможности или невозможности осуществления некоторых выборок или расположений элементов. Логическая сущность метода включений и исключений определяется тем, что он применяется к важной задаче разделения множеств на подмножества в зависимости от того, обладают ли их элементы определённой совокупностью свойств или нет.

Рассмотрим сначала простую задачу о нахождении числа элементов объединения множеств. Напомним, что объединением (или суммой) множеств A и B называют множество C , определяемое следующим образом:

C = A È B = { x Î C / ( x Î A) Ú ( x Î B)} .

Обозначим через n( A) количество элементов множества A , через n(B) - количество элементов множества B . Тогда основная формула,

которой пользуются при нахождении числа элементов объединения двух множеств, такова:

n( A È B) = n( A) + n(B) - n( A Ç B) .

(5.1)

Эта формула совершенно очевидна из диаграммы Эйлера-Венна.

				Значение n( A) + n(B)		является		числом,
				которое получается при подсчете сначала
	A	A Ç B	B	всех элементов множества A ,			а потом всех
				элементов множества B . Однако, при этом
				общие элементы множеств A			и	B , а их
				будет	n( A Ç B) , считаются		дважды, т.е.
	следует равенство (5.1).			n( A) + n(B) = n( A È B) + n( A Ç B) , откуда и
		Например.
		1. Среди сотрудников научно-исследовательского института 47
	владеют английским		языком, 35 –		немецким, а 23	сотрудника знают

английский и немецкий языки. Сколько сотрудников научноисследовательского института владеют хотя бы одним иностранным

языком?
	Решение.
	Пусть A - множество сотрудников, владеющих английским языком;
B	- множество сотрудников, владеющих немецким языком. Тогда	A Ç B -
это	множество сотрудников, знающих оба этих языка, а A È B	- это

множество сотрудников, которые владеют хотя бы одним из этих языков.

30