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

Например: Выпишем все сочетания множества A ={1; 2;3; 4} по 2 элемента:

{1; 2}, {1;3}, {1; 4}, {2;3}, {2; 4}, {3; 4}. Имеем: C42 =6 .

Теорема 1.3. Число неупорядоченных выборок из n элементов по k без повторения вычисляется по формуле:

	n	n −1 ...	n −k +1		n!
Cnk =	(	) (	)	=			(1.3)
					k !(n −k )!
		1 2 3 ... k

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

Формула (1.3) легко получается из выведенных ранее формул для размещений и перестановок.

Составим вначале все сочетания из n элементов по k , а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается все размещения из n элементов по k , причем каждое только по одному разу. Но из каждого k - сочетания можно сделать Pk перестановок, а число этих сочетаний Cnk . Значит, справедлива формула

				Ak	= P C k .
				n	k n
	Отсюда находим, что
	C k =	Ak		n (n −1) ... (n −k +1)			n!
		n	=			=
		P		1 2 3 ... k			k ! n −k	!
	n
		k					( )

Например.

∙ Сколькими способами читатель может выбрать 3 книжки из 5?

Решение: C3	=	5!		=	4 5	=10 .
5		3! 2!		2

∙ Сколькими способами из 7 человек можно выбрать комиссию, состоящую из 3 человек?

Решение: C3	=	7!		=	5 6 7	=35 .
7		3! 4!			1 2 3

∙ В турнире принимали участие n шахматистов, и каждые 2 шахматиста встретились 1 раз. Сколько партий было в турнире?

	n!			n	n −1
Решение: Cn2 =			=	(	)	.
					2
2!(n −2)!

11

ЛЕКЦИЯ 2.

РАЗМЕЩЕНИЯ, ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ С ПОВТОРЕНИЯМИ.

Размещения с повторениями.

Определение. Рассмотрим множество Sn , состоящее из n элементов.

Размещением с повторениями из n элементов множества Sn по k

элементов называется всякая последовательность длины k , составленная из элементов этого множества (в последовательности возможны повторяющиеся элементы).

Теорема 2.1. Число упорядоченных выборок с повторениями из n элементов по k (число размещений с повторениями) равно

k	= n	k	(2.1)
An

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

Первый элемент выборки может быть выбран n способами, т.е. любой из n элементов множества Sn , 2-ой – также любой из n элементов и т.д. до k -го элемента выборки. Значит, по правилу умножения

k	= n n n ... n = n	k	.
A
n
	k

Например.

∙ Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово». Это слово набирается с помощью одного или нескольких дисков, на которых нанесены буквы (или цифры). Пусть на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько попыток может быть сделано человеком, не знающим секретного слова?

5	=12	5	= 248832 .
Решение: A12
∙ Сколько	существует			различных	индивидуальных

идентификационных номеров из 10 цифр ?

Решение. Поскольку номер нужно выбирать из неотрицательных целых чисел, меньших 10, то выбираются 10 цифр и каждая выбирается из 10

цифр с повторениями, поэтому	=10 - номеров.
A10
10	10

∙ Сколько различных автомобильных номеров можно составить, используя 10 цифр и 27 букв русского алфавита, если номер состоит из 4 цифр и 4 букв.

12

4	4	=10	4	27	4	=5314410000 .
Решение: N = A10	A27

Замечание. Основное свойство размещений – порядок – в размещениях с повторениями не нарушается: номера АН 4111 НН и НА 1411 НН – различные!

		Перестановки с повторениями.
	Идея перестановки с повторениями может показаться
бессмысленной,		поскольку		перестановки	ассоциируются						с
перегруппировками элементов множества: abc, acb, cba и т.д.
	Повторение предполагает возвращение объекта и повторное его
использование.
	Определение. Перестановкой с повторениями из							n элементов
множества Sn называется всякое размещение с повторениями длины n .
	Рассмотрим следующую задачу.
	Задача. Сколько различных слов (бессмысленных) можно составить,
