Balanced strings using two kinds of brackets
Question
Consider strings of length 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 denote the number of proper strings of length . Find .
Short answer
. Ignoring the bracket type, a proper string is a balanced parenthesisation, counted by the Catalan number ; then each of the matched pairs independently chooses its type. So and .
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 solutionLessons behind this question
- Counting and Combinatorics
- Sample Spaces, Events, and the Probability Axioms
- Conditional Probability, Total Probability, and Bayes' Rule
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