Геометрия окружностей - Учебное пособие (Мендель В.В.)

Ii. классические задачи, связанные с конечными множествами

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

Например, рассмотрим задачу о перечислении всех подмножеств содержащих k-элементов множества А, содержащего n-элементов (n³k). Используя простые отображения (или знания комбинаторики) получим, что число подмножеств равно , где .

Расположим элементы множества А в виде последовательности {а1, а2, …, аn}. И поставим в соответствие подмножеству вектор, состоящий из 0 и 1, состоящий из n-элементы. У этого вектора на i-том месте стоит 1, если элемент ai принадлежит подмножеству и 0, если элемент ai не принадлежит подмножеству. Такой вектор называется вектором инцидентности подмножества. Вектор, соответствующий подмножеству содержит k единиц и n-k нулей. Следовательно, число подмножеств такое же, как и число векторов с k единицами. Данный вектор можно рассматривать как число в двоичной системе исчисления, содержащее k единиц и не более чем n разрядов. Так как двоичные числа легко перечисляются, то используя соответствие  мы легко пересчитаем подмножества. В частности подсчитав подмножества множества А, мы построим формулу

.

Здесь 2n – это число двоичных чисел содержащих не более чем n разрядов. Другой любопытной задачей, связанной с конечным множеством из n-элементов является задача о перестановках элементов этого множества. Перестановка элементов множества это, фактически, взаимно однозначное отображение этого множества на себя. Найти количество перестановок не составляет труда, всего перестановок n!, но получить хорошее описание всех перестановок задача для школьника нетривиальная.