переставляя буквы в слове «мама».
	Решение. Проблема состоит в том, что буквы повторяются. Если бы
буквы	были различны, то		существовало бы 4!= 24		способов составить
разные слова. В данном случае можно составить всего 6 слов:
	МАМА, ММАА, АММА, АМАМ, ААММ, МААМ.
	Почему так происходит? Чтобы понять, поставим в соответствие
цифрам 1 и 2 букву «М», а цифрам 3 и 4 букву «А».
	Тогда МАМА: 1324
	ММАА: 1234, но еще 2134, 2143, 1243 – буквы меняются, а
слово остается неизменным.
	Каждой перестановке букв соответствует 4 перестановки цифр
дающих одно и то же слово, значит, число различных слов:						4!	=		24	= 6 .
					4			4
	Рассмотрим задачу в общем виде.
	Пусть дана выборка длины n , составленная из элементов множества
X ={x1 , x2 ,..., xk }, причем элемент				x1 входит в эту выборку n1					раз, элемент
x2 - n2	раз, …,	элемент	xk −nk	раз. Причем n1 +n2 +...+nk = n .							Если

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

повторениями из элементов x1 , x2 ,..., xk , имеющими состав			(n1 , n2 ,..., nk ).
Число таких перестановок будем означать:
Pn (n1 ; n2 ;...; nk )=Cnn1 Cnn−2 n	Cnn−3 n −n	... C nk		.
1	1 2	n−(n1 +nk )

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

13

n1 ! n2 ! ... nk !

Но n элементов можно представить друг с другом n! способами. Поэтому, число различных перестановок с повторениями, имеющих состав

(n1 , n2 ,..., nk ) , т.е.

Pn (n1 , n2 ,..., nk )

в

n1 ! n2 ! ... nk ! меньше, чем n! . Получим

формулу:

Pn (n1; n2 ;...; nk )

=

n!

(2.2)

n ! n ! ... n !

1

2

k

Т.о. доказана следующая теорема.

Теорема 2.2. Пусть

n1 , n2 ,..., nk -

целые неотрицательные числа,

причем n1 +n2 +...+nk

= n . Число различных перестановок, которые можно

составить из n элементов,

среди которых n1 элементов 1-го типа, n2

элементов 2-го типа,…,

nk

элементов k -го типа равно:

Pn (n1 , n2 ,..., nk )=

n!

- полиномиальный коэффициент.

n ! n ! ... n !

1

2

k

Замечание. Пусть имеется n букв:

n1 букв a1 , n2 букв

a2 ,…,

nk

букв ak , причем

n1 +n2 +...+nk

= n . Тогда число различных слов, которые

можно составить из этих букв, очевидно, вычисляется по формуле (2.2).

Например:

∙ Сколько различных слов можно составить, переставляя буквы

слова «математика».

Решение:

P

2, 3, 2,1,1,1 =

10!

=

1 2 3 4 5 6 7 8 9 10

=6 5 7 8 9 10 =151200 .

10 (

)

2! 3! 2!

1 2 1 2 3 1 2

∙ Сколько слов длиною в восемь букв можно составить из букв «а» и

«б» таких, что количество букв «а» в этих словах не превышает 3-х?

Решение:

N = P

0;8 +P 1;7

+P

(

2;6

)

+P 3;5 =

8!

+

8!

+

8!

+

8!

=

8 (

)

8 (

)

8

8 (

)

7! 1!

2! 6!

3! 5!

8!

=1+8 +28 +56 =93 - слова.

Сочетания с повторениями.

Основным свойством сочетаний является их неупорядоченность, т.е.

abc = acb =bac =...

Рассмотрим задачу.

14

Задача. В кондитерском магазине продаются пирожные 4 сортов: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно

купить 7 пирожных?

Решение: Если записывать порядок, в котором продавец кладет пирожные в коробку, то получится выборка объема 7 из 4 элементов – сортов пирожных. Однако две выборки одного и того же состава, например (Н, П, Э, П, С, С, Э) и (Э, Н, С, Н, Э, П, С) означают по сути дела одну и ту же покупку: 2 наполеона, 2 эклера, 2 слоеных и 1 песочное. Значит, выборки должны отличаться только составом, а не порядком следования элементов. Таким образом мы пришли к задаче.

