3
$\begingroup$

I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are.

For example if the string is of length ten as $w = aabbbaabba$, the total number of permutations will be

$\qquad \displaystyle \frac{|w|}{|w|_a! \cdot |w|_b!} = \frac{10!}{5!\cdot 5!}$

Now had the string been of distinct characters, say $w'=abcdefghij$, I would have found the permutations by this algorithm :

for i = 1 to |w|
  w = rotate(w)
w = rotate(w)
return w.head + rotate(w.tail)

Can some one throw new ideas on this - how to find the number of permutations for a string having repeated characters? Is there any other mathematical/scientific name of for what I am trying to do?

$\endgroup$
  • $\begingroup$ I edited your post to be more legible. Please check whether I kept your meaning. In particular: 1) What is the "type" of a permutation? 2) Do you want the number of all permutations, or do you want to list them? Your algorithm does neither. $\endgroup$ – Raphael Jun 22 '12 at 9:15
5
$\begingroup$

The total number of (different) permutations of strings with $n_i$ characters of type $i$ is given by $$\frac{(\sum_i n_i)!}{\prod_i n_i!}.$$ In other words, if the length of the string is $n=n_1 + n_2 +...$, you have $\frac{n!}{n_1!n_2!n_3!\ldots}$ different permutations. Note that the formula fits your simple case.

Why is this formula correct?

Because $n!$ is the number of permutations. But some permutations give the same string (e.g., aa rotated is still aa). Then we need to "remove" all the permutations that give the same string. For a given string, for each letter $i$, there are $n_i$ permutations that are identical to the string we started with. So (for each possible letter $i$) we divide by this number to get the final result.

$\endgroup$
  • 1
    $\begingroup$ i agree this is the formula.Imeant the algorithm to generate it. $\endgroup$ – softy Jun 22 '12 at 17:42
  • $\begingroup$ @softy: You have the formula. Is the implied algorithm not good enough? Please edit your question to ask what you really want. $\endgroup$ – Raphael Jun 23 '12 at 15:15
  • $\begingroup$ @Raphael, I think he/she looks for some sort of dynamic programming like what we use in finding binomial coefficient, actually this formula, simply raises stackoverflow, also it's too slow (because of number of multiplications and big division). $\endgroup$ – user742 Jun 23 '12 at 21:23
1
$\begingroup$

Do you know the urn problem? You usually consider two kinds of marbles (i.e. $n=2$), which gives rise to the binomial coefficient $\binom{N}{k}$ as the number of sequences of length $N$ with $k$ marbles of one kind (and $N-k$ of the other), if you draw with replacement.

You do the same with $n$ kinds of marbles. There is a natural extension to the binomial coefficient, namely the multinomial coefficient $\binom{N}{k_1\ \dots\ k_n}$ as the number of sequences of length $N$ with $k_1$ marbles of kind one, ...


If you want to understand why those are correct, I suggest you start with the binomial coefficient; the multinomial coefficient works similarly.

We have

$\qquad \displaystyle \binom{N}{k} = \frac{N!}{k!\cdot (N-k)!}$

by definition. $N!$ is the number of all permutations of $N$ marbles, that is if they are all distinguishable. Now we have $k$ black marbles (and $N-k$ white marbles), we can not distinguish. So we have to count all permutations that put the white black (and white) marbles in the exact same spots as one. We count every such permutation $k! \cdot (N-k)!$ times -- to see this, number the marbles, fix a distribution of black and white marbles and calculate the number of ways you can place the numbers -- so we have to divide by this number.


If your problem is to compute the multinomial coefficient, you can reduce this to computing the binomial coefficient, e.g. by

$\qquad \displaystyle \binom{n}{k} = \prod_{i=1}^k \frac{n-(k-i)}{i}$,

with this formula:

$\qquad \displaystyle \binom{N}{k_1\ \dots\ k_n} = \prod_{i=1}^m \binom{\sum_{j=1}^i k_j}{k_i}$.

$\endgroup$
  • $\begingroup$ Seems he looks for an algorithm which could calculate multinomial coefficient. $\endgroup$ – user742 Jun 23 '12 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.