UGC NET CSE | June 2016 | Part 2 | Question: 25

Question

In how many ways can the string $A \cap B - A \cap B -A$ be fully paranthesized to yield an infix expression?

• A. 15
• B. 14
• C. 13
• D. 12

Comments

Is it (2)14??

---

yes but how

Answer 1

Actually there is a formula
No of ways we can parenthesise n operands(like in matrix multiplication,arithmetic exp )=
                                    Catalan No(n-1)=$1/(n)*\binom{2(n-1)}{(n-1))}$

Here n=5 So no of way would be Catalan No(4)=$1/(5)*\binom{8}{4}$=14

Comments

n means total occurences of A and B right ?

---

Yes N means total ocurance of any operand in the expression

---

1/5 * (84) how to solve

---

formula is 1/N * ^2(N-1)C_(N-1)

where N is number of operands

=1/5 * ⁸C₄

Answer 2

formula is 1/N * 2(N-1)C(N-1)

where N is number of operands

=1/5 * 8C4
=14

Answer 3

answer is 14 that is 2 option.

Comments

chhavi can u explain it how 14 is answer....actually i need clear view not expert view

---

Either of the four operators can be the outermost one, so there are four cases to consider. If the first operator is the outermost one, then we need to compute the number of ways to fully parenthesize B - An B - A. Here there are 5 possibilities: 1 in which the "n" symbol is the outermost operator and 2 with each of the " - " symbols as the outermost operator. If the second operator in our original expression is the outermost one, then the only choice is in the parenthesization of the second of its operands, and there are 2 possibilities. Thus there are a total 7 ways to parenthesize this expression if either of the first two operators are the outermost one. By symmetry there are another 7 if the outermost operator is one of the last two. Therefore the answer to the problem is 14. 

---

Chhavi gupta. I like you how u explained.