Proof of n-1 Parentheses for Full Parenthesization of n Elements
To demonstrate that fully parenthesizing an expression with n elements requires exactly n-1 pairs of parentheses, consider a recursive approach. For n=1, no parentheses are needed. For n>1, expressions are formed by combining two subexpressions:
package main
import (
"fmt"
"strings"
)
func generateExprs(n int) []string {
if n == 1 {
return []string{"x"}
}
var exprs []string
for k := 1; k < n; k++ {
left := generateExprs(k)
right := generateExprs(n - k)
for _, l := range left {
for _, r := range right {
exprs = append(exprs, fmt.Sprintf("(%s+%s)", l, r))
}
}
}
return exprs
}
func countParens(s string) int {
pairs := 0
for _, ch := range s {
if ch == '(' {
pairs++
}
}
return pairs
}
func main() {
n := 4
expressions := generateExprs(n)
for _, expr := range expressions {
fmt.Println(expr)
}
fmt.Printf("Total expressions: %d\n", len(expressions))
fmt.Printf("Parentheses pairs per expression: %d\n", countParens(expressions[0]))
}
This implementation generates all possible parenthesizations for n elements. The recursive decomposition shows that each combination step adds one pair of parentheses. For n elements, the base case (n=1) requires 0 pairs, while each additional element adds exactly one pair through the combination process, resulting in n-1 total pairs.
The algorithm produces $C_{n-1}$ valid expressions (Catalan number), each containnig exactly n-1 parentheses pairs. This confirms that full parenthesization of n elements requires precisely n-1 parentheses pairs regardless of expression structure.
