2Дискретка / комбинаторика

m!(n − m )!

n!

4. Комбинаторика

Перестановка – это упорядоченный набор чисел 1, 2,..., n , обычно трактуемый как биекция на множестве {1, 2,..., n} , которая числу i ставит в соответствие i-й

элемент из набора. Число n при этом называется порядком перестановки.

Число всех перестановок порядка n обозначается P и равняется факториалу

n

P = n! .

n

В более общем смысле, перестановкой произвольного (обычно конечного) множества называется всякая биекция этого множества на себя. Если

исходное			множество содержит qi элементов i -го			сорта,	q1 + ... + qm = n и
элементы			одного		сорта идентичны, то число	таких	перестановок
n (	1	m )		n!	.
P	q	,..., q	=

q1 ! qm !

Размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размещением (из n по m) называется упорядоченный набор из m различных элементов некоторого n-элементного

	множества. Число размещений из n по					m обозначается	Am	и	задается
							n
	соотношением Am =	n!		.	Нетрудно	видеть, что при	n = m		число
		(n − m )!
	n

размещений превратиться в число перестановок P = n! .

n

Размещение с повторениями – это размещение предметов в предположении, что каждый предмет может участвовать в размещении сколь угодно раз. По правилу умножения количество размещений с повторениями из n по m равно

Anm = nm .

Если на каждую i-ю из m позиций можно поставить один из qi элементов, то количество таких размещений Anm (q1 ,..., qn )= q1 qn .

Сочетанием из n по m называется набор m различных элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания

отличаются от размещений. Число сочетаний Cnm = .

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

(m + n −1)!

повторениями равно Cnm = Cmm+ n−1 = m!(n −1)! .

Свойства сочетаний:

n

1. Бином Ньютона (a + b )n = ∑Cmn ambn −m ,

m=0

2. Cnm = Cnn −m ,

3. Cnm = Cnm−−11 + Cnm−1 ,

4. Cnm = n Cnm−−11 ,

m

5. CnmCmk = Cnk Cnm−−kk .

Комбинаторные правила: 1. Правило суммы.

Если объект A выбирается n способами, объект B выбирается другими k способами, то «либо A , либо B » можно выбрать n + k способами.

2. Правило произведения.

Объект A выбирается n способами, и объект B после этого выбирается

kспособами, то выбрать « A , а после этого B » можно n k способами.

3.Принцип включений-исключений.

Пусть A , A ,..., A

- конечные множества, тогда

1

2

n

∑

∑

∑

− ... +

−1

n−1

A ∩ A ∩ ... ∩ A

.

A

=

A

−

A ∩ A

j

+

A ∩ A

∩ A

i

i

i

i j

k

(

)

1 2

n

i

i

i< j

i < j <k

Определение:

Вероятность Ρ события A – отношение числа благоприятных исходов к общему числу исходов.

Пример 4.1:

Пусть есть m различных шаров и n различных урн. Найти число способов раскладки шаров по урнам.

Решение:

Каждый шар может занимать одно из n мест, то есть n – число способов размещения одного шара по n урнам, воспользуемся правилом произведения, получим nm .

Пример 4.2:

Сколькими способами можно разместить m одинаковых шаров по n различным урнам?

Решение:

Каждой раскладке шаров по урнам сопоставим бинарный вектор из m + n − 1 элементов, нули – шары ( m штук), единицы – внутренние перегородки ( n − 1 штук).

0 0 0 1 0 1 1 0 0

Число раскладок равно числу перестановок элементов вектора без учёта

(m + n − 1)!

перестановок нулей и единиц, то есть Cmm+ n −1 = m!(n − 1)! .

Пример 4.3:

Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в неё вошло не более 3 юношей?

Решение:

Воспользуемся правилом суммы и получим ответ

Пример 4.4:

n > 2 человек садятся за круглый стол, 2 размещения по местам будем считать совпадающими, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол?

Решение:

Пример 4.5:

Сколько можно построить функций со значениями на множестве из m

элементов, если функции зависят от n переменных x1 ,..., xn , где xi может принимать одно из ki значений?

Решение:

Рассмотрим n =1 , тогда для каждого аргумента из k1 можно поставить одно

из m значений, то есть m m , обобщив на случай произвольного n , получим

ki

Пример 4.6:

Из колоды (52 карты) вынули 10 карт. Найти вероятность того, что

1.выбран ровно один туз,

2.выбран хотя бы один туз,

3.не менее двух тузов.

Решение:

