2

I've been trying to understand an example question in my textbook but after looking around the answer seems unclear to me.

The question:

"How many combinations/permutations of $8$ different rings can be put on $3$ different fingers? Both if the order matters and also if it does not."

My attempt, if order does not matter would be :

$8^3$

If the order does matter:

$8P3 = 8 \cdot 7 \cdot 6$

Is this the correct way to interpret such a question?

Some online resources seem to have varying and sometimes odd solutions such as this: $C(n+r -1, r-1)$

Any assistance in understanding if I'm heading to the correct interpretation would be helpful.

Edit

Note : More than $1$ ring can be put on each finger

JMP
  • 21,771
D3181
  • 191
  • 1
    Is more than one ring allowed to be on one finger? – Parcly Taxel Mar 26 '17 at 16:27
  • yes i will clarify it in the question, thanks for commenting :) – D3181 Mar 26 '17 at 16:31
  • Does it count if one or two fingers have no rings? That is, must every finger have at least 1 ring. – amWhy Mar 26 '17 at 16:31
  • The question states the rings are different...which im assuming means distinct. and im also assuming as it asks for all combinations it means that one or two fingers can be empty....however the question isnt terribly clear as shown in my post... – D3181 Mar 26 '17 at 16:35

3 Answers3

4

For order doesn't matter, each ring can be placed on one of $3$ fingers. This results in a unique string, for example $12323113$, which results in finger $1$ having rings $1,6,7$, finger $2$ has rings $2,4$ and finger $3$ has rings $3,5,8$.

This clearly groups each finger's rings as distinct, and gives $3^8$ strings.

$8^3$ is three rings onto $8$ fingers.

If order does matter, using $3^8\cdot8!$ doesn't work, for example in the above case there are only $3!2!3!=72$ permutations.

Instead, use stars and bars to give the number of available patterns as $\dbinom{10}{2}=45$.

To feed the fingers their rings, first arrange the rings into one of the $8!$ permutations, and feed from finger $1$ through to finger $3$. This ensures uniqueness, and gives the result as:

$$\binom{10}{2}\cdot8!=45\cdot40320=1814400$$

JMP
  • 21,771
  • This is a good answer but would you mind explaining a little something if it's ok. Where does the 8 factorial come from when you say : 3^8⋅8! . I understand the 3^8, but why do you multiply it again by (8!)? – D3181 Mar 26 '17 at 18:24
  • 1
    because the obvious next step is to say each position in the string can have a different ring, but this leads to over-counting as I explain, so the sentence is removing this possibility.@D3181 – JMP Mar 26 '17 at 18:35
  • Would you possibly be able to explain the stars and bars part that results in 45? As im confused as to how to attain that result? – D3181 Mar 26 '17 at 19:50
  • we find the numbers of arrangements of $********||$ - 8 stars, 2 bars, which gives us the number of ordered partitions into 3 parts. This is $\binom{10}{2}$. – JMP Mar 26 '17 at 19:53
  • so if we increase the number of fingers to 5 we would also increase the number of bars to 4? – D3181 Mar 26 '17 at 19:59
  • @D3181; yes, and increasing the number of rings to 9 means we need 9 stars. – JMP Mar 26 '17 at 20:02
  • great thanks so much for explaining! just one last question. Is The factorial of 10 chosen by the number of bars? I.E if i use 3 bars is it 10 over 3? resulting in it being (1097)/3 = 210 – D3181 Mar 26 '17 at 20:14
  • @D3181; it's $\binom{\text{stars+bars}}{\text{bars}}$ – JMP Mar 26 '17 at 20:15
  • but you use the bars as a factorial for the stars? Such that 10*9 / 2 = 45 such as in your answer? – D3181 Mar 26 '17 at 20:20
  • @D3181; well its $\dfrac{(s+b)!}{s!b!}$, which is the number of ways you can choose s or b objects from s+b objects. C(10,3)=1098/3=240 btw – JMP Mar 26 '17 at 20:34
  • ah perfect, thanks for the breakdown and taking the time to explain! – D3181 Mar 26 '17 at 20:37
  • Actually now i have calculated it out and is it odd that the total number of combinations when order doesent matter is smaller than the number of combinations when it does? E.G 3^8=6561 and when order matters the result was 1814400? Should the value of all possible ways with no order not be less than the ordered number? – D3181 Mar 26 '17 at 20:47
  • 1
    @D3181; no order means 123,132,213,231,312,321 are all the same – JMP Mar 26 '17 at 20:49
  • Ah fantastic thanks for explaining! You are a legend – D3181 Mar 26 '17 at 20:58
