For example, with elements a,b,c,d
, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses):
(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))
The first example multiplies a*b
, then multiplies that product by c
, then multiplies that product by d
. The second example first multiplies b*c
, then multiplies that product by a
, then multiplies that product by d
.
Any valid parenthesized expression of 2n elements will necessarily have n (
and n )
with the property that, reading from left to right, there are always at least as many (
as )
.
I know that for n numbers, the number of ways is the (n-1)th Catalan number. But how does one accurately generate all the resulting groupings?
Thanks
(As an aside: There are over 160 equivalent formulations of this problem, all based on different combinatorial objects enumerated by the Catalan Numbers. For the most up to date list of these, see Richard Stanley's Catalan Addendum.)
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…