1. Если g и f – сюръекции, то их композиция – сюръекция;

2. Если g и f – инъекции, то их композиция – инъекция;

3. Если g и f –биекции, то их композиция – биекция;

3. Некоторые специальные функции

1) Перестановка множества A была определена ранее.

2) Тождественная функция была определена ранее.

3) Пусть задано некоторое множество M  U. Характеристической функцией этого множества является функция χ, равная 1 на элементах множества M:

4) Бинарной операцией на множестве A называется функция b : A A  A. Образ пары (x,y) при отображении b записывается как b(x,y) или как xby.

Поскольку область значений бинарной операции на A по определению есть подмножество A, то множество A обладает свойством замкнутости относительно бинарной операции.

5) Конечной последовательностью называется функция из N₀ ={0, 1, 2, 3, …, n} в некоторое множество A. f : N₀  A Бесконечной последовательностью называется функция из {0, 1, 2, 3, …} в некоторое множество A. Элементом последовательности является упорядоченная пара (n,a), в которой a = f(n). Обычно эта пара обозначается через a_n, а последовательность f : N₀  A – через {a_n }.

Иногда нумерацию членов последовательности начинают с 1, т.е. иногда последовательностью называют функцию, определенную на множестве N.

23. Широко известными видами последовательностей являются арифметическая и геометрическая прогрессии.

6) Еще одна известная специальная функция, которая далее потребуется при комбинаторных вычислениях – факториал. На примере этой функции уместно вспомнить о принципе математической индукции.

Принцип математической индукции состоит в следующем.

Если некоторое свойство P выполняется на элементе 0, и для любого nN из выполнимости P на элементе n следует его выполнимость на элементе n+1, то свойство P выполняется на любом элементе nN.

Формальная запись: P ( (P(0),nN P(n)P(n+1))  nN P(n) ).

Принцип математической индукции позволяет доказывать утверждения, проверять свойства и давать индукционные определения. Итак, для доказательства свойства P согласно принципу мат. индукции выполняются следующие шаги:

1. База (базис) индукции. Проверяется выполнение P(0).

2. Индукционный переход. Предполагается, что выполнено P(n). Показывается, что тогда выполнено и P(n+1): P(n)P(n+1).

Иногда удается установить выполнение свойства P(k) только начиная с некоторого k>0 и P(n)  P(n+1) n  k.

Индукционное определение понятия P(n) дается следующим образом:

1. Задается значение P(0);

2. Задается правило получения P(n+1) по числу n и значению P(n).

24. Индукционное определение факториала f = n! будет выглядеть следующим образом: f(0)=1; f(n+1)=f(n)(n+1).

(следующий файл)

20