Пример 1.Каждый кортеж N , где , кодируется k-элементным подмножеством множества . Поэтому, при фиксированном k, число всех кортежей N , где , равно . n

Пример 2. Перечисление беспорядков степени n. Обозначим U - множество всех перестановок степени n, . Будем считать, что элементами перестановок являются числа . Перестановка степени n называется беспорядком, если для всех .

Существует только один беспорядок степени 2.

Существует только два беспорядка степени 3.

Для обозначим множество всех перестановок степени n таких, что . Число всех беспорядков степени n равно числу всех перестановок степени n не принадлежащих множеству . Обозначим число всех беспорядков степени n. По формуле включения- исключения

, (1)

где суммирование ведётся по всем кортежам N таким, что

. Легко видеть, что для любого кортежа N , где справедливо равенство

.

При фиксированном k число всех кортежей N , где , равно . Из равенства (1) следует, что

.

Поэтому

. n