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've been trying to solve this problem and I am kind of struggling with it and with other combinatorics problems. Could you check and see if i did it right?

Given problem:

  1. How many ways can 5 rings be placed 4 fingers if the rings are all the same?
  2. What if the rings are all distinct?

Answer:

  1. I used the formula $\tbinom{n+k-1} k$ because I assumed that the question is saying that order doesn't matter and repetition is allowed; therefore I',m using that formula. By using that formula I have come up with this: $\tbinom{5+4-1}4 = \tbinom 8 4=\tfrac {8!}{4!(8-4)!}$

  2. Since the rings are distinct (meaning different), i used $n^k$ to compute it: $5^4$

Could anyone check if I did it right or wrong? If wrong, could you correct it and tell me how to solve it correctly? Because I really want to understand what I did wrong and know how to solve it correctly. Thank you so much.

share|improve this question
    
Welcome to MSE! It really helps readability to format questions using MathJax (see FAQ). Excellent showing your work! Regards –  Amzoti Jun 16 '13 at 19:36
1  
Please learn to use your shift key. It will go a long way toward convincing people to spend their valuable time helping you if you show you're not too lazy to capitalize. –  dfeuer Jun 16 '13 at 19:43
    
Where are these formulae coming from? Can you give an intuitive explanation of why they apply? –  dfeuer Jun 16 '13 at 19:46
    
did i do it right? am i on the right track?? –  ammie Jun 16 '13 at 19:49
    
If you thing there are $\tbinom{n+k-1}k$ ways to put a total of exactly $n$ rings on $k$ fingers, then you are wrong. For $k=1$, this yields $n$, which is wrong. –  dfeuer Jun 16 '13 at 20:10

3 Answers 3

This sounds like the classic stars and bars problem, and your formula is wrong.

You need to put 5 rings on 4 fingers. So consider a string of 5 R's and 3 bars, giving you such a picture. E.g. RRR||R|R says put $(3,0,1,1)$ rings on fingers $(1,2,3,4)$. It's easy to convince yourself there is an exact correspondence between such strings and arrangements that you are seeking. So it's enough to count the number of such strings.

But in such a string, there are $n=5$ places for R and $k-1=3$ places for bars, and picking either all stars or all bars should be enough (because all other places will be filled by the other symbol). Since there is a total of $n+k-1 = 8$ positions, there is a total of $$ \binom{n+k-1}{n} = \binom{8}{5} = \frac{8!}{5!\cdot 3!} = 56 $$ such strings.

Alternatively, picking bars, you get $$ \binom{n+k-1}{k-1} = \binom{8}{3} = \frac{8!}{5!\cdot 3!} = 56 $$

as well.

share|improve this answer
    
Excellent explanation. –  dfeuer Jun 16 '13 at 22:10

In the first case, if you are assuming all five rings are worn, you're close; you just mixed up your $n=4$ and $k= 5$. For the first: we can look at this as the number of ways to sum 4 non-negative integers to equal $5$: $$\underbrace{f_1 + f_2 + f_3 + f_4}_{n = 4\;\text{fingers}} = \underbrace{5}_{5\; \text{rings}}$$ where the $f$'s stand for fingers (four of them), and the 5 is the number of rings. This gives us: $$\binom{4 + 5 -1}{5} = \binom{8}{5} = \dfrac{8!}{5!3!} = \dfrac{8\cdot 7\cdot 6}{3\cdot 2 \cdot 1} = 56\;\;\text{combinations}$$

In the second case, there is no assumptions being made by your method: counting every possible way of wearing no ring, one ring...5 rings, on any one or more fingers gives us $5^4$ ways of wearing distinct rings, or no ring at all.

If you want to require that all rings be worn, as in case one, then we multiply the result of $(1)$ by $k! = 5!$, which gives all permutations of the rings, as they are distinct, and can thus be rearranged: that gives us $$(5!)\binom{4 + 5 -1}{5} = (5!)\binom{8}{5} = (5!)\dfrac{8!}{5!3!} = (5!)\dfrac{8\cdot 7\cdot 6}{3\cdot 2 \cdot 1} = (5!)56\;\;$$

share|improve this answer
    
@ammie Does this help you? –  amWhy Jun 17 '13 at 1:18
1  
+ Looks to me too like @Amzoti. –  Babak S. Jun 22 '13 at 4:59

By the stars-and-bars approach, the solution for part 1 is $n+k-1\choose n$. For the second part note that different ring orders per finger may produce different outcomes. This is accounted for by simply multiplying the part 1 result with $n!$ (write down that stras-and-bars again and note that the stars can be permuted arbitrarily.


The number $\lim_{n\to\infty} n!{n+k-1\choose k}$ might be called Liberace constant.

share|improve this answer
    
You're using $n$ and $k$ interchangebly here. Look at the difference between your two binomials. –  amWhy Jun 16 '13 at 21:24
    
Huh. I didn't realize different orders on one finger were to be considered different. Silly me. –  dfeuer Jun 16 '13 at 22:11
    
Shouldn't this goes to infinity? –  ablmf Jun 17 '13 at 1:14

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.