Зачем делить в комбинаторике

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

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

Последнее, что нужно заметить — то, что нам не важен порядок команд. Например, если Пин окажется в первой команде, а все остальные во второй — то же самое, что Пин во второй команде, а все остальные в первой. Тем самым все способы разделяются на пары одинаковых. Поэтому, чтобы посчитать окончательное количество способов, надо поделить число на два: способов разбиться на две непустые команды.