1
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ Why didn't i see that! Thanks a lot. $\endgroup$ Commented Dec 7, 2014 at 16:07
  • $\begingroup$ @user155768 You're welcome. $\endgroup$ Commented Dec 7, 2014 at 16:07

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.