# 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!! Commented 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
Commented Aug 22, 2017 at 13:07

I am not so sure that the provided answer is what you are looking for. Let’s assume that we have 4 different numbers. The number of combinations is then 4! = 24. Now let’s assume that the number 1 and 2 really are the same. We now get 12 different sets. Now assume that 1 and 3 are also the same and we obtain 4 different sets. It appears intuitively that a set of 4 numbers with 2 repeats amounts to 12 sets and a set of 4 numbers with 3 repeats corresponds with 4 sets. Again without proof the number of combinations with one repeated element is N!/n! where N is the number of numbers and n is the number of repeats. As an example 4 numbers and 2 repeats equates to 12; 4 numbers with 3 repeats equates to 4. This is for instance the case when looking for how many different bridge hands have the 4-4-3-2 combination (=12, 4 numbers 2 repeats) or how many different bridge hands have the 4-3-3–3 combination (=4, 4 numbers 3 repeats). For further explanation about this see https://www.occasionalenthusiast.com/bridge-hand-probability-analysis/