Combination with repetitions removing the permutated sequences

Question

Is there any closed form expression for the number of combinations with repetitions removing the permutated sequences (for a given number of spaces (N1) and a given number of possible numbers (N2))?

For example in this case there are 5 spaces and 4 possible numbers:

1 1 1 1 1 -> Valid
1 1 1 1 2 -> Valid
1 2 1 1 1 -> This one is a repetition of the above line
1 2 4 4 1 -> Valid
1 4 1 4 2 -> This one is a repetition of the above line
1 2 3 4 4 -> Valid 

It does not matter getting the sequence 1 2 4 4 1 or de 1 4 1 4 2 in the end. But it is not possible to get both of them.

Is this a known problem? Is there any elegant algorithm or closed form expression to solve this problem?

Thanks!

Answer 1

Suppose there are $r$ spaces, and $n$ possible numbers $1,...,n$.

Counting only one instance for sequences which permute to each other, each sequence of $r$ terms, where each term is one of the numbers $1,..,n$, corresponds to a solution $(x_1,...,x_n)$ of the equation $$x_1 + \cdots + x_n = r$$ where each $x_k$ is a nonnegative integer representing the multiplicity of the number $k$ in the given sequence.

By the stars-and-bars formula, the desired count is $$\binom{r+n-1}{n-1}$$ For example, if $r=5,\;n=4$, we get a count of $$\binom{5+4-1}{4-1}=\binom{8}{3}=56$$ To illustrate the correspondence, note that the sequence $$(1,1,3,4,4)$$ is the unique sequence (up to a permutation of the terms) with

• $2$ terms equal to $1$
• $0$ terms equal to $2$
• $1$ term equal to $3$
• $2$ terms equal to $4$

corresponding to the solution $$(x_1,x_2,x_3,x_4)=(2,0,1,2)$$ of the equation $$x_1+x_2 + x_3 + x_4 = 5$$

Answer 2

To present another derivation of the answer already given, you are looking for the
Number of words, of length $r$, with characters taken from the alphabet $\{1,2,\cdots,n \}$, net of (non considering) the permutations.

Now, not considering the permutations is clearly equivalent to arrange the characters "alphabetically", i.e. in a non-decreasing (or non-increasing) order.

So you are looking for
Number of non-decreasing words, of length $r$, with characters taken from the alphabet $\{1,2,\cdots,n \}$.
That is the number of solutions to $$ 1 \le \;x_{\,1} \le x_{\,2} \le \cdots \le x_{\,r} \le n $$ or $$ 0 \le \;y_{\,1} \le y_{\,2} \le \cdots \le y_{\,r} \le n - 1 $$

Put $$ z_{\,1} = y_{\,1} \quad z_{\,2} = y_{\,2} - y_{\,1} \quad \cdots \quad z_{\,r} = y_{\,r} - y_{\,r - 1} $$ and you get $$ 0 \le \;z_{\,1} \le z_{\,1} + z_{\,2} \le \cdots \le z_{\,1} + z_{\,2} + \cdots + z_{\,r} \le n - 1 $$ i.e. $$ \left\{ \matrix{ 0 \le z_{\,j} \le n - 1\quad \left| {\;1 \le j \le r} \right. \hfill \cr z_{\,1} + z_{\,2} + \cdots + z_{\,r} \le n - 1\quad \hfill \cr} \right. $$ which is the same as $$ \left\{ \matrix{ 0 \le z_{\,j} \le n - 1\quad \left| {\;1 \le j \le r + 1} \right. \hfill \cr z_{\,1} + z_{\,2} + \cdots + z_{\,r} + z_{\,r + 1} = n - 1\quad \hfill \cr} \right. $$ and that is the number of weak compositions of $n-1$ into exactly $r+1$ parts. $$ \left( \matrix{ n - 1 + r \cr n - 1 \cr} \right) = \left( \matrix{ n - 1 + r \cr r \cr} \right) $$