Сочетания с повторениями.

Пусть А = {a₁, a₂,…, a_n}, где a₁, a₂,…, a_n - “представители” 1-го, 2-го, … n-го типа элементов. Объектов каждого типа имеется в неограниченном количестве, элементы одного типа неразличимы между собой.

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

Пусть в него входят: r₁ объектов 1-го типа,

r₂объектов 2-го типа,

. . . . . . . . .

r_n объектов n-го типа; .

Некоторые r_i могут быть равны 0. Сочетанию можно поставить в соответствие следующую схему:

Вертикальные черточки отделяют элементы одного вида от элементов другого вида. Если элементов какого-либо вида нет, две черты будут рядом. Количество черточек равно (n-1). Каждому сочетанию с повторениями соответсвует схема и наоборот, каждая подобная схема соответствует некоторому сочетанию с повторениями.

Количетво сочетаний с повторениями из n по m равно числу таких схем.

Всего в схеме (n -1)+m объектов, (n -1) – черточек и m – нулей. Число схем равно числу различных перестановок из (n + m–1) – элементов, среди которых (n– 1) – одинаковых “|” и m – одинаковых “0”.

 

 

Например: