3
$\begingroup$

I am currently studying a photography course, and I have run into a bit of difficulty with one of my projects in relation to combinatorics. I have a key rack and there are 39 hooks on this key rack. I understand that to get the amount of combinations that could be produced with 39 keys, I would have to do 39! , but I want to get the amount of combinations with 38, 37, 36... 1 key(s) on top of that. The problem is that for one key, it would obviously be 39, as there are 39 hooks that it could go on to make it a different combination, but for two, there are 39 different hooks (so logic would declare 78 permutations) but there are also the different positions that the keys could be in relation to each other, so this number no longer seems correct.

Any help would be much appreciated.

$\endgroup$
1
$\begingroup$

I think the numbers you're looking for are the binomial coefficients (also colloquially known as the "choose coefficients" where I'm from). Binomial coefficients

For one key on a 39-hook rack you're right, there are 39 choices. For two keys however, there are a bit more than 78: place the first key on the first hook, and then there are 38 other choices for the second key. Now move the first key to the second hook - there are another 38 choices for the second key. And we can do that for all 39 hooks, so there are actually 39*38 choices. But! If the keys are interchangable (i.e. we don't distinguish between two keys, so if the first key is on hook one and the second key is on hook two we treat that the same as there being a key on hook one and a key on hook two) then we need to divide by the number of ways we can arrange the keys. So where we have two keys we need to divide by two and we get 39*38/2 = 39*19=741 ways of arranging two keys on 39 hooks.

In general then, we get that there are $\frac{39!}{(39-n)! \cdot n!}$ ways of arranging the keys.

If the keys can be distinguished then you get a slightly larger number of permutations given by $\frac{39!}{(39-n)!}$ where $n$ is your number of keys.

$\endgroup$
  • $\begingroup$ Exactly what I was looking for, thankyou $\endgroup$ – cjm Apr 24 '13 at 10:16
2
$\begingroup$

If you have $k$ keys there are $\frac{39!}{(39-k)!}$.

For the 1st key I have thirty nine different hooks I can put it on, for the next there are thirty eight and so on.

so for $k$ keys there are $39\times 38 \times 37\times \dotsm\times 39 - (k-1)$ different ways of placing my keys.

I can get rid of the dots by noticing that if I multiply by $(39-k)!$ I get $39!$ so it's easiest to write this as a fraction $\frac{39!}{(39-k)!}$.

If you actually want to calculate the number it's best to do it the long way ($39\times38\times\dotsm)$, as $39!$ is such a big number that most calculators won't calculate it accurately.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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