Kenneth Rosen Edition 6th Exercise 6.1 Example 8 (Page No. 400)

Question

Find a recurrence relation for Cn  the number of ways to parenthesize the product of n+1 numbers , x0*x1*x2.......*xn , to specify the order of multiplication. For example C3 = 5 because there are five ways to parenthesize x0*x1*x2*.....*xn to determine the order of multiplication.

Comments

its T(n) = $\sum_{i=1}^{n-1}T(i).T(n-i)$

---

you can relate here ..just some base conditions are different 

https://gateoverflow.in/897/gate2003-6

---

https://brilliant.org/wiki/catalan-numbers/

---

how catalan numbers

here it is given C₅=5

not getting this comment

---

srestha its catalan no but base condition is change ... her for n we have to use n-1 in formula then we will get correct order of multiplication

---

how C₅=5?

---

i think he wrote something wrong it should be 14 ..for c5

---

its C3 typing mistake sorry.

---

@ pankaj_vlr , in this article i m not getting how they proved C_n = ²ⁿC_n/n+1. Plz explain.

---

1. https://math.stackexchange.com/questions/337842/simplifying-catalan-number-recurrence-relation

2. https://course.ccs.neu.edu/cs1800/17F/Honors/catalan.pdf

P.S: If not able to understand, then I will try to prove it.

---

https://brilliant.org/wiki/catalan-numbers/  in this article i m stuck on this " which number of sequences are a₁,a₂ , ...." like what these a's represent here.

---

It means how many ways are there to arrange them in a sequence $a_{1} + a_{2} + a_{3} + ...........................+ a_{k}$ such that there partial sum satisfy $\sum_{k = 1}^{2n} a_{k} \geqslant 0$ for $1\leqslant k\leqslant 2n$

---

thnx

Answer 1

 sonam vyas 

what is initial condition T(0) AND T(1)??

Comments

if there a only 1 no , only 1 way to parenthesize it ..(itself)