Number of Different Combination Possible?

5
votes

You are given number of places as m and number of digits as n. You have to fill those m places in such a way that each digit appears at least one time.

For example

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

Lets take a simple example:

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

aba aab abb bab bba baa

Thus 6 combinations are possible only. Is there Any Formula for this because I am required to find the possible number of combinations?

1
mathcombinationspermutation
This question appears to be off-topic because it is about mathematics rather than programming. – Paul R
I can smell some DP here. Possibly some recursive function can solve this. – user3345047

1 Answers

1
votes

Answer to the question

The answer is n!S(m,n), where S is Stirling numbers 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 this formula?

Stirling numbers of the second kind S(m,n) count the number of ways to partition a set of m elements into n nonempty subsets. So for this question, S(m,n) count the number of ways to partition m places into n groups, each group corresponding to a digit. After the partition, we should designate one digit to each group, and there are n! ways to do this. Therefore, the answer is n!S(m,n).