Counting the number of configurations without permutations

Question

Let $\mathcal{A} = \left\{1,2,...,M\right\}$, and let $N>M$ be some natural number.

A configuration is a string of $N$ numbers where each of the $N$ numbers takes values in $\mathcal{A}$. For example, if $\mathcal{A} = \left\{1,2\right\}$, and $N=3$, then possible configurations are \begin{align} 1,1,1\\ 1,1,2 \end{align} and so on. I want to count the number of possible configurations excluding permutations. So, for the previous example, this number is equal to $4$, where the possible configurations are (of course, we can choose other permuted configurations) \begin{align} 1,1,1\\ 1,1,2\\ 1,2,2\\ 2,2,2 \end{align}

Answer 1

You are essentially asking for non-decreasing sequences of $N$ elements of $\mathcal{A}$, i.e., numbers in the range $1 \ldots M$. Say a configuration is $a_1, a_2, \ldots, a_N$, take: \begin{align} x_0 &= a_1 - 1 \\ x_1 &= a_2 - a_1 \\ &\vdots \\ x_N &= a_N - a_{N - 1} \\ X_{N + 1} &= M - a_n \end{align} Note that this way $x_0 + \ldots + x_{N + 1} = M - 1$. Your restrictions mean that each $x_k \ge 0$, and that (by the stars and bars argument) has just: $$ \binom{(N + 2) + (M - 1) - 1}{M - 1} = \binom{M + N}{M - 1} $$ solutions.

Answer 2

consider $A=\{1,2,...m\}$ and $N$. Then suppose a string consists of $X_{i}$ copies of $1\leq i \leq m$. Then the number of strings is in one to one correspondence with solutions to $$X_{1}+X_{2}+...+X_{m}=N.$$