П.7. Мультимножества (сочетания с повторениями)

Отказ от различимости элементов множества приводит к понятию мультимножества, т.е. под мультимножеством мы понимаем совокупность элементов среди которых могут быть одинаковые (неразличимые). Всякое мультимножество A можно представит его основанием base (A), т.е. множеством всех его различных элементов и функцией n: base (A) ® N такой, что n(a) равно кратности элемента a - числу повторений элемента a в мультимножестве A.

Способы задания мультимножества аналогичны способам задания множества. Например, мультимножество A = { a , a , a , a , a , a } имеет основание base (A) = { a , a , a } и кратности n(a ) = 3, n(a ) = 2, n(a ) = = 1. Число элементов конечного мультимножества равно числу элементов в нём учитывая их кратность и обозначается | A |.

Два мультимножества называются равными, если равны их основания и равны функции кратности (достаточно потребовать равенства функций кратности). Мультимножество не содержащее элементов называется пустым, пустое мультимножество единственно и обозначается Æ, |Æ| = 0.

Пусть B = { b ,..., b } - множество, | B | = n.

Определение. Мультимножество A, содержащее k элементов и такое, что base (A) Í B называется сочетанием с повторением из n элементов множества В по k.

Пример 1. Пусть B = { b , b , b } - множество, | B | = 3. Выпишем все 2-х элементные сочетания с повторениями из множества B:

{ b , b },{ b , b },{ b , b },{ b , b },{ b , b },{ b , b }. n