Дискретная математика (стр. 3 )

Здесь n! (эн факториал) определяется следующим образом:

1.  0!=1;

2.  .

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

1.  ;

2.  при .

Если при этом , то , где .

Перестановками с повторениями из элементов рассматриваемого множества Х называются перестановки всех элементов множества Х, в которых элементы одного типа не различаются (то есть перестановка однотипных элементов не изменяет данную перестановку с повторениями).

Количество перестановок с повторениями обозначается и может быть вычислено по формуле:

.

Размещениями (без повторений) из n элементов по m называют упорядоченные последовательности n – элементного множества Х длиной в т элементов, состоящие из различных элементов.

Количество размещений из п элементов по т обозначают . Формула для вычислений имеет вид:

.

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

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

.

Сочетанием (без повторений) из п элементов по т называется всякое т-элементное подмножество п-элементного множества с различными элементами.

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

.

Количество сочетаний для краткости также называют просто сочетаниями. Сочетания обладают рядом важных свойств. Отметим несколько простейших, основополагающих свойств:

1°. ;

2°. Для имеем ;

3°. Для выполняется .

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

							1
						1		1
					1		2		1
				1		3		3		1
			1		4		6		4		1
		1		5		10		10		5		1
	1		6		15		20		15		6		1
1		7		21		35		35		21		7		1
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.

Сочетания с повторениями. Пусть имеется п конечных множеств, в каждом из которых содержатся однотипные (не различимые в условиях рассматриваемой задачи элементы) в количестве не меньшем т. Для такой ситуации всякое т-элементное подмножество из объединения данных множеств называется сочетанием с повторениями из п по т.

Количество таких сочетаний с повторениями (также для краткости называемые сочетаниями с повторениями) обозначается . Вычислить значение можно по формуле:

.

Задачи для решения:

Задача 1. Номер машины имеет формат БЦЦЦББ, где Б – буква, а Ц – цифра. В качестве букв используются только те, которые имеют одинаковое начертание в латинице и кириллице, то есть это буквы из множества . Цифрами являются все цифры десятичной системы счисления. Сколько можно составить различных номеров указанного формата?

Задача 2. В ящике сборщика 8 деталей, среди которых 3 детали окрашены. Сборщик наудачу извлекает 5 деталей. Сколько существует различных наборов из 5-ти деталей, среди которых две окрашены?

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

ТЕМА 2
Бином Ньютона

Общие указания: Разобраться в теоретическом изложении, решить предложенные задачи, решения и ответы выслать для проверки в виде текстового файла (документ Word'а).

Учитывая правила умножения и действия со степенями, получим:

1.  ;

2.  ;

3.  ;

4. 
.

Сравнивая последовательности коэффициентов, полученные при возведении (a+b) в целую степень, со строками треугольника Паскаля (см. тему 1) мы видим их совпадение для нескольких первых степеней. Методом математической индукции (учитывая также свойства числа сочетаний, отмеченные в теме 1) можно показать, что это не случайное совпадение, а закономерный результат. Итоговым утверждением здесь является так называемая формула бинома Ньютона:

.

Пример: Вычислить .

При вычислении используем соответствующую строку 1, 5, 10, 10, 5, 1 из треугольника Паскаля. Получаем:

.

Задачи для решения

Вычислить:

1.  ;

2.  .

ТЕМА 3
Использование разностных уравнений для решения
рекуррентных соотношений

Общие указания: Рассмотреть алгоритм решения линейных однородных разностных уравнений с заданными начальными условиями и решить предложенные задания. Решения в виде текстовых файлов (документ Word'а) выслать на проверку.

Мы будем рассматривать только рекуррентные соотношения глубины два (обобщение на случай большей глубины тривиально).

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