A price makes 10 up ticks and 10 down ticks in some order, starting at 0. How many of the C(20, 10) orderings keep the price at or above 0 after every tick? Name the sequence and give the number.

A price makes 10 up ticks and 10 down ticks in some order, starting at 0. How many of the C(20, 10) orderings keep the price at or above 0 after every tick? Name the sequence and give the number.

Approach: Count the bad paths instead. Reflect the path after the first time it reaches minus one and show the reflection is a bijection onto a set of unconstrained paths with a different tick balance.

16796. The count is the Catalan number C_10 = C(20, 10)/11 = 184756/11 = 16796. To see it, note the total number of lattice path orderings is C(20, 10) = 184756, and a bad path touches -1 at some first time. Reflect every step after that first touch, swapping ups and downs. This reflection principle is a bijection between bad paths and unrestricted paths with 9 ups and 11 downs, of which there are C(20, 9) = 167960, so the good count is 184756 - 167960 = 16796. The general formula is C_n = C(2n, n) - C(2n, n-1) = C(2n, n)/(n+1). The same number counts balanced bracket strings, binary trees on 11 leaves and the ways to triangulate a 12-gon, which is why it appears whenever an inventory or a stack has to stay non-negative.

Follow-up: What is the count if the price must stay strictly above 0 after the first tick, and how does the ballot theorem generalise this to unequal tick counts?

Key concepts: catalan number, reflection principle, lattice path, bijection.