Is the number of different combinations possible?

Question

You are given the number of places as m and the number of digits as n. You must fill in these m spaces so that each digit is displayed at least once.

for instance

Given m as 4 and n as 3, you have 4 places and 3 digits. Now for this total possible number of combinations 36.

Let's look at a simple example:

m = 3 and n = 2 (a, b suppose), then the possible combinations are:

aba aab abb bab bba baa

Thus, only 6 combinations are possible. Is there any formula for this because I need to find the possible number of combinations?

Answer 1

Answer the question

The answer is n!S(m,n) , where S the Stirling number of the second kind .

For example, for m=4, n=3 , n!=6 , S(4,3)=6 , so n!S(m,n)=36 , which is the expected answer.

Why is this formula?

Stirling numbers of the second kind S(m,n) count the number of ways to split the set of elements m into n nonempty subsets. So, for this question S(m,n) count the number of ways to split m into groups n , each of which corresponds to a digit. After the section, we must assign one digit to each group, and there is n! ways to do it. Therefore, the answer is n!S(m,n) .