Так как вероятность – отношение числа благоприятных исходов к общему числу исходов, то найдём общее число исходов, для всех подзадач оно будет одинаковым и равным C5210 , то есть можно выбрать 10 любых карт из колоды.

1.Один туз мы можем выбрать 4-мя способами (по числу мастей в картах). После этого выберем не из тузов оставшиеся 9 карт, это можно

сделать C 9	способами, в итоге получим ответ	4C489		.
48		C	10
		52

2.Чтобы выбрать хотя бы один туз можно из общего числа способов выбрать 4 карты вычесть выборки без тузов, которые можно сделать

C10	способами. В итоге получим ответ	C10	− C10
		52		48	.
				10
48		C
			52

3.Для выборки не менее двух тузов отнимем от общего числа способов число способов выборки без тузов и с одним тузом. В итоге получим

ответ C5210 − C4810 − 4C489 .

C5210

Пример 4.7:

Сколькими способами можно составить три пары из n шахматистов?

Решение:

Для формирования трёх пар выберем с учётом порядка 6 шахматистов, это можно сделать An6 способами. Так как порядок внутри пары не важен (число способов установить порядок внутри пар 23 ) и порядок самих пар

(перестановки 3!) тоже не важен, то итоговый ответ будет	A6
	n	.
	23 3!

Пример 4.8:

Сколько существует n -значных чисел, у которых сумма цифр равна k ,

где k < 10 , k = 10 ?

Решение:

Задача сводится к урновой схеме, где n – число различных урн и k – количество одинаковых шариков (один шар – единица). При рассмотрении случая, когда k < 10 мне не можем в одну из позиций положить больше девяти шаров. Один из шаров мы положим в первую урну, так как первая цифра числа не нуль, остаётся разложить k − 1 шар. Поэтому при k < 10 ответ будет Cnk+−k1−2 способов.

Если k = 10 , то следует вычесть из общего числа способов варианты, когда в одной из урн становится более 9-ти шариков. Таких вариантов может быть только один, когда в первую урну к уже имеющемуся шарику добавляют ещё

9 шаров, поэтому ответ в случае k = 10 будет C k −1 − 1 .

n + k −2

Пример 4.9:

Сколько существует 10-значных чисел, в которых имеется хотя бы две одинаковые цифры?

Решение:

Для решения задачи из общего числа 10-значных чисел вычтем число чисел, без повторов цифр. Общее количество 10-значных чисел:

В случае чисел без повторов на первую позицию выбираем одну из цифр 1,2,…,9, а на каждую оставшуюся позицию одну из оставшихся цифр – это можно сделать 9 9! способами. В итоге получим ответ 9 109 − 9 9!.

Пример 4.10:

Сколько слов можно составить из пяти букв А и не более чем из трёх букв Б?

Решение:

Для получения количества слов нужно просуммировать количество слов, полученных из 5 букв А и не одной Б, из 5 букв А и 1 буквы Б, из 5 букв А и 2 букв Б, из 5 букв А и 3 букв Б. Также следует не учитывать перестановки

	одних и тех же букв. В итоге получим ответ 1	6!			7!			8!			= 84 .
		+			+			+
			5! 1!			5! 2!			5! 3!
	Пример 4.11:
	В урне a белых и b чёрных шаров ( a ≥ 2 ,							b ≥ 2 ).			Из урны без

возвращения извлекаются 2 шара. Найти вероятность того, что шары одного

цвета.
Решение:
Общее число исходов C 2		–		выбор двух шаров из		смеси шариков.
a +b
Благоприятные варианты C 2	(выбор белых шаров) или C 2					(выбор чёрных
a					b
шаров). В итоге получим ответ			C 2	+ C 2
			a	b	.
			Ca2+b

Пример 4.12:

Найти вероятность того, что при размещении n различных шаров по N различным урнам заданная урна будет содержать ровно k ( 0 ≤ k ≤ n ) шаров.

Решение:

Общее число размещений шаров по урнам – урновая схема, число таких способов N n . Сформировать заданную урну можно Cnk способами, то есть

выбрать k шариков из общего количества без учёта порядка в урне. После этого оставшиеся n − k шариков разложим по N −1 урнам, применим урновую

C k (N −1)n −k

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

N n

Пример 4.13:

Колода из 32 карт тщательно перетасована. Найти вероятность того, что все 4 туза лежат в колоде один за другим.

Решение:

Общее число перестановок колоды карт 32! . Представим туз одной картой, в итоге получим 32 − 4 + 1 = 29 карт, где одна карта есть склеенные тузы, число перестановок новой колоды 29! . Учитывая перестановки тузов 4! получим

