Дискретная математика / ДМ_Комбинаторика

Ответ: если n 1, то S 1 ; если n 1, то S 1.

Задание 2.4. Найти коэффициент при x k в разложении данного выражения Р по полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов.

Пример решения задания 2.4.

Найти коэффициент при x30 в разложении данного выражения 3 x2 x5 19 по полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов.

Решение. Общий член разложения по полиномиальной формуле имеет вид:

3m x2 n x5 k P m, n, k .

Для отыскания всех случаев, в которых возникает x30 , решаем в целых неотрицательных числах уравнение 2n 5k 30 . Выразим из уравнения k: k 6 2n5 . Так как k может принимать только целые неотрицательные значения, то 6 2n5 0 и n должно быть кратно 5, отсюда 0 n 15 и n 5 (делится нацело). Выпишем все такие случаи:

11

n 0 ,

k 6 ;

n 5 ,

k 4 ;

n 10 ,

k 2 ;

n 15 ,

k 0 ;

Для каждой найденной

пары

значений

n и

k

находим значение m

из

уравнения

m n k 19. В результате получим

четыре набора

m, n, k :

13, 0,

6

, 10, 5, 4 ,

7, 10, 2 ,

4, 15, 0 .

Слагаемы содержащие x30 , таковы:

313 x2 0 x5 6 P 13, 0,

6 ;

310 x2 5 x5 4 P 10, 5,

4 ;

37 x2 10 x5 2 P 7, 10,

2 ;

34 x2 15 x5 0 P 4, 15,

0 .

Тогда коэффициент при x30 имеет вид:

13

10

7

4

3

3

3

3

19!

4!15!0!

.

13!0!6! 10!5!4!

7!10!2!

13

10

7

4

3

3

3

3

Ответ: 19!

.

13!0!6!

10!5!4!

7!10!2! 4!15!0!

3. Формула включений и исключений

Пусть имеется N предметов, которые могут обладать свойствами 1, 2 , , n . Обозначим

через N 1, 2 , , k

количество предметов,

обладающих

набором

свойств

1, 2 , , k ,

1 k n , а через N 1, 2 , , k – количество предметов, не обладающих ни одним из указан-

ных свойств. Тогда справедлива формула включений и исключений:

N 1, 2 , , n N N 1 N 2 N n N 1, 2 N 1,3 N n 1, nN 1, 2 ,3 1 n N 1, 2 , , n .

Количество перестановок n различных предметов, при которых ни один предмет не стоит

на своём первоначальном месте, обозначается Dn

и вычисляется по формуле

1

2

n

n

1

1

1

n

1

Dn n! Cn

n 1 ! Cn n 2 ! 1

Cn

или

Dn n! 1

1

.

3!

1! 2!

n!

Количество перестановок n различных предметов, при которых ровно k предметов стоят на

своих первоначальных местах, обозначается Dn,k

и вычисляется по формуле

D

C k D

.

n,k

n n k

Задание 3.1. Сколько натуральных чисел от 1 до 10000 не делится ни на , ни на , ни на, ни на ?

12

Пример решения задания 3.1.

Сколько натуральных чисел от 1 до 10000 не делится ни на 2, ни на 4, ни на 5, ни на 9?

Решение. Если число не делится на 2, то оно и подавно не будет делиться на 4. Поэтому число 4 в условии можно опустить.

Заметим, что на 2 делится каждое второе натуральное число, на 5 – каждое пятое, на 9 – каждое девятое, на 2 и на 5 – каждое 10-е, на 2 и на 9 – каждое 18-е и т.д. Воспользуемся формулой включений и исключений, обозначив искомое число через М, при этом через [A] будем обозначать целую часть числа A. Получим:

	M 10000	10000				10000				10000				10000				10000				10000				10000			10000 5000
			2				5				9				10				18				45				90

2000 1111 1000 555 222 111 3555.

Ответ: 3555 чисел.

