Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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)!}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.