2014-06-08
Сколько различных пар непересекающихся подмножеств имеет множество, состоящее из $n$ элементов?
Решение:
Найдем количество различных пар непересекающихся подмножеств при условии, что в паре выделены первое и второе подмножества. Для каждого из $n$ элементов есть 3 возможности: его можно или включить в первое подмножество, или включить во второе подмножество, или не включать ни в одно из них. Поэтому количество указанных пар равно $3^{n}$. Среди них есть одна пара, в которой оба подмножества пусты. Оставшиеся $(3^{n} -1)$ пары в свою очередь разбиваются на двойки совпадающих пар, если разрешить переставлять в парах местами первое и второе подмножества. Таким образом, существует $(3^{n} - 1)/2$ (неупорядоченных) пар подмножеств, из которых хотя бы одно не пусто. Всего же имеется $(3^{n} - 1)/2 + 1 = (3^{n} + 1)/2$ различных пар подмножеств, удовлетворяющих условию задачи.