Given a set S of m unique numbers, n slots are to be filled using those m numbers. What are the number of ways to do it, given the following constraints:
- A particular number from those m numbers should always be present in atleast one of the slots, and that number x will be given.
- Any number can be picked any number of times, i.e., repetition is allowed in the slots.
- Two ways are different if atleast one of the slots differ.
Example:
S = {2, 4, 6}, So, m = 3. Given, n = 4 and x = 2.
Here, x = 2, so in all of the ways, 2 will be present in atleast one of the slots.
Few of the possible ways to fill the given n slots are:
[2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 4, 4], [2, 2, 2, 6]
I have found a pattern to solve this using the number of times x is repeated in the slots, like in the given example it can be repeated 1, 2, 3 or 4 times, and for each number of times, we can count the number of possible permutations for other remaining numbers in S but this process is too lengthy. Is there any shorter way to do it?
Suppose $x$ occurs exactly once. Then the number of possibilities is $$\binom{n}{1}(m-1)^{n-1}$$ If $x$ occurs twice, then the possibilities are $$\binom{n}{2}(m-1)^{n-2}$$ etc. Thus the total number is $$\sum_{k=1}^{n}{\binom{n}{k}(m-1)^{n-k}}$$ By the binomial theorem, this is the same as $$((m-1)+1)^n-\binom{n}{0}(m-1)^n=m^n-(m-1)^{n}$$ It is perhaps easier to see it this way: There are $m^n$ possibilities, and there are $(m-1)^n$ configurations with no slot having $x$. So the answer is $$m^n-(m-1)^n$$