# And Now for the Legal Formula

So, did you come up with a working rule to describe the pattern we looked at last time? Here’s what I came up with:

As we saw last time, the “root” of the tree diagram (the first column) shows $$\mathtt{_{4}P_1}$$, which is the number of permutations of 1 card chosen from 4. The first and second columns combined show $$\mathtt{_{4}P_2}$$, the number of permutations of 2 cards chosen from 4. So, to determine $$\mathtt{_{n}P_r}$$, according to this pattern, we start with $$\mathtt{n}$$ and then multiply $$\mathtt{(n-1)(n-2)}$$ and so on until we reach $$\mathtt{n-(r-1)}$$.

The number of permutations of, say, 3 items chosen from 5, then, would be $\mathtt{_{5}P_3=5\cdot (5-1)(5-2)=60}$

This is a nice rule that works every time for permutations of $$\mathtt{r}$$ things chosen from $$\mathtt{n}$$ things. It can even be represented a little more ‘mathily’ as $\mathtt{_{n}P_r=\prod_{k=0}^{r-1}(n-k)}$

So let’s move on to the “legal” formula for $$\mathtt{_{n}P_r}$$. A quick sidebar on notation, though, which we’ll need in a moment.

When we count the number of permutations at the end of a tree diagram, what we get is actually $$\mathtt{_{n}P_n}$$. In our example, that’s $$\mathtt{_{4}P_4}$$. The way we write this amount is with an exclamation mark: $$\mathtt{n!}$$, or, in our case, $$\mathtt{4!}$$ What $$\mathtt{4!}$$ means is $$\mathtt{4\times(4-1)\times(4-2)\times(4-3)}$$ according to our rule above, or just $$\mathtt{4\times3\times2\times1}$$. And $$\mathtt{3!}$$ is $$\mathtt{3\times(3-1)\times(3-2)}$$, or just $$\mathtt{3\times2\times1}$$.

In general, we can say that $$\mathtt{n!=n\times(n-1)!}$$ So, for example, $$\mathtt{4!=4\times3!}$$ etc. And since this means that $$\mathtt{1!=1\times(1-1)!}$$, that means that $$\mathtt{0!=1}$$.

So, for the tree diagram, $$\mathtt{_{4}P_4}$$ means multiplying all the way to the right by $$\mathtt{n!}$$. But if we’re interested in the number of arrangements of $$\mathtt{r}$$ cards chosen from $$\mathtt{n}$$ cards, then we need to come back to the left by $$\mathtt{(n-r)!}$$ And since moving right is multiplying, moving left is dividing.

4
4 × 3
4 × 3 × 2
4 × 3 × 2 × 1
÷ (4 – 1)!
÷ (4 – 2)!
÷ (4 – 3)!
÷ (4 – 4)!

The division we need is not immediately obvious, but if you study the tree diagram above, I think it’ll make sense. This gives us, finally, the “legal” formula for the number of permutations of $$\mathtt{r}$$ items from $$\mathtt{n}$$ items: $\mathtt{_{n}P_r=\frac{n!}{(n-r)!}}$