Count permutations of N A's and B's

Question

Given N "A"s and N "B"s. We need to arrange them such that if A is on left of B then our solution increase by +1 and also we need to maintain that at every point the number of A's must be greater than or equal to number of B's.

Now we need to count such permutations of these 2*N alphabets such that solution is equal to K every time.

Example : Say N=4 and K=2 then here answer is 6.

6 possible ways are :

ABAAABBB
AABBAABB
AABAABBB
AAABABBB
AAABBABB
AAABBBAB

My approach : I am having O(N*K) approach to solve this problem by doing brute type solution.

Make a function say F(last,Acount,K) and then check if we can place A or B their satisfying the conditions.But problem is N and K can be large .

So how to solve this problem

Answer 1

Now that there's a spoiler, let me expand on my comment.

Given a string with n ('s and n )'s, append a ). Exactly one of its n + 1 rotations ending in ) begins with a length-2n parenthesized expression. This is one way to prove the Catalan formula

C(n) = (2n choose n) / (n + 1).

For this problem, we want to count only the parenthesized expressions that have k occurrences of (). The number of ordered partitions of n elements into k nonempty parts is (n - 1) choose (k - 1), by choosing k - 1 positions out of n - 1 to insert part boundaries. By partitioning n + 1 into k nonempty parts also, we can count the number of length-(2n + 1) strings that begin with (, end with ), and have n ('s and n + 1 )'s and k ()'s as

((n - 1) choose (k - 1)) (n choose (k - 1)).

Of these strings, exactly k rotations result in strings of the same form, hence the division by k to get the number that are parenthesized properly. (There is no rotational symmetry because if k > 1 then k fails to divide n or n + 1.) The final answer is

((n - 1) choose (k - 1)) (n choose (k - 1)) / k.

To compute the binomial coefficients quickly, cache the factorials and their inverses modulo the modulus up to the maximum value of n.

Answer 2

Short answer: Narayana numbers is what you need.

I've spent whole saturday researching your problem. Thanks for an interesting question :) Here I would like to tell you my steps to solve it if you are interested.

You said that you can brute force the problem for a small inputs. For an algorithmic problems this ofthen might give you such an insight for better solution (e.g. if you find out some relations and guess the generating function). So I did brute force too (with dynamic programming aproach) and looked at given numbers. First time I wrote it to my output file wrong way (for every K for all N one after another in one column) so I didn't find some beatiful relations. That's why I didn't find answer that time and spent some more to get better reccurent function.
Then I tried to deduce it to nonreccurent function but failed (I think because it wasn't the best one possible). However doing this I found relations like Pascal triangle has (kind of symmetry) and then wrote numbers sequence to the output file in a triangle way.
It looked like very nice sequence so I just googled some of its numbers and found links to Narayana numbers.
Then I tried to deduce nonreccurent formula with no success again (now I could check its correctness because the sequence formula is already knonwn) :) So this time I don't know exactly how Narayana numbers' formula is given although the formula seems simple and small but you can search more if you are interested. I wish I go deep more but I'm afraid of spending the whole holidays for it :)

Here my brute force solution #1 and better reccurent solution #2. And here the outputs I've got in a triangle way (word wrap makes it ugly so be careful). Also, thanks DavidEisenstat for pointing the right way in comment to your question. I checked that link but didn't go further googling to find a solution. Although that would be the shortest path to the answer your question.

UPDATE I didn't provide implementation of fast calculation of combinations. There're different ways to do this which you can simply find in the internet including its implementations. The complexity of calculations would be O(N) so you will pass the execution time bounds you have. Or if you need to answer the query (with different N and K) multiple times, you can precalculate factorial for every number from 1 to N modulo (1e6 + 9) and then use them to calculate combinations with O(1).