1
$\begingroup$

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\}$$

And answer is one.

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$

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ it looks like exactly what i needed, thanks!! $\endgroup$
    – Vincent
    Aug 22, 2017 at 14:04
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Dirk
    Aug 22, 2017 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.