grandes-ecoles 2021 Q28

grandes-ecoles · France · centrale-maths1__official Permutations & Arrangements Combinatorial Proof or Identity Derivation
Assume $k$ is even and $\vec{\imath} \in \mathcal{B}_{k}$ is a cycle passing through $\frac{k}{2}+1$ distinct vertices (i.e. $|\vec{\imath}| = \frac{k}{2}+1$). We traverse the edges of $\vec{\imath}$ in order. To each edge of $\vec{\imath}$ we associate an opening parenthesis if this edge appears for the first time and a closing parenthesis if it appears for the second time.
Count the cycles $\vec{\imath}$ that correspond to a fixed well-parenthesized word.
Assume $k$ is even and $\vec{\imath} \in \mathcal{B}_{k}$ is a cycle passing through $\frac{k}{2}+1$ distinct vertices (i.e. $|\vec{\imath}| = \frac{k}{2}+1$). We traverse the edges of $\vec{\imath}$ in order. To each edge of $\vec{\imath}$ we associate an opening parenthesis if this edge appears for the first time and a closing parenthesis if it appears for the second time.

Count the cycles $\vec{\imath}$ that correspond to a fixed well-parenthesized word.