Arrangements and Combinations · Catalan Numbers: Introduction

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Problem. Two candidates, A and B, participated in the elections. The ballot box contained exactly \(n\) votes for A and exactly \(n\) votes for B. All \(2n\) ballots are sequentially removed from the box. Let \(V(n)\) be the number of ways to remove the ballots in such an order that at any point in time, A has at least as many votes as B. For example, \(V(3)=5\): \[\text{ABABAB, ABBAAB, AABBAB, AABABB, AAABBB.}\] What is \(V(4)\)?

4 points