Задача. Сколько различных составов могут иметь выборки объема

k из n элементов?

По-другому эту задачу можно сформулировать и так: назовем две выборки эквивалентными, если они имеют одинаковый состав. На сколько

классов эквивалентности разбивается при этом вся совокупность выборок объема k из n элементов? Такие выборки называют сочетаниями с повторениями из n элементов по k , длины k из n видов, а их число

обозначают Cɶnk = fnk .

Для того, чтобы стало ясно, как вычисляются Cɶnk , вернемся к задаче

о пирожных. Каждой выборке поставим в соответствие последовательность из 0 и 1, составленную следующим образом: вначале пишем столько единиц, сколько в выборке стоит элементов 1-го типа, затем пишем 0, далее, столько единиц, сколько элементов второго типа, опять 0 и т.д. Например, если Н-2;

Э-3; П-1; С-1, то (2;3;1;1)→(1101110101) или (1100111011)→(2; 0;3; 2) .

Число нулей в записях будет равно 3, а единиц – 7. Переставляя нули и единицы, получим различные комбинации элементов. Число таких комбинаций равно числу перестановок с повторениями

f k = f 7

= P

3, 7

)

=

10!

=

8 9 10

=120 способов.

n

4

10

(

3! 7!

6

В общем случае получаем последовательность из k

единиц и n −1

нулей, т.е. последовательность

длины

n +k −1 .

Число таких

последовательностей равно числу способов выбора k

мест для единиц из

всех n +k −1 мест или n -1 места для нулей, т.е.

C k

=C n−1

.

n+k−1

n+k−1

Между

рассматриваемыми

выборками

и

построенными

последовательностями существует взаимнооднозначное соответствие. Поэтому число неупорядоченных выборок с повторениями равно

k	ɶk	k	(2.3)
fn	=Cn	=Cn+k−1

15

Например:

∙ Кости домино можно рассматривать как сочетания с повторениями из семи цифр 0,1,2,3,4,5,6 по две. Число всех таких сочетаний равно:

f 2	=C 2		=C 2	=	8!		=	7 8	= 28 .
7	7+2−1		8		2! 6!			2
∙ Сколько целых
		неотрицательных						решений имеет уравнение

x1 +x2 +...+xn = m ?

Решения данного уравнения можно интерпретировать так: если имеем целые неотрицательные числа x1 , x2 ,..., xn , такие, что

x1 +x2 +...+xn = m , то можно составить комбинацию из n элементов по m взяв x1 элемент 1-го типа, x2 -2-го типа,…, xn - n -го типа. Наоборот, имея

комбинацию из n по m элементов, получим решение уравнения. Т.о. число решений равно:

Cnm+m−1 =Cnn+−1m−1 .

Например, если x1 +x2 +x3 +x4		=10 , то число решений
f =C10	=C3	=	13!	= 286 .
10+4−1	13		4! 9!

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

fnk −n =Cnk+−kn−n−1 =Ckn−−11 .

Число различных сочетаний из k объектов по n объектов с повторениями, когда необходимо выбрать хотя бы по одному объекту каждого вида равно Ckn−−11 .

16

ЛЕКЦИЯ 3.

БИНОМ НЬЮТОНА. БИНОМИАЛЬНАЯ ТЕОРЕМА. ТРЕУГОЛЬНИК ПАСКАЛЯ.

ПОЛИНОМИАЛЬНАЯ ТЕОРЕМА.

Бином Ньютона – это достаточно хорошо известная формула в математике. Она представляет выражение (x −a)n , где n - целое

положительное число, в виде многочлена.

Из элементарной математики хорошо известны формулы

сокращенного умножения:
(x −a)2 = x2 −2xa +a2	(x +a)2 = x2 +2xa +a2
(x −a)3 = x3 −3x2 a +3xa2 −a3	(x +a)3 = x3 +3x2 a +3xa2 +a3

Естественно, возникает задача, найти общую закономерность в формулах (x −a)n для упрощения вычислений, хотя можно действие

осуществить последовательным раскрытием скобок.

Теорема 3.1 (биномиальная теорема).

Справедливы равенства

n

(x −a)n = ∑(−1)k Cnk xn−k ak k =0

n

(x +a)n = ∑Cnk xn−k ak k =0

(3.1)

(3.2)

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

Проведем доказательство формулы (3.1), используя свойства многочленов. Проследим за произведениями двучленов:

(x −a1 )(x −a2 )= x2 −a1 x −a2 x +a1a2 = x2 −(a1 +a2 )x +a1a2 ;

(x −a1 )(x −a2 )(x −a3 )=(x2 −(a1 +a2 )x +a1a2 )(x −a3 )=

=x3 −a3 x2 −(a1 +a2 )x2 +(a1 +a2 )a3 x +a1a2 x −a1a2 a3 =

=x3 −x2 (a1 +a2 +a3 )+x(a1a2 +a1a3 +a2 a3 )−a1a2 a3 .

Возьмем произведение n двучленов:

Pn (x)=(x −a1 )(x −a2 )(x −a3 ) ... (x −an ).

Если раскроем в нем скобки и сгруппируем члены с одинаковыми показателями степени, то получим многочлен, записанный по значениям показателей степеней, которые уменьшаются:

Pn (x)= xn −xn−1 (a1 +a2 +...+an )+xn−2 (a1a2 +a1a3 +...+an−1an )− −xn−3 (a1a2 a3 +a1a2 a4 +...+an−2 an−1an )+...+(−1)n x0 (a1a2 a3 ... an ).

17

Нетрудно заметить, что:

∙старший коэффициент t0 многочлена Pn (x) равен 1;

∙члены имеют знакочередующиеся коэффициенты;

∙каждый коэффициент tk представляет собой суммы всевозможных

сочетаний	элементов	множества Sn ={a1 ; a2 ;...; an }	взятых по k
элементов этого множества, то есть:
k =1:	a1 , a2 , a3 ,..., an
k = 2 :	a1a2 ; a1a3 ;...; an−1an
Число всех сочетаний из n элементов по k равно			C k . В случае,
			n
когда a1 = a2 = a3 =... = an		= a имеем:

Pn (x)=(x −a)n = xn −Cn1 xn−1a +Cn2 xn−2 a2 −Cn3 xn−3 a3 +...

+(−1)k Cnk xn−k ak +...+(−1)n an

Таким образом k -ый коэффициент имеет вид:

			−1 k	C k xn−k ak ,
t	k	=			k = 0, n
		(	)	n

Тогда, из условия, что

t0 =(−1)0 Cn0 xn−0 a0 = xn

tn =(−1)n Cnn x0 an =(−1)n an

получим формулу:

n

(x −a)n = ∑(−1)k Cnk xn−k ak , что и требовалось доказать.

k =0

Для доказательства формулы (3.2) применим метод математической индукции.

Докажем, что

n

(x +a)n = ∑Cnk xn−k ak . k =0

Действительно, при n =1 формула справедлива:

1

n =1: (x +a)1 = ∑Cnk xn−k ak =C10 x1a0 +C11 x1−1a1 = x +a .

k =0

Далее, предположим, что при n −1 формула верна и докажем, что она верна и для n . Имеем:

n−1

(x +a)n =(x +a)n−1 (x +a)=(x +a)n−1 x +(x +a)n−1 a = x ∑C k− xn−1−k ak +

n 1

		k =0
n−1	n−1	n−1

+a ∑Cnk−1 xn−1−k ak = ∑Cnk−1 xn−k ak +∑Cnk−1 xn−1−k ak +1 = k =0 k =0 k =0

18

Во втором слагаемом

заменим индекс суммирования

=

n−1

k

n−1−k

k +1

n

j−1

n−j

=

j −1 = k, тогда j

a

a

j

= k +1: ∑Cn−1 x

= ∑Cn−1 x

k =0

j=1

n−1

n

= ∑Cnk−1 xn−k ak +∑Cnk−−11 xn−k ak =

k =0

k =1

Выравняем пределы суммирования в обеих

=

суммах. Для этого введем дополнительно : .

n

=0;

−1

Cn−1

Cn−1 = 0

n−1

n

Тогда

∑Cnk−1 xn−k ak = ∑Cnk−1 xn−k ak

k =0

k =0

n

n

∑Cnk−−11 xn−k ak = ∑Cnk−−11 xn−k ak

k =1

k =0

n

n

n

= ∑Cnk−1 xn−k ak +∑Cnk−−11 xn−k ak = ∑(Cnk−1 +Cnk−−11 )xn−k ak =

k =0

k =0

k =0

(

n −1 !

(

n −1 !

(

n −1 !

C k

+C k −1

=

)

+

)

=

)

+

n−1

n−1

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

=

(

n −1 !

(

n −1 ! n −k +k

)

n!

k

=

)

)(

+

=

=

=Cn

k !(n −k )!

k !(n −k )!

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

n

= ∑Cnk xn−k ak , что и требовалось доказать.

k =0

Как видим из бинома Ньютона, число сочетаний возле каждого из его членов играют важную роль. Поэтому Cnk называют биномиальными

коэффициентами.

Историческая справка.

На самом деле бином Ньютона для целых положительных n знали еще до Ньютона (1643-1727) среднеазиатские математики, в частности, Омар Хайям (1048-1131), а в Западной Европе – Паскаль (1623-1662). Заслуга Ньютона состоит в том, что он обобщил эту формулу для дробных и отрицательных показателей n . Про это открытие Исаак Ньютон сообщил в 1676 году, но полноценного доказательства не имел. Его доказательство базировалось больше на примерах и аналогиях, нежели на теории. В 1774 году эту теорему пытался доказать Леонард Эйлер и только в 1812 году ее доказал Карл Фридрих Гаусс с помощью теории бесконечных сумм.

Длинный путь в истории – большое значение для науки.

19

Для n нецелого при x < 1 , формула имеет вид:

(1 + x)α = 1 + α x + α (α −1) x2 + α (α −1)(α − 2) x3 + ...

2! 3!

+ α (α −1)(α − 2)...(α − k +1) xk + ...

k !

Например:

1.Найти разложение (2x +3y2 )4 .

Решение. n = 4 , значит

(2x +3y2 )4 =C40 (3y2 )0 (2x)4 +C41 (3y2 )1 (2x)3 +C42 (3y2 )2 (2x)2 +C43 (3 y2 )3 (2x)1 +

+C44 (3y2 )4 (2x)0 =16x4 +4 3y2 8x3 + 4! 9 y4 4x2 + 4! 27 y6 2x +1 81y8 1 =
2! 2!	3! 1!

=16x4 +96x3 y2 +216x2 y4 +216xy6 +81y8 .

2.Найти коэффициент при x4 y6 в разложении (3x +4 y)10 .

Решение. Слагаемое, содержащее x4 y6 имеет вид:

C106 (3x)4 (4 y)6 = 10! 34 x4 46 y6 = 7 8 9 10 46 34 x4 y6 =
6! 4!	1 2 3 4

=210 4096 81x4 y6 =69672960x4 y6 .

3.Найти шестой член в разложении (2x −3y)6 .

Решение. tk =(−1)k Cnk ak xn−k .

t	= −1 5	C5		2x	1 3 y	5	=−	6!		35 y5 2x =−6 243 2xy5 =−2916xy5 .
			(			)
5	( )	6			) (			5! 1!

4.Найти наибольший член разложения (5 +3)10 :

Решение: tk =C10k

3k (

)10−k

5

, причем tk

>tk −1 и tk >tk +1 .

k

k

10−k

−1

11−k

3

( 5)

k −1 k

( 5)

C10

>C10 3

10−k

9−k

k

k

( 5)

( 5)

k +1 k +1

C10

3

>C10 3

20