окончательный ответ 29! 4! .

32!

Пример 4.14:

Какова вероятность угадать k номеров в спортлото 6 из 49?

Решение:

Общее число билетов C496 , то есть выбираем 6 чисел из 49. Для формирования нужного билета нужно выбрать k номеров из шести C6k , а затем добрать оставшиеся номера из 43 не выпавших чисел C436−k . В итоге получим ответ

C k C 6− k

6 43 . C496

Пример 4.15:

Поступающий в ВУЗ сдаёт 4 экзамена. Достаточно набрать 17 баллов. Сколькими способами можно набрать 17 и более баллов?

Решение:

Рассмотрим варианты набора 20, 19, 18 ,17 баллов. 20 баллов можно набрать при получении 5, 5, 5, 5 – 1 вариант. 19 баллов можно набрать при получении 5, 5, 5, 4 с учётом перестановок (получение разных оценок по разным

	предметам), но без учёта перестановок пятёрок –	4!	= 4 . 18 баллов можно
		3!

набрать, если получить 5, 5, 5, 3 или 5, 5, 4, 4 с учётом получения разных оценок за разные экзамены и без учёта перестановок одинаковых оценок –

4!	+		4!				= 10 . 17 баллов можно набрать, если получить 4, 4, 4, 5 или 3, 4, 4, 5 –
3!				2! 2!
4!		+		4!	= 16 . Просуммировав варианты получим 31 способ.
2!			3!

Пример 4.16:

Сколькими способами можно выбрать 6 карт из колоды (52 карты) так, чтобы среди них были карты каждой масти?

Решение:

Существует два варианта формирования шести карт. Первый: выбираем масть, которая даст три карты, затем выбираем эти три карты, потом

3

добираем из оставшихся мастей по любой карте – C41C133 (C131 ) варианта.

Второй вариант: выбираем две масти, которые дадут по две карты, затем выбираем из каждой масти по две карты, потом добираем оставшиеся карты

2 2

– C42 (C132 ) (C131 ) варианта. Воспользуемся правилом суммы и получим

3 2 2

итоговый ответ C41C133 (C131 ) + C42 (C132 ) (C131 ) способов.

Пример 4.17:

Сколько пятизначных чисел можно составить из цифр числа 75226522?

Решение:

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

7, 2, 6, 5, 5 – Ρ (1,1,1, 2), 7, 6, 5, 2, 2 – Ρ (1,1,1, 2), 7, 2, 2, 5, 5 – Ρ (1, 2, 2) , 6, 2, 2, 5, 5 – Ρ (1, 2, 2) , 7, 5, 2, 2, 2 – Ρ (1,1, 3) , 7, 6, 2, 2, 2 – Ρ (1,1, 3) , 5, 6, 2, 2, 2 – Ρ (1,1, 3) , 7, 2, 2, 2, 2 – Ρ (1, 4), 5, 2, 2, 2, 2 – Ρ (1, 4), 6, 2, 2, 2, 2 – Ρ (1, 4), 5, 5, 2, 2, 2 – Ρ (2, 3) ,

просуммировав варианты получим 265 вариантов.

Пример 4.18:

Имеется множество C, состоящее из n элементов. Сколькими способами можно выбрать в C два подмножества A и B так, чтобы множества A и B не пересекались?

Решение:

Любой элемент может попасть в одно из множеств A и B или не попасть в них. Итоговый ответ 3n .

Пример 4.19:

Сколько существует n-значных натуральных чисел, у которых цифры расположены в неубывающем порядке?

Решение:

Рассмотрим урновую схему, где сначала идут единицы, затем двойки и т.д. Также возможен вариант, что каких либо цифр нет. Цифры будут служить

урнами, а разряды шариками. Получим ответ Cnn+9−1 = (n +8)! .

n! 8!

Задачи для самостоятельного решения

1.Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом?

2.Сколько существует чисел от 0 до 10n , в которые не входят две идущие друг за другом одинаковые цифры?

3.Сколько диагоналей в выпуклом n -угольнике?

4.В футбольной команде (11 человек) нужно выбрать капитана и ассистента. Сколькими способами можно это сделать?

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

6.В классе 31 человек, сколькими способами можно выбрать команду (11 человек) так, чтобы Петя и Вася не входили в команду одновременно?

7.Множество состоит из n элементов, сколько множеств можно построить из данного множества (мощность множеств всех подмножеств)?