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

							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'а) выслать на проверку.

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

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

Крупным недостатком рекуррентного способа задания последовательностей является необходимость вычисления всех предыдущих членов последовательности при вычислении нужного члена. Само вычисление при этом можно осуществлять как итерационным способом, так и рекурсивно. В некоторых случаях удается осуществить переход от рекуррентного способа к явному заданию последовательности в виде функции, то есть формулой общего члена. Такой переход принято называть решением рекуррентного соотношения. Для различных частных случаев имеются специфические способы решения.

Здесь мы рассмотрим рекуррентные соотношения глубины два, имеющие в общей ситуации вид и приводящиеся к так называемым линейным однородным разностным уравнениям с постоянными коэффициентами. Теория для этого класса разностных уравнений фактически аналогична соответствующим методам для линейных дифференциальных уравнений, в том числе и неоднородных. Даже имеется весьма точный аналог операционному исчислению в виде дискретного преобразования Лапласа. Мы рассмотрим простейшую ситуацию.

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

Опишем способ решения этого соотношения.

1 шаг. Составить и решить характеристическое уравнение, соответствующее исходному разностному уравнению. Это уравнение , то есть обычное квадратичное уравнение. Пусть его корни и .

2 шаг. Составление общего решения исходного разностного уравнения. Этот вид зависит от корней характеристического уравнения.

·  Если и , то общее решение исходного уравнения имеет вид: , где и ‑ произвольные постоянные;

·  Если и , то общее решение исходного уравнения следует искать в виде ;

·  Если , то есть корни комплексные, то, как известно, они будут сопряженными комплексными числами. Пусть тригонометрическая форма записи одного из этих корней имеет вид . Тогда общее решение разностного уравнения можно искать в виде .

3 шаг. Определение значений констант из общего решения за счет использования начальных условий. Нужно составить систему двух уравнений приравнивая выражение для общего решения при п=0 значению и при п=1 значению . Решив систему нужно полученные значения констант подставить в общее решение, что и даст искомый ответ.