Let the problem be represented as f(i,j) for i A's and jB's. Amir represented it correctly as: f(i,j) = f(i,j-1) + f(j,i-1)
Lets try another representation: Let t(i,j) is the number of strings of length i+j with iA's and jB's in any order. Hence, t(i, j) = (i+j)Ci Now some valid strings for our problem would be: "A"<t(n-2,0)>"A""B...ntimes", where <t(n-2,0)> is a string counted as valid by t(n-2,0) Or "A"<t(n-2,1)>"A""B...n-1times", <t(n-2,1)> is a string counted as valid by t(n-2,1) Hence, *f(n,n) = t(n-2,0) + t(n-2,1) + t(n-2,2)+.......+t(n-2,n-1)* * * Adding these terms should give you the answer. Hope this helps Cheers Nikhil Jindal Delhi College of Engineering On Thu, Aug 5, 2010 at 9:56 PM, Ashish Goel <[email protected]> wrote: > can u explain how is this number reached at? > > (2n)!/((n+1)!(n!)) > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Thu, Aug 5, 2010 at 12:53 PM, umesh kewat <[email protected]> wrote: > >> Calculate the number of string can be formed by this formula in one >> statement.. >> >> for cross check the result is >> >> 2N!/((N+1)! * N!).... where is number of A or B in string >> >> >> >> >> On Thu, Aug 5, 2010 at 8:54 AM, Ashish Goel <[email protected]> wrote: >> >>> >>>> >>>> void dyckWords(int index, int open, int close) >>>> { >>>> static int dyck=0; >>>> if (index == 2 *n) >>>> { >>>> printf("%s\n", out); >>>> return ; >>>> } >>>> >>>> out[index] = '('; //or A >>>> if ((open + 1) <= n && open >= close) >>>> >>>> >>>> >>>> >>>> >>>> >>>> { >>>> dyckWords(index + 1, open + 1, close); >>>> } >>>> out[index] = ')';//or B >>>> >>>> if ((close + 1) <= n && open >= close) >>>> { >>>> dyckWords(index + 1, open, close + 1); >>>> >>>> >>>> >>>> } >>>> } >>>> >>>> Best Regards >>>> Ashish Goel >>>> "Think positive and find fuel in failure" >>>> +919985813081 >>>> +919966006652 >>>> >>>> >>>> On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari < >>>> [email protected]> wrote: >>>> >>>>> @ashish: AAA is the prefix of the string and it is valid as a prefix >>>>> and it's only used for strings with length >= 6 (where it is a valid >>>>> prefix) >>>>> actually only dp[i][j] where i==j counts the number of such strings and >>>>> otherwise there is no string where i!=j and it that case dp[i][j] counts >>>>> the >>>>> number of valid prefixes for string >>>>> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As >>>>> & Bs are the same >>>>> the logic behind n/2 is that if the length of the string is n this >>>>> means that it has n/2 As and n/2 Bs (n must be even) >>>>> the dp for n=4 doesn't look like that! this is how it looks (i just >>>>> compiled the code and checked values of dp): >>>>> 1 0 0 >>>>> 1 1 0 >>>>> 1 2 2 >>>>> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2 >>>>> >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]<algogeeks%[email protected]> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards >> >> Umesh kewat >> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
