Number of ways to color such that one color always leads

Question

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes colored blue should always be greater than the number of boxes colored red.All boxes have to be colored. What are the total number of distinct coloring possible.

Answer 1

I will list a particular colouring as a pair of blue and red, such as $(4,2)$ representing a colouring that has $4$ blue and $2$ red.

So you start with one box. It must be blue. $$(1,0)$$ The next box must also be blue. $$(2,0)$$ Since you have two more blue than red, the next one you do can be either. $$(3,0),(2,1)$$ For $n=4$, the valid combinations are $(4,0)$ and $(3,1)$. The only way to reach $(4,0)$ is from $(3,0)$. But you can reach $(3,1)$ from either previous set. $$(4,0),2(3,1)$$ For $n=5$ the valid combinations are $(5,0)$, $(4,1)$ and $(3,2)$. Like above, some of these can be reached in several ways, giving you $$1(5,0),3(4,1),2(3,2)$$ And you can continue this $$1(6,0),4(5,1),5(4,2)$$ $$1(7,0),5(6,1),9(5,2),5(4,3)$$ $$1(8,0),6(7,1),14(6,2),14(5,3)$$

A pattern has emerged. The ways to a valid pair $(b,r)$ is the sum of the ways to get to $(b-1,r)$ and $(b,r-1)$. In the case of $r = b+1$, it's just $(b,r-1)$. In the case of $(b,0)$ it's just $(b-1,0)$ since you can't have a negative $r$.

What this forms is version of Pascal's triangle but with everything to one side of the middle, and the middle itself, zeroed out. This is known at Catalan's triangle, and fortunately the sum of any diagonal in that table is given by a simple formula, $$\sum_{i=0}^n(n-i,i)=\binom{n}{\lfloor\frac{n}{2}\rfloor}$$

However this is for a zero index, so we just need a bit of an offset. $$\text{ways to colour}=\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$$