Lobb's Generalization of Catalan's Parenthesization Problem
Abstract:A. Lobb discovered an interesting generalization of Catalan's parenthesization problem, namely: Find the number L(n, m) of arrangements of n + m positive ones and n − m negative ones such that every partial sum is nonnegative, where 0 ≤ m ≤ n. This article uses Lobb's formula, L(n, m) = (2m + 1)/(n + m + 1) C(2n, n + m), where C is the usual binomial coefficient, to prove that L(n, m) is odd for all m if and only if either n = 0 or n is a Mersenne number. It follows that L(n, m) and the Catalan number Cn have the same parity. We also show that L(n, m) = C(2n, n − m) − C(2n, n − m − 1), so every Lobb number can be read from Pascal's triangle. In addition to other interesting combinatorial identities, we establish that every Catalan number C2n is the sum of n + 1 squares.
Document Type: Research Article
Publication date: 2009-03-01
More about this publication?
- The College Mathematics Journal is designed to enhance classroom learning and stimulate thinking regarding undergraduate mathematics. CMJ publishes articles, short Classroom Capsules, problems, solutions, media reviews and other pieces. All are aimed at the college mathematics curriculum with emphasis on topics taught in the first two years.
- Information for Authors
- Submit a Paper
- Subscribe to this Title
- Membership Information
- Information for Advertisers
- Terms & Conditions
- MAA Journals at ingentaconnect
- MAA Store
- Ingenta Connect is not responsible for the content or availability of external websites