1

In how many ways can eight rings be placed on three fingers if the order in which the rings are placed on the fingers does not matter?

All that matters is which finger receives which ring. There are three choices of finger for each of the eight rings, so there are $3^8$ ways of placing rings on fingers.

In how many ways can eight rings be placed on three fingers if the order in which the rings are placed on the fingers matters?

We need to decide how many rings each finger receives. Let $x_k$ be the number of rings placed on the $k$th finger. Then $$x_1 + x_2 + x_3 = 8 \tag{1}$$ This is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of two addition signs in a row of eight ones. For instance, $$1 1 1 1 + 1 1 1 + 1$$ corresponds to the solution $x_1 = 4$, $x_2 = 3$, and $x_3 = 1$, while $$+ 1 1 1 1 + 1 1 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = x_3 = 4$. Thus, the number of solutions of equation 1 is the number of ways two addition signs can be inserted in a row of eight ones, which is $$\binom{8 + 2}{2} = \binom{10}{2}$$ since we must decide which two of the ten positions (for eight ones and two addition signs) will be filled with addition signs.

We have not yet accounted for the order of the rings on each finger. To do so, we arrange the eight rings in order, which can be done in $8!$ ways, then place them on the fingers from left to right and from base to tip.

Hence, the number of ways of eight rings on three fingers when the order in which the rings are placed matters is $$\binom{10}{2} \cdot 8!$$

N. F. Taussig
  • 76,571
  • You can't use stars and bars because the rings are distinct. So $x$ might have $r_1, r_2, r_3, r_4$, which is distinct from the situation where $x$ contains $r_1, r_5, r_6, r_7$. In both cases finger $x$ has four distinct rings, but the rings differ in each case. – amWhy Mar 26 '17 at 17:04
  • I haven't broached order. I am talking about the fact that there are 8 distinct rings to distribute. Stars and bars applies only when all 8 rings are indistinguishable. – amWhy Mar 26 '17 at 17:09
  • @JonMarkPerry The way I interpreted the question is that it matters which ring is on which finger and it also matters in which order the rings are placed on the fingers. – N. F. Taussig Mar 26 '17 at 17:09
  • 8 different rings usually means 8 different rings, aka, 8 distinct rings. – amWhy Mar 26 '17 at 17:11
  • @amWhy What I did was count how many ways the rings could be distributed to three fingers without taking into account the fact that the rings are distinct, then multiplied by the number of orders in which the rings can be arranged. See Andre Nicolas's answer to this question. – N. F. Taussig Mar 26 '17 at 17:14
  • 1
    We use two addition signs since we are placing the rings on three fingers. Notice that the number of addition signs is one less than the number of fingers receiving the rings. It does not depend on the number of rings. If we were distributing nine rings to three fingers, then we would have $$x_1 + x_2 + x_3 = 9$$ where $x_k$ is the number of rings placed on the $k$th finger. On the other hand, if we were placing eight rings on four fingers, we would have $$x_1 + x_2 + x_3 + x_4 = 8$$ since we need three addition signs to separate eight ones into four groups. – N. F. Taussig Mar 26 '17 at 19:47
-1

If you're like me the problem is finding a strategy.

And the strategy that figuring each ring has $3$ choices of fingers so there are $3^8$ ways to choose fingers for each ring, is a dead end as order matters and we can't straightforwardly multiply by any choice or permutation value for each finger as we don't know how many rings are on each finger.

We can choose to say each finger has $aPb = \frac {a!}{(a-b)!}$ where $a$ are the number of rings left, and $b$ are the number of rings on the finger:

Then the answer is $\sum_{k= 8,-1}^0 (8 P k)\sum_{j=0}^k(k P j)(k-j P k-j)$. Which seems intimidating but: $(k P j)(k-j P k-j) = \frac {k!}{(k-j)!}(k-j)! = k!$ and so $sum_{j=0}^k (k P j)(k-j P k-j) = \sum k! = (k+1)k! = (k+1)!$ and $\sum_{k= 8,-1}^0 (8 P k)\sum_{j=0}^k(k P j)(k-j P k-j) = \sum_{k = 0}^8 \frac{8!}{k!}*(k+1)! = 8! \sum_0^8 (k+1) = 8!\sum_{i=1}^9 i = 8!\frac{9*10}2 = 8!*45$.

But simpler way of thinking of it is that if all the rings were identical and there were $N$ ways to place $8$ things on $3$ fingers. And there are $8!$ ways to arrange the 8 rings. There would be $8!N$ ways to arrange 8 different rings.

