How to find unique multisets of n naturals of a given domain and their numbers?

Question

Let's say I have numbers each taken in a set $A$ of $n$ consecutive naturals, I ask myself : how can I found what are all the unique multisets, which could be created with $k$ elements of this set $A$?

For example I've got $A=[1,2,\dots,499]$. If I wanted to create unique multiset of 3 elements, I would search all the multisets $\{a,b,c\}$ such as $a\leq b\leq c$ and then have all the unique multisets. As such for each elements $a$ there is $499-(a-1)=500-a$ possibilities for $b$ and $500-b$ possibilities for $c$. Unfortunately I'm stumped here and can't find the number of possible combination, as I didn't do any maths for years. I know that I should have some kind of product, but I don't know how to find the product anymore.

So first, I would like to know if I am right in my original assumption, or if I am looking in the wrong direction. Second I would like to approach that as if I were doing an homework, as I would like to understand the logic behind it: What would be the formula to give the numbers of multisets of $k$ elements from a set $A$ of $n$ consecutive naturals?

P.S. I'm totally new to math.SE, as such, I'm not sure I tagged the post appropriately.

Answer 1

Hint: If $O_i$ is the number of occurrences of $i$ in the multiset, the tuple $(O_1, O_2, \dots, O_n)$ uniquely identifies the multiset. What constraint can you write down with the $O_i$, if the multiset has exactly $k$ elements?

Ok, to elaborate.

The number of multisets of size $k$ is equal to the number of non-negative integral solutions to the equation

$$O_1 + O_2 + \dots + O_n = k$$

Since the stars and bars method was already mentioned, here is a derivation of the formula using a more general approach, which is one of the main building blocks of analytic number theory: Generating Functions.

The number of solutions to the above equation is same as the coefficient of $x^k$ in

$$(1 + x + x^2 + x^3 + \dots )(1+x + x^2 + x^3 + \dots) \dots (1+ x + x^2 + x^3 + \dots) \ \text{repeated} \ n \ \text{times} \ \text{(why?)}$$

The above is same as

$$ \frac{1}{(1-x)^n} = (1-x)^{-n}$$

as $$ (1 + x + x^3 + x^3 + \dots) = \frac{1}{1-x}$$

Now we apply binomial theorem, (which is also valid for negative exponents)

The coefficient of $x^k$ is $$-1^{k}\ \frac{-n(-n-1)(-n-2)\dots(-n-(k-1))}{k!} = \frac{n(n+1)(n+2)\dots(n+k-1)}{k!}$$

$$= \frac{(n-1)!n(n+1)(n+2)\dots(n+k-1)}{(n-1)!k!}= {n+k-1 \choose k} $$

Answer 2

For a three-item multiset, the easiest approach is to start by picking $b$. As you say, there are $500-b$ choices for $c$. Similar logic says there are $b$ choices for $a$. Multiplying gives the number of choices for a given $b$. Now just sum over $b$. So you have $$\sum_{b=1}^{499} (500-b)b$$

For a larger set $A$, just change 499 to the largest number in $A$. For larger numbers of elements, you can make the formula have an upper limit of $n$ instead of 499. This will give you the number of 4 element multisets with the upper element $n$. Now you can sum over $n$ from 1 to the largest number in $A$. This gets tedious with increasing $k$, but maybe you can find a pattern.

We could have followed the strategy in the second paragraph to get the 3 element sets, but the symmetry around the middle element made it a bit easier. We would have started by saying there are $n$ one element multisets out of $n$. Then there are $\sum_{i=1}^{n} i=\frac{n(n+1)}{2}$ two element multisets out of $n$ and $$\sum_{i=1}^n \frac{i(i+1)}{2}=\frac{n(n+1)(2n+1)}{12}+\frac{n(n+1)}{4}$$ three element multisets. This looks different, but agrees with the prior result.

Added: For the general case, see the section "Multiset coefficients" in Wikipedia's Mulitset

Answer 3

Often a combinatorial counting problem is solved elegantly by relating it to something one already knows how to count.

Let's imagine a fly crawling from one corner of a grid to another (seriously, bear with me and we'll make it back to multisets shortly!). The fly's walk is efficient in that each step is either up or to the right. So if it goes from say $(0,0)$ to $(m,p)$, then the fly will take in all $p$-steps up and $m$-steps to the right. The challenge is to calculate how many possible such paths there are. Each path can be considered an arrangement of steps up and steps to the right, with a known number of each.

Here's a way to map your counting of $k$-multisets taken from some set $A$ of $n$ items and recast it as a question about how many paths there are for the fly to take. Consider the horizontal lines of the grid as being labeled by the items in set $A$, so (careful about the fence posts) there are $p = n-1$ vertical edges along the grid. Consider the number of a particular item in set $A$ as being the number of horizontal steps along its respective line. Since there will be $k$ entries in total for our multiset, this means $m = k$ horizontal edges across any path (and across the grid as a whole).

Put those ideas together and you'll have a recipe for counting the $k$-multisets from $A$.

If you actually wanted to list said multisets, it's more of a programming problem, but I think it would be fair game to discuss the algorithm to produce such a list.

Answer 4

In parallel to Moron's hint, I'd suggest looking into the "stars and bars" technique, which is explained well in this answer by Ben Alpert (or here's an answer of mine explaining it).