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

Понятно, что первая цифра в таких последовательностях может быть выбрана любой, а число выборов значения каждой последующей цифры в последовательности зависит от предшествующей ей цифры набора. Например, двухэлементная последовательность 2, 3 может быть продолжена 8 способами, а другую двухэлементную последовательность 2, 5 можно продолжить лишь 6 разными способами. Следовательно, для данной задачи условия правила умножения не выполнены. Поэтому для её решения, нельзя использовать правило умножения.

Правило сложения обычно применяется в случаях, когда множество комбинаторных объектов неоднородно, не может быть представлено конструкциями одной и той же структуры, для которой существует простая формула определения числа разных конструкций.

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

Рассмотрим пример задачи, решаемой с помощью правила сложения.

Пусть требуется определить число различных слов в английском алфавите, имеющих длину 7 и начинающихся либо с символов WH, либо с символа F. Напомним, что английский алфавит состоит из 26 символов.

Очевидно, что заданное множество слов распадается на две части:

1) множество A ₁ - слова, начинающиеся с WH;

2) множество A ₂ - слова, начинающиеся с F.

С помощью правила умножения можно показать, что A ₁ содержит 26⁵ различных слов, а A ₂ - 26⁶ слов. Поэтому общее количество слов в рассматриваемом множестве равно

26⁵ + 26⁶ = 26⁵ · 27.

РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ

Пусть D - конечное множество, содержащее n элементов.