Combinatorics

Question

The number of ways in which 4 person each rolling a single dice once can have total of 17???

Plz explain....

The answer is 104 ways,

Comments

https://gateoverflow.in/123727/isi-2004-miii Please refer 

---

Thanks..

---

But by this method still I'm getting 80 only

But answer is 104..plz explain where I'm going wrong

---

You are not considering some of the duplicates. please check the answer. Someone should verify whether any mistakes are there in my answer.

Answer 1

Solving it using stars and bars method,

let x1,x2,x3 and x4 be their scores when rolling. 

we need x1+x2+x3+x4 = 17 ($1\leq Xi \leq 6$)

since they have minimum value 1, remaining 13 have to be scored as, 

x1'+x2'+x3'+x4' = 13 (Xi' = Xi-1)

N1 = number of ways = c(13+4-1 ,13) = c(16,3) = 560 . 

Now we have to subtract the number of ways in which atleast one of Xi $\geq$ 7 .

assuming x1 as 7 , since it is already having minimum 1, we will assume x1'=6 . If we split the remaining among 4 now, any split will be invalid as x1 is already invalid. 

x1'+x2'+x4'+x4' = 7 (since x1' is already a 6)

Number of ways of splitting 7 among all 4 = C(7+4-1,7) = C(10,3) = 120

similarly same case can come for x2', x3' and x4' . which will make it a total of , 

N2 = 4*120 = 480.  

Now we have some duplicate cases  , such as,

1.when we fix x1'=6 and we split and if we give x2'=6

2. when we fix  x2'=6 and we split and give x1'=6. 

 here case 1 and case2 are same. i.e., we have to subtract all cases from N2 where two of the Xi get value more than 6. which can be done in , 

x1'+x2'+x3'+x4' = 1 (since two have now value 6)

ways =  C(1+4-1,1) = C(4,1) = 4.

we can choose C(4,2) such duplicate pairs gives a total of 

N3= C(4,2)*4 = 24.

Total number of ways = N1-(N2-N3) = 560 - (480-24) = 104  and hence the answer. 

Answer 2

x1 + x2 + x3 + x4 = 17 ...eqn(1) with constraints 1≤ x1 ≤6 , 1≤ x2 ≤6 , 1≤ x3 ≤6, 1≤ x4 ≤6

All xi's are greater than equal to 1. Hence the eqn(1) becomes,

y1 + y2 + y3 + y4 = 13

So, number of solutions = $\binom{13+4-1}{13} = \binom{16}{13} = \binom{16}{3}$

Now, consider the following cases :

Case 1 : x1 $\geq$ 7,1 ≤ x2 ≤ 6 , 1 ≤ x3 ≤ 6, 1 ≤ x4 ≤ 6 ($\because$ we need to subtract those cases in which xi $\geq$ 7 has been considered a solution)

So, eqn(1) will become

k1 + k2 + k3 + k4 = 17 - 3 - 7

k1 + k2 + k3 + k4 = 7

and we'll have $\binom{4}{1}$ such cases for each one of xi

So, number of solutions = $\binom{4}{1} * \binom{7+4-1}{7}$ = $4*\binom{10}{7}$

Case 2 : Using principle of inclusion and exclusion, we'll need to add those cases which got subtracted twice. Imagine a Venn diagram with 4 circles.

x1 $\geq$ 7, x2 $\geq$ 7, 1 ≤ x3 ≤ 6, 1 ≤ x4 ≤ 6 and there will be $\binom{4}{2}$ such cases (selecting 2 xi's out of 4)

eqn(1) becomes

z1 + z2 + z3 + z4 = 17 - 2 - 14

z1 + z2 + z3 + z4 = 1

So, number of solutions = $\binom{4+1-1}{1}$ =$\binom{4}{1}$

Case 3 :

x1 $\geq$ 7, x2 $\geq$ 7, x3 $\geq$ 7, 1 ≤ x4 ≤ 6 and $\binom{4}{3}$ such cases

eqn(1) becomes

p1 + p2 + p3 + p4 = 17 - 7 - 7 - 7 - 1

p1 + p2 + p3 + p4 = -5

So we can see, the inner part of the 4-variable Venn diagram has no solutions in common.

So, we have total solutions as

$\binom{16}{3} - \binom{4}{1}*\binom{10}{7} + \binom{4}{2}*\binom{4}{1 } - \binom{4}{3}*0$ = 104

Comments

case 3 won't come right ? since we have already exceeded total sum 17.

Also, 

k1 + k2 + k3 + k4 = 17 - 3 - 7

k1 + k2 + k3 + k4 = 10

Here sum should be 7  , not 10.  

---

yes case 3 won't come, I've mentioned 0 solutions in it.

---

We don't have to consider at all since it physically doesn't make sense.

---

I just laid down all the cases to make it clear