Задание 3.2. Найти количество различных перестановок цифр данного числа , при которых никакие n одинаковых цифр не идут друг за другом.

13

Пример решения задания 3.2.

Найти количество различных перестановок цифр данного числа 123132, при которых никакие 2 одинаковые цифры не идут друг за другом.

Решение. Общее количество различных перестановок цифра данного числа равно

	P 2, 2, 2	6!			720	90 .
		2!2!2!			8

Если какие-то две одинаковые цифры стоят рядом, мы можем считать эту пару единым символом, например 112323 становится 12323. Тогда количество перестановок, содержащих этот символ, равно

	P 2, 2, 1	5!			120		30 .
		2!2!1!			4

Число таких случаев для нашего примера равно C31 3 .

Аналогично находим количество перестановок, в которых присутствуют два двойных символа, например 112332 становится 1232:

P 2, 1, 1 2!1!1!4! 242 12 .

Число таких случаев равно C32 3 . Остается найти количество перестановок, в которых три двойных символа, например 112233 рассматривается как 123. Находим

P 1, 1, 1 P3 3! 6 .

Применяя формулу включений и исключений, получим: 90 3 30 312 6 30. Ответ: 30 перестановок.

Задание 3.3. Сколько существует перестановок n различных предметов, при которых на своих первоначальных местах окажутся ровно k или ровно m предметов?

14

Пример решения задания 3.3.

Сколько существует перестановок 9 различных предметов, при которых на своих первоначальных местах окажутся ровно 2 или ровно 6 предметов?

Решение. Количество различных перестановок девяти предметов, при которых на своих первоначальных местах окажутся ровно 2 предмета, равно D9,2 , а количество различных переста-

новок девяти предметов, при которых на своих первоначальных местах окажутся ровно 6 предметов, равно D9,6 . Применяя правило сложения, а также формулу для вычисления Dn,k , получим:

			2			6		9!						1			1			1			1		1		1		1			9!				1				1			1
D D		C		D	C		D			7! 1																								3! 1
9,2	9,6		9	7		9	3
								2!7!						1! 2! 3! 4! 5! 6! 7!																		6!3!				1!				2!			3!
										9!			1854						9!		2 66912.
										2!7!							6!3!

Ответ: 66912 перестановок.

4. Задачи о распределениях

Пусть имеется n шаров, которые распределяются по k ящикам. Тогда количество способов распределения для различных случаев равно:

1) шары различимы, ящики различимы, все ящики в результате распределения непустые:

k 1

U * n, k 1 i Cki k i n ;

i0

2)шары различимы, ящики различимы, допускаются пустые ящики:

U n, k k n ;

3) шары различимы, ящики неразличимы, все ящики непустые:

	V * n, k	U * n, k				;
		k!
4)	шары различимы, ящики неразличимы, допускаются пустые ящики:
	k
	V n, k V * n, i ;
	i 1
5)	шары неразличимы, ящики различимы, все ящики непустые:
	T * n, k C k 1		;
		n 1
6)	шары неразличимы, ящики различимы, допускаются пустые ящики:
	T n, k C k 1			;
		n k 1
7)	шары неразличимы, ящики неразличимы, все ящики непустые:
	W * n, k W n k, k ;
8)	шары неразличимы, ящики неразличимы, допускаются пустые ящики:

k

W n, k W * n, i ,

i 1

15

на практике удобно пользоваться рекуррентной формулой

W n, k 1 W n, k W * n, k 1 , k 1, 2, .

Пара совместно рекурсивных формул для W * n, k и W n, k позволяет вычислять количе-

ства способов распределения при больших значениях n и k с помощью чисел W * , W с меньшими значениями этих переменных.

Задание 4.1. Сколькими способами можно распределить n различных открыток в k

1)различных;

2)неразличимых конвертов,

если: а) все конверты должны быть непустые; б) допускаются пустые конверты? (Рассмотреть 4 случая)

Пример решения задания 4.1.

