How many towers can you build such that a layer cannot have more blocks than the last one?

 Or in mathematical words:

How many possible combinations for $1 \le i_1 \le ... \le i_k \le n $?

This week's problem was inspired by a simple question from my discrete mathematics class. The original question the teacher asked was:

\[a_n = |(i_1,...,i_k) \in \mathbb{Z}^k :1 \le i_1 < ...<i_k \le n| \]

The answer to this question is $\binom{n}{k}$ since we are picking k many different numbers smaller than n. Afterwards a simple question came to my mind. What's $b_n$ such that:

\[b_n = |(i_1,...,i_k) \in \mathbb{Z}^k :1 \le i_1 \le ... \le i_k \le n| \]

The Visualization

If these notations seem a bit confusing there is another way to ask these questions. Let's say $a_n$ is the number of possible buildings with k many floors such that every floor  has at least 1 and at most n rooms and such that a floor must have less rooms than the one below it. And $b_n$ is the number of possible buildings with k many floors such that every floor  has at least 1 and at most n rooms and such that a floor can have at most as many rooms as the one below it.  So, $a_n$ is the number of possible card towers while $b_n$ is the possible towers built using small building blocks.You can visualize the possible buildings for $b_2$ where k=3 as:

The Initial Instinct

When you look at this question, it looks simple enough but if you try to fight it head on you'll realize that it gets very complicated. 

Let's try to calculate the number of possibilities such that there are no equal pairs. The answer is  $\binom{n}{k}$ like we did earlier.

Then it's time to calculate the number of possibilities such that there is only 1 pair of equal numbers. So we'll pick $\binom{n}{k-1}$ many different numbers and then, we'll pick one number to be the equal pair. So the answer for this sub question is $\binom{n}{k} \times \binom{k-1}{1}$. Seems easy enough.

But when we have to calculate other possibilities such as where there are 2 distinct pairs, where there 3 of the $i$'s which have the same value, where 3 of the i's have the same value and there is an extra pair etc etc it becomes a very long equation. While working on it, I asked my good friend Nevzat Akkaya if he had any ideas. He came up with a pretty elegant idea. So the credit goes to him.

The Solution

We know that there are $k-1$ many signs between the $i$'s when we try to order them. So instead of trying to calculate a formula where we decide how many $i$'s are gonna be equal, we decide how many signs will be "=" and how many of them will be "<". But in order to prove the question this way, first, we have to see:

-If we have n many numbers and we order them using only "<" and "=", then there is only one possible ordering. 

Well this is clear due to $\mathbb{Z}$ being a well ordered set.

Now let's say we have $x$ many distinct  numbers. Then we must have $x-1$ "<" signs and subsequently $(k-1)-(x-1)=k-x$ many "=" signs. How many orderings of these sign are possible? Well the answer is: $\frac{(k-1)!}{(x-1)! \times (k-x)!}$. 

When we have an ordering of signs, there is only 1 possible way to fill the slots up since there are $x-1$ many "<" signs and x many distinct numbers. The slots between the "=" signs already fill themselves up. 

We are assuming that $n \geq k$ (if not just let $\binom{n}{k}$s where $k >n$, equal to zero). Then the answer is:

 \[ \binom{n}{1} \times \frac{(k-1)!}{(1-1)! \times  (k-1)!} + \binom{n}{2} \times \frac{(k-1)!}{(2-1)! \times (k-2)!} + ... + \binom{n}{k} \times \frac{(k-1)!}{(k-1)! \times (k-k)!} \]

 \[= \sum_{i=1}^{k} \binom{n}{i} \frac{(k-1)!}{(i-1)! \times (k-i)!} \] 

We finially get the answer:

\[ \sum_{i=1}^{k} \binom{n}{i} \binom{k-1}{i-1}  \]