Методы пересчета. 
Задачи и теории дискретной математики

В классической комбинаторике используются три основных метода пересчета: геометрический, рекуррентных соотношений и производящих функций. Метод производящих функций является одним из наиболее развитых комбинаторных методов. Главные его идеи были впервые высказаны в конце XVIII века в работах Лапласа по теории вероятностей. Поясним их на следующем примере.

Пример 1. Используя биномиальный ряд Ньютона, получить некоторые свойства для сочетаний.

Решение. Рассмотрим биномиальный ряд Ньютона.

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

1) Пусть — натуральное число, тогда все слагаемые в правой части, начиная с + 2 слагаемого (+ 1), обращаются в нуль. Получаем в этом случае бином Ньютона.

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

а).

б).

Складывая и вычитая полученные соотношения, получаем еще два свойства для чисел сочетаний:

где — целая часть числа.

В данном случае функцию = (1 + называют производящей функцией числа сочетаний из элементов.

Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere — возвращаться). Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить.

Пример 2. Используя метод рекуррентных соотношений, получить формулу для числа перестановок элементов без повторений.

Решение. Пусть у нас есть предметов, , …,,. Любую их перестановку можно получить, если присоединить элемент к перестановке, , …,. Число различных мест, которые может занять элемент, равно, и поэтому перестановок из элементов в раз больше, чем перестановок из элементов. Тем самым установлено рекуррентное соотношение.

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

Поскольку из одного элемента можно сделать лишь одну перестановку, то и.

Решение. Обозначим через количество пар кроликов по истечении месяцев с начала года, тогда через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца, то есть еще пар кроликов. Следовательно, имеет место рекуррентное соотношение.

По условию и, а далее последовательно находим, Числа называют числами Фибоначчи.

а).	или.
б).	или.

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

а) Поскольку от точки до точки, (, существует путей, то по правилу сложения получаем.

Полученное соотношение можно переписать на языке сочетаний с повторениями:

б) Учитывая, что количество кратчайших путей от точки до точки можно найти и иначе, а именно как, получаем следующее соотношение:

Решение. 1 способ (вычислительный).

2 способ (комбинаторный).

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

3 способ (геометрический).

Обратим внимание на то, что к точке можно пройти обязательно через одну из двух точек и, а к ним ведут и путей соответственно. Тогда получаем.

4 способ (производящих функций).

В примере 11 показано, что является производящей функцией для числа сочетаний. Поскольку то коэффициенты при в левой и в правой частях тождества равны.

Вопрос 1.

Условие. Пусть U — множество точек плоскости, на которой задана декартова система координат. Найти пересечение множеств , объединение , разности множеств АВ, ВА, дополнения множеств А', В', изобразить их на плоскости:

;

1) Пересечение множеств.

;

2) Объединение множеств.

;

3) Разность множеств.

;

4) Разность множеств.

;

5) Дополнения множеств А'.

;

6) Дополнения множеств В'.

Вопрос 2 [2.1(1)].

Условие. Доказать выполнимость следующего соотношения .

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

Пусть, , .

а) Рассмотрим. Найдем множество. По определению .

Обозначим через x все элементы, которые удовлетворяют следующим условиям:, , а через у все элементы с, такие что .

Следовательно,, .

По определению декартового произведения множеств.

(1).

б) Рассмотрим выражение .

По определению декартового произведения множеств.

;

.

Тогда состоит из множества всех упорядоченных пар, таких, что a=b=x, c=y, т. е.

(2).

Из равенства правых частей соотношений (1) и (2) следует, что .

Вопрос 3 [3.2(15)].

Условие. Построить композиции отображений g°f и f°g; проверить, являются ли они инъективными, сюръективными или биективными.

f:C>R⁺, y=|x|², g:R>R, y=log₂(x²+3).

Композиция функций не является сюрьецией, так как нет ни одного элемента, для которого есть образ, например, y=0. Композиция функций не является инъекцией, так как для разных элементов есть одинаковые образы .

Таким образом, — ни сюръекция, ни инъекция, но является отображением, так как каждому элементу соответствует только один элемент .

Композиция функций не является сюрьецией, так как нет ни одного элемента, для которого есть образ y<0. Композиция функций не является инъекцией, так как для разных элементов есть одинаковые образы. Таким образом, композиция функций — не биективно, но является отображением, так как каждому элементу соответствует только один элемент .

Вопрос 4 [4.2(14)].

Условие. На множествах А и В заданы отношения порядка и соответственно и задано отображение где ,. Определить, является ли оно изотонным, изоморфизмом или автоморфизмом.

;; ;

Проверим, является ли отображение изотонным.

Найдем образы функции. ,, ,,. Отображение f не сохраняет порядок, так как выполняется, а, т. е. не выполняется. Следовательно отображение не изотонно.

Вопрос 5 [7.3(1)].

Условие. Проверить полноту систем функций.

Проверить полноту системы функций.

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

- класс функций, сохраняющих 0;

- класс функций, сохраняющих 1;

- класс самодвойственных функций;

- класс монотонных функций;

- класс линейных функций.

Для исследуемой системы составим таблицу Поста. Если функция входит в функционально замкнутый класс, то в таблице Поста в соответствующей ячейке ставится знак «+», иначе — знак «-».

Для исследования системы на полноту построим таблицы истинности функций и .

1. Обозначим .

Из таблицы видно, что функция не сохраняет 0 и сохраняет 1. Данная функция немонотонна, так как набор (0, 0) предшествует набору (1, 0), но. На противоположных наборах (0, 0) и (1, 1) функция принимает одинаковые значения 1, следовательно, она несамодвойственна.

Для проверки линейности построим канонический полином Жегалкина:

. Функция не линейна, так как содержит элемент .

2. Обозначим .

По таблице видим, что сохраняет 0 и не сохраняет 1. Функция монотонна. На противоположных наборах 0 и 1 функция принимает одинаковые значения 0, следовательно, она несамодвойственна.

3. Построим таблицу Поста для заданной системы.

;		;	;	;
	;	;

Система функций будет полна, если в каждом столбце таблицы Поста стоит, хотя бы один знак «-». Система функций полна.

Вопрос 6 [8.1(1)].

Построим таблицу истинности для данной формулы:

Формула является тавтологией, так как не существует интерпретация, на которой она принимает ложное значение.

Вопрос 7. Синтезировать в базисе И-НЕ (ИЛИ-НЕ) устройство, заданное логической функцией:

Решение.

а) приводим функцию к базису И-НЕ.

Построим логическую схему.

б) приводим функцию к базису ИЛИ-НЕ.