Формулы числа сочетаний с повторениями.

Число всех сочетаний с повторениями по 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.