Сколькими способами можно распределить 6 различных открыток в 4 1) различных; 2) неразличимых конвертов, если: а) все конверты должны быть непустые; б) допускаются пустые конверты?

Решение. 1а) Если конверты различимы, и все они должны быть непустые, то число способов распределения равно

3
U * 6, 4 1 i C4i	4 i 6	C40 46 C14 36 C42 26 C43	4096 4 729 6 64 4 1560 .
i 0

1б) Если конверты различимы и допускаются пустые конверты, то число способов распределения равно

U 6, 4 46 4096 .

2а) Если конверты неразличимы, и все они должны быть непустые, то число способов распределения равно

V * 6, 4 U * 6, 4 1560 65 . 4! 24

2б) Если конверты неразличимы и допускаются пустые конверты, то число способов распределения равно

	4											U * 6, 1			U * 6, 2		U * 6, 3
	V 6, 4 V * 6, i V			* 6, 1 V * 6, 2 V * 6, 3 V * 6, 4
	i 1											1!		2!		3!
			C 0	26 C1		C 0	36	C1	26	C 2
	65 C 0		2	2		3		3		3	65 1 31 90 65 187.
	1			2				6

16

Ответ: 1а) 1560; 1б) 4096; 2а) 65; 2б) 187.

Задание 4.2. Сколькими способами можн6о представить число n в виде k а) неотрицательных, б) положительных целых слагаемых, если представления, отличающиеся только порядком слагаемых, считаются:

1) различными, 2) одинаковыми? (Рассмотреть 4 случая)

Пример решения задания 4.2.

Сколькими способами можн6о представить число13 в виде 4 а) неотрицательных, б) положительных целых слагаемых, если представления, отличающиеся только порядком слагаемых, считаются: 1) различными, 2) одинаковыми?

Решение. Данная задача равносильна задаче распределения 13 неразличимых шаров (т.е. единиц, образующих число 13) по 4 ящикам (4 слагаемым).

1а) Если слагаемые неотрицательны, а представления, отличающиеся только порядком слагаемых, считаются различными, то количество различных способов представления числа 13 в виде суммы 4 слагаемых равно

T 13, 4 C 4 1	1	C3		16!	560 .
13 4		16		3!13!

1б) Если слагаемые положительны, а представления, отличающиеся только порядком слагаемых, считаются различными, то количество различных способов представления числа 13 в виде суммы 4 слагаемых равно

T * 13, 4 C 4 1	C3		12!	220 .
13 1	12	3!9!

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

одинаковыми, нужно найти числа W n, k и W * n, k для случаев неотрицательных и положительных слагаемых соответственно.

Заметим, что существует только одно представление числа n n 1 одним слагаемым, по-

этому W * n, 1 W n, 1 1. Если число положительных слагаемых в представлении совпадает с самим числом, т.е. n k , то W * n, k 1 при n k 1, 4 . Если же число положительных слагае-

мых больше самого числа, т.е.	n k , то	W * n, k 0 . Поэтому	W * 1, k 0 для	k 2, 3, 4 ,
W * 2, k 0 для k 3, 4 , W * 3,	4 0 .

С учётом замечания и формулы для W n, k , находим

17

W 1, 2 W * 1, 1 W * 1, 2 1 0 1,

W 1, 3 W 1, 2 W * 1, 3 1 0 1,

W 1, 4 W 1, 3 W * 1, 4 1 0 1.

Далее, так как W * 2, 1 1, W * 2, 2 1, W * 2, 3 W * 2, 4 0 , то

W 2, 2 W * 2, 1 W * 2, 2 1 1 2,

W 2, 3 W 2, 2 W * 2, 3 2 0 2,

W 2, 4 W 2, 3 W * 2, 4 2 0 2.

Аналогично, W * 3, 1 1, W * 3, 2 W 3 2, 2 W 1, 2 1, W * 3, 3 1, W * 3, 4 0 , тогда

W 3, 2 W * 3, 1 W * 3, 2 1 1 2,

W 3, 3 W 3, 2 W * 3, 3 2 1 3,

