По следам Великого Комбинатора

Вы, наверное, уже догадались, что всего пар будет 30. Но можно сделать это очевидным.
Расположим списки кошек и собак немного по-другому: кошек по вертикали, а собак – по горизонтали:

1. БАРБОС 2. БИМ 3. ЖУЧКА 4. ПОЛКАН 5. ЦЕРБЕР 6. ШАРИК
1. БАЗИЛИО Барбос-Базилио Бим-Базилио Жучка-Базилио Полкан-Базилио Цербер-Базилио Шарик-Базилио
2. БЕГЕМОТ Барбос-Бегемот Бим-Бегемот Жучка-Бегемот Полкан-Бегемот Цербер-Бегемот Шарик-Бегемот
3. ВАСЬКА Барбос-Васька Бим-Васька Жучка-Васька Полкан-Васька Цербер-Васька Шарик-Васька
4. МУРКА Барбос-Мурка Бим-Мурка Жучка-Мурка Полкан-Мурка Цербер-Мурка Шарик-Мурка
5. ЛЕОПОЛЬД Барбос-Леопольд Бим-Леопольд Жучка-Леопольд Полкан-Леопольд Цербер-Леопольд Шарик-Леопольд

Теперь сразу видно, что каждая возможная пара образуется на пересечении строки и столбца.

Можно сформулировать и общее правило- правило произведения:
Если элемент из множества A можно выбрать m способами, и после каждого такого выбора элемент из множества B можно выбрать n способами, то выбор пары (A,B) можно осуществить mn способами.

Когда применять правило суммы, а когда правило произведения? Это легко запомнить: если «или» (кошка или собака), то пользуемся правилом суммы, а если «и» (кошка и собака), то правилом произведения.