# How to find the pattern?

I'm challenging myself to figure out the mathematical expression of the number of possible combinations for certain parameters, and frankly I have no idea how.

The rules are these:

Take numbers 1...n. Given m places, and with no repeated digits, how many combinations of those numbers can be made?

AKA

• 1 for n=1, m=1 --> 1
• 2 for n=2, m=1 --> 1, 2
• 2 for n=2, m=2 --> 12, 21
• 3 for n=3, m=1 --> 1,2,3
• 6 for n=3, m=2 --> 12,13,21,23,31,32
• 6 for n=3, m=3 --> 123,132,213,231,312,321

I cannot find a way to express the left hand value. Can you guide me in the steps to figuring this out?

-
The furthest I've gotten is that it's n + something, which seems trivial to me. –  Aerovistae May 9 '12 at 9:55
$P_m^n$. is what I am thinking. Permutations –  yiyi May 9 '12 at 9:57

Suppose you have to construct such a sequence of length $m$ using $n$ different objects (in your case, digits).

To create such a sequence, you can first pick any of the $n$ objects as the first entry of your sequence. Then you pick the second entry, but this time you only have $n-1$ choices remaining (since you're not allowed to use the same object twice). Next, you pick the third entry, and for this you have $n-2$ choices.

Continuing in this way, you would have a total of $$n(n-1)(n-2)\cdots (n-m+1)$$ choices (to see that you stop at the factor $n-m+1$, realize that you need a total of $m$ factors, one for each entry you have to pick).

So the answer is $$n(n-1)(n-2)\cdots (n-m+1)$$ which is sometimes written $P_{n,m}$ (or $P^n_m$ or ...). For those who prefer using the notation with factorials (personally, I do, but it's easier to see where the formula comes from without factorials), this is just $$\frac{n!}{(n-m)!}.$$ Wikipedia has an article on permutations, including the solution to your problem (at "There is also a weaker meaning").

-
Surely someone has already asked a question of this ilk, so I hesitate to ask again, but how does one make the jump from n(n-1)(n-2)...etc to n!/(n-m)! ? –  Aerovistae Jun 10 '12 at 1:17
Note that $n!/(n-m)! = \frac{n(n-1)(n-2)\cdots(n-m+1)(n-m)\cdots2\cdot1}{(n-m)(n-m-1)\cdots2\cdot1}$ and you can cancel all the terms in the denominator against terms in the numerator. What is left is exactly $n(n-1)(n-2)\cdots(n-m+1)$. –  Daan Michiels Jun 17 '12 at 18:28

I believe what you are looking for is

$P_m^n$

Permutations so far has hold.

The equations is $\frac{n!}{(n-k)!}$

where ! means factorial N is the set and K would be the size of the set that you select from the larger set N.

Or in your case $\frac{n!}{(n-m)!}$

-