0
$\begingroup$

For the string "aaaaaabbbbbb" (that's $12$ characters with $6$ a's and $6$ b's), let's say that I want to find the number of unique possible strings that have exactly 4 of the same characters as the given string and in the right place, exactly $4$ of the same characters that exist in the given string but they are in the wrong place (with respect to the given string), and the last $4$ characters can be any character from c to f (that is: c, d, e, or f) each. Also, we can only map any character to one of these conditions just once, and not more (Equivalent to saying the possibilities should not exceed 6 'a's or 6 'b's). For example, "abbaccdfbaba", "aebfbabfafab" are both different possibilities that match the given conditions. But "aaaaccaaaacd" does not meet the last condition.

Also, while it would be great to get an exact number as to how many different possibilities exist, I would really be satisfied with a "ball park" or the order of magnitude of the number of different combinations with some sort of justification. I predicted that it would be around $100$k, but two of my friends think it should be around $8$ million possibilities, so I would really like to settle this discrepancy more than anything.

Note: If you want to make an educated guess without any justification, that's also fine, please comment with your guess.

  • 0
    Yes, there will be no scenario where it maps uniquely to the original string but has more than 6 'a's or more than 6 'b's. My apologies for the poor choice of words in the question leading to the confusion.2012-11-16

1 Answers 1

1

Here is the exact number. Let any solution have, among the first $6$ positions, $i$ letters "a" and $j$ letters "b", then among the last $6$ positions it has $4-i$ letters "b" and $4-j$ letters "a". The numbers $6-i-j$ and $i+j-2$ of remaining positions must be non-negative, so $2\leq i+j\leq 6$, and because there are no more than $6$ letters each "a" and "b" available, $|i-j|\leq2$. Given such $i$ and $j$ there are $ \binom6{i,j,6-i-j}\binom6{4-i,4-j,i+j-2}\times4^4 $ solutions, where $4^4=256$ counts the possibilities of filling the remaining four positions with a word in $\{c,d,e,f\}$. So all in all there are $ 256\sum_{i,j=0 \atop 2\leq i+j\leq 6\text{ and }|i-j|\leq2}^4 \binom6{i,j,6-i-j}\binom6{4-i,4-j,i+j-2} =8140800 $ possibilities.