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} \]

You have given essential data for us. about Abacus Online Classes It is excellent and good for everyone. Keep posting always. I am very thankful to you.

ReplyDeleteVery well written article. It was an awesome article to read. Complete rich content and fully informative. I totally Loved it.Singapore bar Model Strategy

ReplyDeleteVery well written article. It was an awesome article to read. Complete rich content and fully informative. I totally Loved it.scholerships in uk

ReplyDeleteNowadays kids spend too much time in front of televisions and computers but are still unaware of what’s happening in the world. They watch cartoons on the television and play games on their mobile phone or computers. You need to solve practical equations to learn maths. You can't learn math without practice. Nowdays you can contact online websites and applications for better learning. For example SmileTutor is the leading home tuition agency for parents and students looking for home tutors. Our services are 100% free and we pride ourselves on successfully matching our clients with the most suitable and qualified tutors. Keep Sharing!

ReplyDeleteThanks for your post. It's very helpful post for us. You can also visit Assignment Help Chicago for more information. I would like to thanks for sharing this article here.

ReplyDelete