Let's define $C$ as the number of possible sequences of length $N$ we can form using symbols $A_i$ from an alphabet $A = \{A_1,\ldots , A_M\}.$
To my knowledge, we always have $C = M^{N+1}$.
For example, the total count of numbers containing 3 digits that we can form using decimal digits is $10^4$ = 1000, which would be the cardinality of $\{000, 001, … 999\}$.
Or for example, the total count of binary numbers we can build with 3 bits is $2^4$ = 16, which would be the cardinality of $\{000, …, 111\}$.
Separately, I have read that the multinomial coefficient ${n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ can be understood as:
The number of distinct ways to permute a multiset of n elements, and $k_i$ are the multiplicities of each of the distinct elements.
How are these problems and quantities related? Are they one and the same for some choices of $k_i$, $n$, $N$ and $M$?
Put another way, can $C$ be written as a multnomial coefficient?
Best Answer
Suppose that you have an alphabet $A=\{a_1,\ldots,a_m\}$ of $m$ symbols. Using this alphabet we can form $m^n$ distinct sequences of length $n$ (not $m^{n+1}$). Now suppose that $$k_1+k_2+\ldots+k_m=n\;;$$ the multinomial coefficient $\binom{n}{k_1,\ldots,k_m}$ is the number of distinct sequences of length $n$ that contain exactly $k_1$ instances of $a_1$, $k_2$ instances of $a_2$, and so on. The relationship between the two is then straightforward:
$$m^n=\sum_{\substack{\langle k_1,\ldots,k_m\rangle\in\Bbb N^m\\k_1+\ldots+k_m=n}}\binom{n}{k_1,\ldots,k_m}\;:$$
the sum is taken over all possible counts of the different symbols.