How was this formula arrived?

Question

If i need chose groups of $n$ elements of a $m$, where $m \geq n$, we can solve by this way:

Example:

I have $5$ players, and I want to make groups of $3$, how many can I do?

Then, there are 5 players ($m$) and each player can make groups with the other $4$ players, and each one of these $4$ players can make groups with the other $3$, then the result is: $5 * 4 * 3 = 60$

With an analysis, problem like this can be solved with:

$V^m_n = m(m - 1)(m -2) ...(m - n + 1)$

I have been looking for intuitive and / or logical demonstrations, I have not found any.

So, how can I get from $V^m_n = m(m - 1)(m -2) ...(m - n + 1)$, to:

$V^m_n = \frac{m!}{(m-n)!}$

I have also been trying, and I have deduced that when i use $V^m_n = m(m - 1)(m -2) ...(m - n + 1)$, the amount of binomials create are $(n - 1)$, that are (m - 1) (m - 2) up to (m - n + 1)

PD: The idea is to prove it, ignoring that the formula existed.

Answer 1

By definition $m! = m*(m-1)*(m-2)*.......*3*2*1$.

And by definition $(m-n)! = (m-n)*(m-n-1)*(m-n-2)*....... * 3*2 *1$.

So $\frac {m!}{(m-n)!} = $

$\frac {m*(m-1)*(m-2)*.......*3*2*1}{(m-n)*(m-n-1)*(m-n-2)*....... * 3*2 *1}=$

$\frac {m*(m-1)*(m-2)*...*(m-n+2)(m-n+1)(m-n)(m-n-1)(m-n-2)*....*3*2*1}{(m-n)*(m-n-1)*(m-n-2)*....... * 3*2 *1}=$

$\frac {m*(m-1)*(m-2)*...*(m-n+2)(m-n+1)\color{red}{(m-n)(m-n-1)(m-n-2)*....*3*2*1}}{\color{red}{(m-n)*(m-n-1)*(m-n-2)*....... * 3*2 *1}}=$

$m*(m-1)*(m-2)*...(m-n+2)(m-n+1)$.

Ex: $\frac {17!}{8!} = $

$\frac {17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1}{8*7*6*5*4*3*2*1}=$

$\frac {17*16*15*14*13*12*11*10*9*\color{red}{8*7*6*5*4*3*2*1}}{\color{red}{8*7*6*5*4*3*2*1}}= $

$17*16*15*14*13*12*11*10*9$.

....

In a similar vein if $k < n$ we can always know that $k!|n!$ and $\frac {n!}{k!} = (k+1)(k+2)*....*(n-1)*n$

And that $n! = k!*(k+1)(k+2)*....*(n-1)*n$.

These are all considered to be inherent.

Answer 2

Hint:

What can you multiply $m(m-1)(m-2)\cdot\ldots\cdot(m-n+1)$ with, to get $m!$? Now, multiply with that same quantity in the denominator.

---

Edit: You have $m$ elements to choose from, and you want to make a group consisting of $n$ elements, in how many ways can you do this? Look at the 1st element of this group, in how many ways can you choose this element? This amount is $m$. Having chosen the 1st element, there are $m-1$ elements to chose the 2nd element from, and so on ... You do this until you have chosen $n-1$th element, and now there are only $m-(n-1)=m-n+1$ elements left for the $n$th element. In total there are $$m(m-1)(m-2)\cdot\ldots\cdot (m-n+1)$$ ways.

Answer 3

I have $5$ players, and I want to make groups of $3$, how many can I do?

What you described is called permutation: choosing $3$ players out of $5$ players, when the order is important. (You can compare it with combination, when the order of selection is not important).

I have been looking for intuitive and / or logical demonstrations, I have not found any.

Call the players $A,B,C,D,E$.

We want to choose $3$ players from $5$ players in different orderings. You described the solution correctly:

Then, there are 5 players (m) and each player can make groups with the other 4 players, and each one of these 4 players can make groups with the other 3, then the result is: 5∗4∗3=60.

Now let's look at the process of selection from different perspective.

There are $5!$ ways to choose $5$ players from $5$ players in different orderings (it is called ordered permutation). For example, $ABCDE$; $ABCED$;$\ \cdots \ $; $EDCBA$. That is $5\cdot 4\cdot 3\cdot 2\cdot 1$.

We are interested in the first $3$ players we choose and do not care about the ordering of the rest $2$ players. That is: $$\begin{align}&ABC\color{red}{DE} \ \ (ABC\color{red}{ED})\\ &ABD\color{red}{CE} \ \ (ABD\color{red}{EC}) \\ &\qquad \qquad \vdots\\ &EDC\color{red}{AB} \ \ (EDC\color{red}{BA}) \end{align}\\$$ Note that once we choose $ABC$, it does not matter if the rest two are $DE$ or $ED$. Also note that all orderings of $5$ players were $5!$ and it is now divided by half (that is the orderings of the last two players, that is $2!$).

Hence, to find the (ordered) permutation of $5$ players chosen $3$ at a time is: $$P(5,3)=\frac{5!}{2!}=\frac{5!}{(5-3)!}.$$

Practice question: How many ways can you choose $7$ players out of $10$ players, when the order is important?