# An efficient method for computing the number of submultisets of size n, of a given multiset

There are a number of ways to describe this problem. I shall name a few.

Submultisets

Let $(M, f)$ be a multiset where $M = {x_1, ... x_k}, |M| = k$ and $f(x_i) = m_i$, i ranging from 0 to k inclusive. Find the number of submultisets $(S,g)$ of $(M,f)$ of size n, $|(S, g)| = n$.

Integer Partitions

Let $n, x_1, ... x_k, m_1, ... m_k \in \mathbb{N}$

Find the number of solutions of the equation:

$x_1 + x_2 + ... x_k = n$

such that $0 \le x_i \le m_i$, i of course ranging from 0 to k inclusive.

Unordered combinations of size n

Let a collection of objects M have k types of objects, where there are $m_i$ identical objects for each type, i from 0 to k inclusive. How many ways can I pick n elements from M, given the restriction that I cannot pick more than $m_i$ from each type?

Unless I've made a mistake somewhere, each of these problems should be identical.

In the ordinary undergrad combinatorics literature, there is a method for picking the number of ways to solve this, without the $m_i$ restrictions I mentioned (or at least $m_i \ge n$. That is call the multiset coefficient. There is also the number of ways of ordering all of the elements of M, provided you use all of them. That is called the multinomial coefficient. This, of course, uses only n elements from M, and does not include ordering.

The only solution I've come across, given the 5 measly hours I've researched the problem, was in Combinatorics and Graph Theory by Harris et. al, which mentions a crude method for counting the number of strings of length 4 of a given set of letters "Alma, Alabama". They enumerate 4 different patterns by hand, and use well known equations on those patterns. It works when n and k are small, but is inefficient otherwise.

Update

Sorry, I should have made my question a bit more explicit. I'm looking for an efficient method to do it by hand. The recurrence equations are helpful, but it's not quite what I was looking for.

I don't think there is a simple equation that provides the answers. A recurrence equation is likely to catch all of the cases, but may not be efficient for computing by hand. I don't think there is an efficient way to do this, if k is large and n is small. Or is there?

Update 2

Forgive me for bringing up the concept of a multiset. I thought it was in the standard literature. The size of a multiset $|(M, f)|$ is just the summation of the multiplicities $|(M, f)| = \sum_{i} f(x_i)$. It's not the same as the size of the support $|M|$. They are only equal when $f(x_i) = 1$ for all of the elements, just a regular set.

-
The generating function in my answer will help you do it by hand. Did you try using it? –  Aryabhata Sep 14 '10 at 17:45
Well.. I was looking at a problem where k = 7 as the motivation for this post. Expanding out 7 terms of the form (1 - x^(m_i+1)) would not be very efficient to do by hand. Maybe a graphing calculator would work, if this was on a test. Regardless, your solution is more elegant than alext87's. If you can give a bit more explanation (a proof?) as to how you solved the problem, I'll mark your answer as the "solution". –  Robin Hoode Sep 14 '10 at 18:11
if n is small, you don't have to expand out the whole thing, only the terms upto x^n. btw, perhaps you can edit your question to mention your case of k=7 and please also mention what the m_i are. Perhaps we can work out how the method will work for your case. For instance if all m_i are equal, there is an easy expansion. –  Aryabhata Sep 14 '10 at 18:17
@Moron: I was trying to stay general :( If there is no "efficient" solution, I'd rather not change my question. Although, so far, yours is looking like the most efficient. –  Robin Hoode Sep 14 '10 at 20:15

I don't really understand the description of the SubMultiset problem.

I think I do understand the description of the integer partition problem.

This can be solved by generating functions.

The number of solutions to

$x_1 + x_2 + \dots + x_k = n$ with $0 \le x_i \le m_i$ is the coefficient of $x^n$ in

$$(1+x+\dots+x^{m_1})(1+x+\dots+x^{m_2})\dots(1+x+\dots+x^{m_k})$$

$$= \frac{\prod_{i}^{k}(1-x^{m_i+1})}{(1-x)^{k}}$$

$$= (\sum_{j=0}^{\infty}{k+j-1 \choose j} x^j) \prod_{i}^{k}(1-x^{m_i+1})$$

-
I managed to convince myself of the first term when k = 2, and it generalizes easy enough for larger k. The second term follows from the first, but I'm not familiar with the third term. How does the summation of the x^j become the 1/(1 - x)^k ? –  Robin Hoode Sep 14 '10 at 20:00
@robinhoode: Binomial Theorem. ${k+j-1 \choose j}$ is another way of writing ${-k \choose j}(-1)^j$. –  whuber Sep 14 '10 at 20:46

Counting submultisets is the same as asking for the number of divisors of $\prod p_i^{m_i}$ (where the $p_i$ are distinct but otherwise arbitrary), so it's just $\prod(m_i+1)$.

-
Yes, but you're not counting the size of the submultiset. The size of a multiset is the summation of all the multiplicities of the elements in the set. That is $Sum_{i} f(x_i) = |(M, f)|$. –  Robin Hoode Sep 14 '10 at 19:56
Ah. In that case you want d_k(N) rather than just d(N). See, e.g., Glyn Harman's Prime-Detecting Sieves. –  Charles Sep 14 '10 at 20:07
Amazon search doesn't understand latex :( What page am I looking for? –  Robin Hoode Sep 14 '10 at 20:36
The first time it's mentioned is page xiii. His notation is actually $\tau_r(d)$, now that I look. –  Charles Sep 15 '10 at 0:20