Формулы числа сочетаний с повторениями. Число всех сочетаний с повторениями по m из n элементов обозначается

Число всех сочетаний с повторениями по m из n элементов обозначается .

Формула числа сочетаний с повторениями из n элементов по m сводится к формуле числа сочетаний без повторений из n + m -1 элементов по m.

Теорема. .

Доказательство. Сочетание a₁a₂…a _m не меняется от перестановки элементов. Поэтому мы одинаковые элементы можем размещать рядом.

Пусть a₁, a₂, …, a _m Î{ a ₁, a ₂, …, a_n }. Тогда каждое сочетание по m из n элементов множества { a ₁, a ₂, …, a_n } с повторениями можно представить следующим образом:

a ₁… a ₁(s ₁ раз) a ₂… a ₂(s ₂ раз)… a_n … a_n (s_n раз), (1)

где s ₁, s ₂,…, s_n ³0, s ₁+ s ₂+…+ s_n = m.

Каждому сочетанию (1) мы поставим в соответствие последовательность

1…1(s ₁ раз)01…1(s ₂ раз)0…01…1(s_n раз). (2)

В последовательности (2) m единиц и n -1 нулей. Указанное соответствие является биекцией между множеством всем сочетаний с повторениями по m из n элементов множества { a ₁, a ₂, …, a_n } и множеством всех последовательностей, состоящих из единиц и n -1 нулей.

Рассмотрим (m + n -1)-множество A номеров элементов последовательности (2). Множество номеров элементов последовательности (2), равных единице, является m -подмножеством множества A, т.е. сочетанием без повторений по m из m + n -1 элементов множества A. Это соответствие между множеством всех последовательностей вида (2) и множеством всех m -подмножеством множества A является биекцией. Значит, сочетаний с повторениями по m из n столько же, сколько сочетаний без повторений по m из m + n -1.