Решение

Очевидно, что если n  1, то первая цифра таких наборов может быть выбрана двумя разными способами. Для всякого i < n  1 и выбранного начала набора длины i значение следующей цифры набора может быть выбрано двумя способами. Если уже выбраны значения первых n – 1 цифр набора, то значение последней цифры может быть выполнено единственным способом так, чтобы дополнить сумму предшествующих цифр до нечетного значения. Поэтому условия правила умножения выполнены со значениями m₁, . . . , m_n1, m_n, равными 2, . . . , 2, 1. Следовательно, число двоичных наборов, содержащих нечетное число единиц, равно 2^n1.

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

Решение

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

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

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

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

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

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

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

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

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

26⁵ + 26⁶ = 26⁵27.

2.4. Размещения и сочетания

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

ОПРЕДЕЛЕНИЕ

Размещениями из n элементов по m элементов множества D называются m-элементные последовательности, каждый член которых является элементом D.

Здесь предполагается, что m  0. При этом, если m = 0, то соответствующее размещение не содержит ни одного элемента и является пустым.

Если множество D неизвестно или не уточняется, то говорят о размещениях из n по m.

Например, слово FALKON может рассматриваться как размещение из 26 элементов символов английского алфавита по 6.

Размещение называется размещением без повторений, если все входящие в него элементы являются разными.

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

Размещение, в котором могут встречаться одинаковые элементы, называется размещением с повторениями. Из приведенных определений следует, что всякое размещение без повторений одновременно является и размещением с повторениями.

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

Определим число различных размещений из n по m без повторений. В таких размещениях первый элемент может быть выбран n способами, при всяком способе выбора первого элемента выбор второго элемента может быть осуществлен n1 разными способами и т.д. При всяком способе выбора значений первых m 1 элементов последний mй элемент может быть выбран n  m + 1 способом.

По правилу умножения число таких размещений не зависит от множества A и равно значению произведения:

n  (n  1)  ...  (n  m + 1).

Для обозначения число размещений без повторений из n по m применяется специальное выражение . Поэтому: = .

В размещениях из n по m с повторениями каждый элемент такого размещения может быть выбран n способами. Поэтому по правилу умножения число размещений с повторениями из n по m равно .

Число размещений с повторениями обозначается как . Следовательно, справедливо соотношение: = .

Частным случаем размещений без повторений являются размещения всех элементов множества или перестановки элементов множества. Как следует из приведенных формул число P_n перестановок элементов произвольного n элементного множества равно n