Различные наборы

Даны множества:

X₁={1,2,3,4,5,6,7}, X₂={2,5}, X₃={1,2,3,4,5,6,7,8,9}, X₅={3,5}, X₆={1,3,5,6,7}, X₇={2,3,5,7,8,9}, X₈={5,7,8}, X₉={2,3,7,9}.

Сколько существует наборов различных цифр (a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈, a₉) таких, что a_i∈X_i Предъявите все эти наборы.

• Подсказка

Подсказка


• Решение

Решение



Запишем матрицу инцидентности

B=(b_ij), i=1,…,9; j=1,…,9 семейства множеств X₁, X₂,…, X₉. . В этой матрице необходимо найти все наборы (трансверсали) вида b_1j1,…, b_9j9 где j₁,…, j₉ – некоторая перестановка цифр 1,2,…,9, и все b_ijk=1, i=1,…,9; k=1,…,9 . Иными словами, ищутся такие наборы из 9 единиц, что все единицы одного набора лежат в разных строках и разных столбцах. Для облегчения поиска переставим в матрице В строки и столбцы по следующему правилу: строки с меньшим количеством единиц ставим выше, а столбцы с большим количеством единиц – левее. Таким образом переставленная матрица приведена на рисунке. 






 Поскольку единицы надо выбирать из разных строк и столбцов, сначала следует выбирать 1 из отмеченной пунктиром матрицы 3 на 3 – в ней две трансверсали. Затем выбираются трансверсали в двух отмеченных прямоугольником матрицах 3 на 3 – в каждой из них по 3 трансверсали. Значит, всего 18 трансверсалей.

• Ответ

Ответ

18 наборов: 

(1, 2, 3, 4, 5, 6, 7, 8, 9), (1, 2, 3, 4, 5, 6, 8, 7, 9), (1, 2, 3, 4, 5, 6, 9, 8, 7), 

(1, 5, 2, 4, 3, 6, 7, 8, 9), (1, 5, 2, 4, 3, 6, 8, 7, 9), (1, 5, 2, 4, 3, 6, 9, 8, 7), 

(4, 2, 3, 1, 5, 6, 7, 8, 9), (4, 2, 3, 1, 5, 6, 8, 7, 9), (4, 2, 3, 1, 5, 6, 9, 8, 7), 

(4, 5, 2, 1, 3, 6, 7, 8, 9), (4, 5, 2, 1, 3, 6, 8, 7, 9), (4, 5, 2, 1, 3, 6, 9, 8, 7), 

(6, 2, 3, 4, 5, 1, 7, 8, 9), (6, 2, 3, 4, 5, 1, 8, 7, 9), (6, 2, 3, 4, 5, 1, 9, 8, 7), 

(6, 5, 2, 4, 3, 1, 7, 8, 9), (6, 5, 2, 4, 3, 1, 8, 7, 9), (6, 5, 2, 4, 3, 1, 9, 8, 7).