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.

  • $\begingroup$ I gave an answer which didn't fit the bill about "only ... once, not more". I'll delete it for now, but just say here that I don't exactly see what the extra restriction is saying... $\endgroup$ – coffeemath Nov 16 '12 at 6:47
  • $\begingroup$ Again, thank you for the solution you had provided earlier, it proved that the solution was in the 8M range, which was all I wanted to know. As for the condition, I think the best way to explain it is to show an example. I think this is the one you had provided earlier, "aaaaccaaaacd": This one meets the conditions that 4 are right, 4 are wrong, and 4 are chosen from {c,d,e,f}, but we have two extra 'a's there that weren't in the original string, so it's not a solution. I guess I can rephrase the last restriction as such: The possibilities should also not have any more than 6 'a's or 6 'b's. $\endgroup$ – hesson Nov 16 '12 at 6:53
  • $\begingroup$ AHA. So now it is to not exceed six a's or b's. I think that is a different question from the "condition" given in the original problem, and maybe you're really thinking about something other than "at most six a's and b's. Because if there are four mapping to efgh and at most 6 to each of a and b there are various possibilities, say 6 a 2 b, or 5 a 3 b, etc. $\endgroup$ – coffeemath Nov 16 '12 at 7:02
  • $\begingroup$ What I meant was that in the examples I provided in the original question, each character in the example string could be mapped to another character in the original string for which it meets the condition just once. However, that is not true for something like "aaaaccaaaacd" since if you try map each character in this example to a corresponding one in the original where it meets the condition, not all the mappings will be unique as with the examples I provided. Anyway, you can forget this condition. It is basically equivalent to saying that it cannot have more than 6 'a's or 6 'b's. $\endgroup$ – hesson Nov 16 '12 at 7:04
  • $\begingroup$ 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. $\endgroup$ – hesson Nov 16 '12 at 7:08

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.

| cite | improve this answer | |

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.