Теорема 1.Для всех k, n ÎN

. (1)

Доказательство. Каждое мультимножество A такое, что base (A) Í B, | A | = = k, кодируется кортежем (n(b ),..., n(b ))Î N таким, что n(b ) +... + +n(b ) = k. Поэтому равно числу кортежей (r ,..., r ) Î N и таких, что . Докажем равенство

= + . (2)

Кортежи N и такие, что бывают двух сортов.

Кортежи первого сорта это те кортежи у которых . Число таких кортежей равно числу кортежей N и таких, что и поэтому равно .

Кортежи второго сорта это те кортежи у которых . Их число равно числу таких кортежей N у которых и поэтому равно .

Из выше доказанного следует справедливость равенства (2).

Докажем теперь равенство (1) индукцией по числу m = k + n.

Для m = 2, k = n = 1 и равенство (1) очевидно выполнено.

Пусть равенство (1) доказано для числа m и докажем его для числа m + 1. Из равенства (2) индукционного предположения и свойства 3 биномиальных коэффициентов следует, что

= + =

По индукции равенство (1) доказано. n

Следствие 1. Число кортежей N и таких, что равно

. n

Следствие 2. Число кортежей N и таких, что равно

. n

Доказательство. Число кортежей N и таких, что равно числу кортежей N и таких, что . По следствию 1 искомое число равно . n

Следствие 3. Число всех мультимножеств A таких, что | A | = k, base (A) = = B равно .

Доказательство. Каждое мультимножество A такое, что | A | = k, base (A) = = B кодируется кортежем (n(b ),..., n(b ))Î N , где n(b )+...+n(b ) = k. По следствию 2 число таких кортежей равно . n

Определение.Мультимножество A называется подмультимножеством мультимножества B, пишем AÍ B, если base(A) является подмножеством base(B) и кратность любого элемента в мультимножестве A не превосходит его кратности в мультимножестве B. n

Теорема 2. Пусть A - мультимножество, base (A)={ }, n()= ,..., . Тогда число всех подмультимножеств мультимномножества A равно .

Доказательство. Каждое подмультимножество B мультимножества A кодируется кортежем N , где - кратность ,..., - кратность в мультимножестве B, ,..., . Искомое число равно числу таких кортежей и равно . n