1

Suppose we have $m+n$ symbols out which $m$ are identical and $n$ are distinct. It is required to find the number of permutations of these $m+n$ symbols such that no two identical symbols are together. I tried to solve it through the help of of a recurrence relation. .My reasoning as follows:

If $f(m,n)$ is the requisite no of permutations the following things are obvious : $$f(1,1)=2$$ $$f(1,n)=(n+1)!$$ and similar such base conditions. Now in the general case the first symbol can be either one among the $m$ identical symbols or it can be one of the $n$ different symbols .This means we have the following recurrence relation $$f(m,n)=n{f(m-1,n-1)+nf(m,n-1)}$$. In particular what is the value of $f(4,6)$

Is my reasoning and hence the above recurrence relation correct ?I would be greatly thankful for any help.

AgnostMystic
  • 1,654

1 Answers1

1

Yes, your recurrence relation looks correct. You need to specify that $f(1, 0) = 1$ in your base case, though.

As an aside, you might want to show that, in general, $$f(m, n) = \binom{n + 1}{m}\times n!$$

Hints for obtaining the general formula -

  1. In how many ways can you arrange $n$ distinct items?
  2. Note that arranging $n$ items creates $n + 1$ new spots (i.e. at the ends and between every two items). In how many ways can you choose $m$ spots?
  3. In how many ways can you arrange $m$ identical items?
iamwhoiam
  • 1,181
  • 10
  • 12
  • when we try to evaluate $f(2,1) $ it comes out to be $f(1,1)+f(2,0)=2+0=2 $ but a direct observation tells us that $f(2,1)=1 $ as in the $a,b,a$.So what is wrong with the recurrence relation.And please would u give some hint as to how we can derive the formula u mentioned for $f(m,n)$ – AgnostMystic Jul 26 '17 at 07:48
  • @sajjadveeri for the first question, please recheck your work. For the second, I've added hints. – iamwhoiam Jul 26 '17 at 08:36
  • Thank u i got it.. – AgnostMystic Jul 26 '17 at 14:24