3. Кортежи.

Не всегда удается составить математическую модель комбинаторной задачи, используя лишь упомянутые выше понятия теории множеств. Во многих комбинаторных задачах существенную роль играет порядок элементов (например, порядок обработки детали на различных станках, порядок солдат в строю и т. д.), в то время как для множеств порядок элементов роли не играет. Далее, часто возникают комбинаторные задачи, в которых некоторые элементы следует считать неразличимыми, тождественными (как, например, две белые шашки из одного и того же комплекта, две автомашины одной и той же марки, цвета и года выпуска и т. д.). Поэтому возникает необходимость ввести новое математическое понятие, которое можно было бы использовать и в таких задачах. Этим понятием является «кортеж» (или, как его еще называют, «слово», -мерный вектор»).

Пусть дано некоторое множество Возьмем множество натуральных чисел и зададим некоторое отображение множества во множество Это значит, что числу 1 ставится в соответствие элемент числу 2 — элемент числу элемент . В результате мы получаем набор элементов множества X, в который некоторые элементы могут входить несколько раз (ведь при отображении в X может случиться, что различным числам отвечает один и тот же элемент множества X). Располагая элементы этого набора по порядку номеров, мы получаем кортеж длины составленный из элементов множества Слово «кортеж» по-французски означает торжественное шествие (иногда и по-русски говорят «свадебный кортеж», «кортеж автомашин» и т. д.). Элемент называют компонентой или координатой кортежа

Кортежи длины 2 называют парами (точнее говоря, упорядоченными парами), а кортежи длины 3 — тройками. Иногда и кортежи длины называют -ками. Примерами кортежей могут служить слова (кортежи, составленные из букв алфавита), десятичные записи чисел (кортежи, составленные из цифр) и т. д.

Два кортежа считают равными, если они имеют одинаковую длину, причем их компоненты, имеющие одинаковые номера, равны. Мы будем обозначать кортежи греческими буквами. Итак, если то в том и только в том случае, когда для всех

Например, если то так как Кортежи не равны, так как имеют различную длину. Кортежи и имеют одинаковую длину и состоят из одних и тех же элементов, но они не равны, так как порядок их компонент различен.

Компонентами кортежа могут быть множества, кортежи и т. д. Например, кортежи равны, так как множества и совпадают (для множеств порядок элементов

не играет роли), а кортежи различны, так как различны кортежи и являющиеся их первыми компонентами.

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

Подчеркнем еще раз отличия понятия кортежа от понятия множества:

а) в множестве порядок элементов не играет роли, а кортежи, отличающиеся порядком элементов, различны даже в том случае, когда они имеют один и тот же состав;

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