Creating my climbing wall

Question

[based on a true story]

I have here some climbing holds that I've made. There are two relevant parameters:

1. The angle on the top, and
2. The thickness, as shown.

Now it is definitely the case that $B_1$ is easier to hold than $S_1$. If we implement an easiness score for each hold — the smaller the number, the easier to grip — it is clear that the easiness score of $B_1$ $<$ easiness score of $S_1$. We will use the function $E(x)$ to denote the easiness score of a hold. Therefore, $E(B_1) < E(S_1)$.

Now, clearly $B_2$ is easier to hold than $S_2$, so we can say: $E(B_2) < E(S_2)$. We can also extend this to $B_3$ and $S_3$: $E(B_3) < E(S_3)$.

It is also the case that $B_1$ is easier to hold than $B_2$, which is easier to hold than $B_3$ — therefore, $E(B_1) < E(B_2) < E(B_3)$. Additionally, $E(S_1) < E(S_2) < E(S_3)$.

In general,

1. The thicker the hold, the easier it is to grip;
2. The more the hold slopes towards the wall, the easier it is to grip.

I want to arrange a course in which they go in order of increasing difficulty. There are 5 possible ways this could be done given the above constraints:

1. $B_1$, $B_2$, $B_3$, $S_1$, $S_2$, $S_3$
2. $B_1$, $B_2$, $S_1$, $B_3$, $S_2$, $S_3$
3. $B_1$, $S_1$, $B_2$, $B_3$, $S_2$, $S_3$
4. $B_1$, $B_2$, $S_1$, $S_2$, $B_3$, $S_3$
5. $B_1$, $S_1$, $B_2$, $S_2$, $B_3$, $S_3$

But, what if I have 4 different angles? Or 5 angles? What's the general number of ways of arranging the routes?

And, trickier perhaps, what if I have 3 different thicknesses ($S$, $M$, $L$) and 3 different angles? Or in general, $n$ different thicknesses and $m$ different angles?

Answer 1

To build your course from top to bottom, you can always choose the next available S or B (the lowest-numbered one remaining) provided that you never have more S's than B's on your wall.

You can visualise this as an $n\times n$ square grid where you have to go from the top-left $(0,0)$ corner to the bottom-right $(n,n)$ corner by travelling along the edges down or to the right only, whilst also staying on or below the diagonal of the square. Every downwards move is choosing the next hold to be a B, every move to the right means you choose an S hold. The number of paths to $(n,m)$ is then equal to the number of ways to build the wall with $n$ S-holds and $m$ B-holds. You can count the number of ways to do this just by filling in the numbers on the grid as follows:

 
 1  -  -  -  -  -
 1  1  -  -  -  -
 1  2  2  -  -  -
 1  3  5  5  -  -
 1  4  9 14 14  -
 1  5 14 28 42 42
 

Each entry is the sum of the number above it and the number to its left, where everything outside the triangle is considered zero.
For example, at three steps down and three to the right (i.e. fourth row and fourth column) there is the number $5$, the number of climbing walls with $3$ holds of each width.

Now we'd like a formula for these.

This is called the Catalan triangle: OEIS A008315
According to that page they have the formula $C(n,m) = \binom{n+m}{n}\frac{n-m+1}{n+1}$.

Proof of the formula:

For $n\ge m$ we have: $$C(n-1,m)+C(n,m-1) = \\ = \binom{n-1+m}{n-1}\frac{n-m}{n} + \binom{n+m-1}{n}\frac{n-m+2}{n+1}\\ = \frac{(n-1+m)!(n-m)}{n(n-1)!m!} + \frac{(n+m-1)!(n-m+2)}{(n+1)n!(m-1)!)}\\ = \frac{(n+m-1)!(n-m)}{n!m!} + \frac{(n+m-1)!(n-m+2)}{(n+1)!(m-1)!)}\\ = \frac{(n+m-1)!(n-m)(n+1)}{(n+1)!m!} + \frac{(n+m-1)!(n-m+2)m}{(n+1)!m!)}\\ = \frac{(n+m-1)!((n-m)(n+1)+(n-m+2)m)}{(n+1)!m!} \\ = \frac{(n+m-1)!(n^2-m^2+n+m)}{(n+1)!m!} \\ = \frac{(n+m-1)!(n+m)(n-m+1)}{(n+1)!m!} \\ = \frac{(n+m)!(n-m+1)}{(n+1)!m!}\\ = \binom{n+m}{n}\frac{n-m+1}{n+1}\\ = C(n,m)$$
Combine this with the fact that $C(n-1,n)=0$ and $C(n,0)=1$, this show that the formula follows the same rules we used to construct the numbers in the grid, so the formula must produce the same numbers.

For an equal number of S-holds and B-holds:

The numbers on the diagonal are the answers for when you have an equal number of S-holds as B-holds. Those numbers are the Catalan numbers: OEIS A000108
They have the formula $C(n,n)=\frac{(2n)!}{n!(n+1)!}$.

I don't know what you'd get if you generalise it to three or more thicknesses.