1
$\begingroup$

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?

  • 0
    $P_m^n$. is what I am thinking. Permutations2012-05-09

2 Answers 2

2

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").

  • 0
    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)$.2012-06-17
2

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)!}$