Let p_n be the number of ways to arrange n pairs of parentheses such that they are correctly matched. Show ...?

This is the Catalan number's sequence; p(1) = 1 should be obvious, as the only possibility is "()". As for n > 1, consider a valid sequence of n pairs of parenthesis; it must start with "(", now find the matching parenthesis ")"; you'll get something like:

(...)[rest of the sequence, may be empty]

The number os pairs in the sequence's initial segment may be any number 1 ≤ k ≤ n (in the former, you have ()(...); in the latter, the sequence is of the type (...)) but, each k labels a set that is part of a partition of the set of admissible sequences and the number of sequences in each of these sets is:

p(k)p(n−k), 1 ≤ k ≤ n

These sets are also disjoint, so the total number of admissible sequences of n pairs is:

p(n) = ∑[k = 1,n]p(k)p(n−k)

CM Punk Ezekiel Jackson Hart Dynasty Sarita Abyss Christian terrific promo had to be The Miz outsmarting Shawn Michaels WQ1- With all the dream fits how can Morrison no longer be important eventer? Morrison vs Shamus Morrison vs Jericho Morrison vs part Morrison vs Orton WQ 2- Draft has made uncooked into the terrific style WWE has to furnish, Smackdown would be happy with Jack Swagger, Christian, Undertaker and CM Punk together with his promptly part Society top-rated the way. i'm unhappy Batista is leaving WWE nonetheless, by no means observed that coming by way of a mile WQ3- Ted Dibiase staying on uncooked grow to be vast dissatisfied, with Jericho, part,Shamus with the aid of fact the ideal heels, he's particularly lots will stay as gentle card wrestler for now. uncertain what plans WWE inventive writers has in save for him ):