There are two ways to solve $N$. You may put $a$= zero to $8$ rings on finger $1$ and you may put $b$ = 0 to $8-a$ on finger 2 and all the rest on finger 3. That is $\sum_{a=0}^8\sum_{b=0}^{8-a}1 = \sum_{a=0}^8 9-a = \sum{a=8,-1}^0 a+1 = \sum_{i=1}^9 i = \frac {9*10}2 = 45$.

Or: you need to divide $8$ onto three fingers. Put the on one after the other. There are nine points in time between $0$ and $8$ that you can put in a "go to next finger marker". Among the $0$ to $8$ ring and the marker there are 10 places to put a second marker. There are ${10 \choose 2} =\frac {10!}{2!8!} = \frac {10*9}n = 45$.

Either way there are $45*8!$ ways to do this.

==== old answer which was stream of thought with mistakes along the way below === it could be illuminating for thought process... or it could be frustrating as it takes a while to get the right answer =====

If order doesn't matter then each ring can go on any one finger is $3^8$ (not $8^3$) is correct.

But if order on the fingers matters (the emerald on the middle finger under the gold is different than the emerald on the middle finger over the gold) it's a different question.

One way: Arrange the rings in order that you will put them on. There are $8*7*6= \frac {8!}{(8-3)!}$ (is that what $8 P 3$ defined to be? I think so.) ways to arrange . Then each ring (in order) has a choice of three fingers to be placed on. So the answer is $8P3*3^8$.

==== Oh, F###; that's over counting ====

If diamond ring is 1 and we choose finger one and emerald is 2 and we choose finger two is the same as emerald is 1 and we choose finger two and diamond is 2 and we choose finger one.

Oh, well, I'm going to leave this up as foood for thought. but... it is a wrong answer.

=====

My first thought was the hardest. You can choose $a$ rings for the first finger and $b$ rings for the second and $8 - a -b$ for the third and so

$\sum_{a= 0}^8 (8Pa)\sum_{b=0}^{8-b}([8-b]Pb)*([8-b-a]!)$

Logic tells me that sum must add up to $8P3*3^8$ (EDIT: It doesn't) but ... I'd hate to actually work it out (EDIT: but I may have to... it seems like the correct answer still.).

(Actually my very first thought was order didn't matter and rings were all the same, so it'd be $\sum_{a=0}^8 \sum_{b=0}^{8-a} 1 = \sum_{a=0}^8 9-a = 9^2 - \frac{8*9}4= 45$).

====

Here's a second way. We are going to put all the rings on in order all the rings on the first finger first, then the rings on the second, and then the third.

There are $8!$ ways to arrange there rings and $\sum_{a=0}^8 \sum_{b=0}^{8-a} 1 = 45$ ways to place the two "breaks" on when we stop putting rings on one finger and start putting them on the other.

So $8!*45$. Is that right?

Anyone with time on his/her hands want to see if $\sum_{a= 0}^8 (8Pa)\sum_{b=0}^{8-b}([8-b]Pb)*([8-b-a]!) = 8!*45=8! {10 \choose 2}$?

fleablood
  • 124,253
  • This answer would probably benefit from you cleaning it up a bit (leaving out incorrect approaches and your own doubts about your results). – Bobson Dugnutt Mar 26 '17 at 17:49
  • 1
    Yeah, but I had to take some time out to shower, eat breakfast, etc. Interesting that I had never noticed that $n+1 \choose 2$ = $\sum_{i=0}^n i$ before. It makes perfect sense and stars and bars with n-1 stars and 2 bars is a perfect example where both are obviously the solution as is picking two numbere balls from $n+1$ by considering which is lower and how many are higher than it. Amazing that I never noticed. – fleablood Mar 26 '17 at 18:25
  • 1
    Ibn al-Banna developed the formula $$\binom{n}{2} = \sum_{k = 0}^{n - 1} k \tag{1}$$ by considering two-element subsets of a set with $n$ elements. Consider the set $S = {1, 2, 3, \ldots, n}$. The left hand side counts two element subsets of $S$. The right hand side of equation 1 counts two-element subsets of $S$ whose smallest element is $k$. There are $n - 1$ such subsets with smallest element $1$, $n - 2$ subsets with smallest element $2$, and so forth until we are left with one two-element subset with smallest element $n - 1$. Source: Victor J. Katz, A History of Mathematics. – N. F. Taussig Mar 26 '17 at 20:52
  • @fleablood That's the best math answer i've ever seen – John Rawls May 23 '17 at 16:34