nice!
On Tue, Sep 7, 2010 at 8:00 PM, Gene <gene.ress...@gmail.com> wrote:
> This is a nice problem. The trick is always defining the recurrence
> in an artful way.
>
> Here let E(L, e) be the number of bracket expressions of length m that
> are proper _except_ that there are e extra left brackets.
>
> So for L = 1 and 0 <= e <= n, we have
>
> E(1, e) = (e == 1) ? 1 : 0
>
> That is, the only unit length proper bracket expression possibly
> having extra left brackets is a single left bracket. It obviously has
> exactly 1 extra left bracket.
>
> Let S = { s1, s2, ... sk}
>
> E(L, e) = (L \in S) ? E(L - 1, e - 1) : // only exprs ending in left
> bracket
> E(L - 1, e - 1) + E(L - 1, e + 1) // exprs ending in left +
> ending in right bracket
>
> To make this complete, we need to add E(L, e) = 0 for any e < 0 or e >
> n because in these cases no proper bracket expression exists.
>
> Finally we get the answer: E(2n, 0)
>
> So for fun, let's suppose the set S is empty and we want to know the
> answer for the case n=3, which is L=6.
>
> We have
> e = 0 1 2 3
> L = 1: 0 1 0 0
> 2: 1 0 1 0
> 3: 0 2 0 1
> 4: 2 0 3 0
> 5: 0 5 0 3
> 6: 5 0 8 0
>
> The answer is E(6,0) = 5 corresponding to [[[]]], [[][]], [][[]], [[]]
> [], and [][][].
>
> I'll let you try some examples where S is non-empty.
>
> On Sep 7, 4:22 am, hari <harihari1...@gmail.com> wrote:
>> You are given:
>>
>> * a positive integer n,
>> * an integer k, 1<=k<=n,
>> * an increasing sequence of k integers 0 < s1 < s2 < ... < sk <=
>> 2n.
>>
>> What is the number of proper bracket expressions of length 2n with
>> opening brackets appearing in positions s1, s2,...,sk?
>> plz.. explain how to solve this problem
>>
>> thanks in advance
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
