Между множествами

Иногда бывает необходимо сопоставлять друг с другом элементы некоторых множеств. Рассмотрим, например, два множества: стадо из четырех овец и рощу из четырех деревьев. Эти множества находятся между собой в таком отношении, в каком ни одно из них не находится с кучей из трех камней или с рощей из семи деревьев. Их можно попарно сопоставить друг с другом, привязав овец к де­ревьям, так что каждая овца и каждое дерево будут в точ­ности принадлежать одной и той же паре. Такое соответствие между элементами двух множеств называется взаимно однозначным соответствием.

Пусть X и Y два конечных множества: m- и n-элементные. Между ними можно установить взаимно однозначное соответствие только в том случае, если m=n. Сколько же существует таких взаимно однозначных соответствий для двух n-элементных множеств X и Y? Первый элемент множества X может быть сопоставлен с любым из n эле­ментов множества Y. Для каждого такого сопоставления второй элемент множества X может быть сопоставлен с любым из оставшихся n-1 элементов множества Y и т. д. После того, как такое сопоставление проведено для n-1 элементов множества X, последний элемент этого множества будет сопоставляться с единственным остав­шимся элементом множества Y. Таким образом, общее число взаимно однозначных соответствий для n-элементных множеств будет n(n-1) ... 1=n!