W 3, 4 W 3, 3 W * 3, 4 3 0 3.

Продолжим вычисление чисел W n, k и W * n, k . Заполним таблицу, в левом верхнем уг-

лу каждой клетки поместим число W n, k , а в правом нижнем углу – число W * n, k . Получим

k		1		2		3		4
n
1	1		1			1		1
		1			0		0	0
2	1		2			2		2
		1			1		0	0
3	1		2			3		3
		1			1		1	0
4	1		3			4		5
		1			2		1	1
5	1		3			5		6
		1			2		2	1
6	1		4			7		9
		1			3		3	2
7	1		4			8		11
		1			3		4	3
8	1		5			10		15
		1			4		5	5
				18

9	1		5		12		18
		1		4		7	6
10	1		6		14		23
		1		5		8	9
11	1		6		16		27
		1		5		10	11
12	1		7		19		34
		1		6		2	15
13	1		7		21		39
		1		6		14	18

Как видно из таблицы, W * 13, 4 18, W 13, 4 39 .

Ответ: 1а) 560; 1б) 220; 2а) 39; 2б) 18.

5. Арифметический треугольник

Коэффициенты обобщённого арифметического треугольника обозначаются через Cm n, k и вычисляются по формулам:

при n 1
	1,	если k m 1,
Cm 1, k
	0, если k m 1;
при n 1
	k
Cm n 1, k i , если k m 1,
i 0
Cm n, k
m 1
	Cm n 1, k i , если k m 1.
i 0

Теорема. Число Cm n, k равно количество n-разрядных чисел в m-ичной системе счисления, сумма цифр которых равна k (допускаются числа, начинающиеся с 0).

Свойства коэффициентов обобщённого арифметического треугольника:

1)C2 n, k Cnk ;

2)Cm n, k Cm n, m 1 n k (свойство симметричности);

3)Cm n, 0 Cm n, 1 Cm n, m 1 n mn (свойство суммы).

Задание 5.1. Имеется m различных шаров, которые помечают цифрами 1, 2, …, m (каждый шар помечен одной цифрой). Шары помещают в мешок, из которого затем наудачу извлекают шар. Номер шара фиксируется, шар возращают обратно в мешок. Процедура повторяется n раз.

Сколько существует различных случаев, при которых сумма выписанных чисел оказалась бы равной k?

19

Пример решения задания 5.1.

Решим задачу при m 8, n 4, k 21.

Решение. Перейдем от шаров, помеченных цифрами 1, 2, …, 8, к шарам, помеченным цифрами 0, 2, …, 7. Тогда сумме номеров, равной 21, полученной прежними метками, будет соответствовать сумма, образованная новыми метками, равная 21 4 17 . При этом каждой «новой» записи будет соответствовать некоторое 4-значное число в 8-ичной системе счисления, причём некоторые числа могут начинаться с нулей. Общее количество 4-значных чисел в 8-ичной системе счисления, сумма цифр которых равна 17, выражается коэффициентом C8 4, 17 .

По свойству симметричности C8 4, 17 C8 4, 7 4 17 C8 4, 11 . Остается найти коэффициент C8 4, 11 , построив арифметический треугольник 8 порядка и применив формулу

7

C8 4, 11 C8 3, 11 i C8 3, 11 C8 3, 10 C8 3, 9 C8 3, 8 C8 3, 7 C8 3, 6

			i 0									3, 5 C8 3, 4 .
										C8
	k	0	1	2	3	4	5	6	7	8		9	10		11
n
1		1	1	1	1	1	1	1	1	0		0	0		0
2		1	2	3	4	5	6	7	8	7		6	5		4
3		1	3	6	10	15	21	28	36	42		46	48		48
4															284

C8 4, 11 15 21 28 36 42 46 48 48 284 .

Ответ: 284 случая.

Задание 5.2. Игральная кость бросается n раз. Во сколько раз число способов набора суммы в p очков превышает число способов набора суммы в k очков?

20