# Number of distinct combination with duplicates from a fixed set of elements

I have a fixed set of $N$ elements

$$\{a_i\}, i = 1, \ldots, N$$

And I am looking for the number of distinct possible combinations of n items I can create from this list (allowing duplicates elements) such as:

$$\{a_{j_k}\}, 1 <= j_1 <= j_2 \ldots <= j_n <= N$$

For example, if we assume $N = 1$ and $n = 3$ then only combination is:

$$\{a_1,a_1,a_1\}$$

If $N = 2$ and $n = 3$ then all possible combinations are:

$$\{a_1,a_1,a_1\}$$ $$\{a_1,a_1,a_2\}$$ $$\{a_1,a_2,a_2\}$$ $$\{a_2,a_2,a_2\}$$

And answer is $4$.

etc...

Ideally I am looking for a closed form if one exists as I am looking to get some figures for large $n$ and $N$

The classical formula for this is $${N + n - 1 \choose n},$$ see for example here.

• it looks like exactly what i needed, thanks!! Aug 22, 2017 at 14:04

Is n typically larger than N? Or the other way around? Or we surely don't know?

If N > n it is very easy;

In each of the n positions we can place one item out of N. So in this case the answer is just N^n. This is obviously a very large number even for quite small n and N

• You are thinking with ordering, but the order doesn't matter. For $N=2$ and $n=3$, for example, you would get eight possible solutions, while OP listed four.
– Dirk
Aug 22, 2017 at 13:07