Total number of possible sub sequence with given condition

Question

Given a sequence of two letters A and B find the total number of possible sub sequences where number of letter A is two times the number of letter B without changing the order.

For example consider the sequence AAAABBAAAA Now the possible sub sequences with given conditions can be AAB BAA AAAABB BBAAAA AAABBA AABBAA and ABBAAA.

Some insights on how to approach this problem would be great, with or without the solution. Also, I often come across these kind of problems where there's a bunch of permutations involved and you've to try them all to figure out the solution. Is there any specific approach for such questions? Any book you can recommend which can help me get better at solving such problem?

Answer 1

You ought to follow a algorithmic approach. Start off with the condition and and analyse the cases possible.

In your case the condition is No. of A's = 2 * No. of B's

So, B,s count in original string = 2;

Now if the string has > 4 A's you can have all cases otherwise you may have to reject cases that are not possible

(1 B, 2 A),(2 B, 4 A)                    ---- Similar approach needs to be followed for general case identification

so for the above two cases

case 1 : (1 B, 2 A)

no of permutations (p1) = fact(3)/fact (2) --- division by fact 2 to nullify the arrangement of identical A's

case 2 : (2 B, 4 A)

no of permutations (p2) = fact(6)/(fact(2)*fact(4))  --- division by fact to nullify arrangement of identical A's and B's

Now adding the answer form the two cases the final answer is

        total no of permutations = p1 + p2

                                 = 3 + 15 = 18

Hope this helps in general first you should always formulate the problem in to sections and parts and then find subparts along the way.