Функции и размещения

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

Термины “функция”, “отображение”, “преобразование” и “соответствие” будут в дальнейшем использоваться как синонимы. При этом запись f: XY означает, что f есть функция с областью определения X, область значений которой содержится во множестве Y, то есть для каждого xX функция f определяет единственный элемент y = f(x)  Y.

Пусть даны множества X, Y, причем множество X содержит n элементов (|X| = n), а множество Y содержит m элементов (|Y| = m). В этих терминах задача может быть сформулирована следующим образом: сколько существует функций (отображений) , удовлетворяющих заданным ограничениям. Элементы множества X соответствуют объектам, элементы множества Y- ящикам, а каждая функция f : X Y определяет некоторое размещение, указывая для каждого объекта xX ящик y = f(x)  Y, в котором данный объект находится.

Другую традиционную интерпретацию можно получить, трактуя Y как множество цветов, а f(x) как “цвет объекта x”. Наша задача эквивалентна, таким образом, вопросу, сколькими способами можно покрасить объекты так, чтобы были соблюдены некоторые ограничения.

Наконец, каждому отображению f : XY, X = n, Y=m, можно взаимно однозначно сопоставить слово< f(x₁), ... , f (x_n)> = <y₁, y₂, ... , y_n> = = y₁ y₂ ...y_n в алфавите из m символов. Получаем третью эквивалентную формулировку задачи: подсчет числа слов в алфавите, удовлетворяющих заданным ограничениям.

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

Утверждение 1.1. Если |X| = n, |Y| = m, то количество всех функций равно mⁿ.

Эквивалентное утверждение 1 .1^. Число слов длины n в алфавите из m символов равно mⁿ.

Доказательство. Без потери общности можно всегда считать, что X = {1,..., n}, Y = {1,..., m}. Каждую функцию можно тогда отождествить с последовательностью < f(1),..., f (n)> = < y₁ ,...,y_n> . Каждый член y_i последовательности можно выбрать m способами, что дает mⁿ возможностей выбора последовательности <y₁ ,...,y_n>.

Определения.

Отображение : X  Y сюръективно, если для каждого элемента yY существует хотя бы один элемент xX , такой что (x)=y (в каждом ящике при размещении находится хотя бы один объект, все буквы алфавита используются в слове, все цвета используются при окраске).

Отображение : X инъективно если . 

В перечисленных интерпретациях основной задачи сюръективному отображению соответствуют такие размещения объектов по ящикам, что каждый ящик не пуст; раскраски объектов такие, что все цвета использованы при раскраске; слова в заданном алфавите, такие что в каждом слове использованы все буквы алфавита. Инъективному отображению соответствуют такие размещения объектов по ящикам, в которых каждый ящик содержит не более одного объекта; такие раскраски объектов, при которых цвета всех объектов различны и, наконец, слова в алфавите, все буквы которых различны.

Если x - действительное число, положим по определению

[x]_n = x (x-1)(x-2)...(x-n+1).

Обозначение [x]_n читается как “n факториал от x вниз” или “нижняя n-ая степень x”.

Утверждение 1.2. Число инъективных отображений (инъекций) множества X из n элементов, | X| = n, во множество Y из m элементов, |Y|= m, есть [m]_n .

Эквивалентное утверждение 1 .2^. Число слов длины n без повторений букв в алфавите из m букв есть [m]_n .

Доказательство. Будем определять на этот раз число инъективных, (то есть имеющих все различные члены) последовательностей <y₁ ,...,y_n>. Элемент y₁ может быть выбран m способами, элемент y₂ можно выбрать m-1 способом из оставшихся элементов. В общем случае, если уже выбраны элементы y₁ ,...,y_i-1, то в качестве y_i может быть выбран любой из m-i +1 элементов множества Y\{y₁,...,y_i-1}. (Принимаем, что mn, если n>m, то и [m]_n и искомое число функций равно 0). Это дает m(m-1)...(m - n+1) возможность выбора инъективных последовательностей <y₁ ,...,y_n>. 

Отметим, что

Определение.

Каждое взаимно однозначное отображение f :XX называется перестановкой множества x. 

В соответствии с утверждением 1 .2 число перестановок n- элементного множества равно n!.