Skip to content

Balanced strings using two kinds of brackets

Question

Consider strings of length 2n2n built from the four symbols (, ), {, }. Call a string proper if every bracket is closed by a bracket of the same kind and the brackets are correctly nested, so (){} and {()} are proper while {(}) and ((} are not. Let PnP_n denote the number of proper strings of length 2n2n. Find P5P_5.

Short answer

13441344. Ignoring the bracket type, a proper string is a balanced parenthesisation, counted by the Catalan number CnC_n; then each of the nn matched pairs independently chooses its type. So Pn=2nCnP_n=2^nC_n and P5=32⋅42=1344P_5=32\cdot42=1344.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free