GATE question

Question

Q. 6 Xs has to be placed in the figure below such that each row contains at least one X. In how many ways can this be done?

a) 160

b) 180

c) 170

d) 26

Answer 1

Total number of ways to select 6 squares out of 8 squares = $\Large\binom{8}{6}$ = 28
Now subtract the cases where any row remains empty.

Only 2 cases are possible-
1) The first row remains empty.
2) The third row remains empty.
Note - Middle row can't have remained empty as minimum 6 squares are required.

So Number of Possible ways = 28-2 = 26. 

Comments

@Soumya , Can we get any generalized solution for this problem because problem can be anything like " there are 10 rows and each row contains 5 square boxes , then find out the number of ways in which we put 15 'X' in such a way that each row has minimum 1 'X' ?" Then how to solve this question.

Can we reduce this problem to this problem ,"How many no. of ways to put 15 identical balls into 50 distinct boxes such that  we put 5 boxes in a row and  atleast one box from each row remains non-empty ?"

One generalized solution using generating function is given below :-

but I want to know can we solve this problem quickly using  this formula C(n+r-1 , r)  and some modification.

---

ankit  
Many constraints can be applied to this type of questions. Even with a single constraint, many cases are possible when 2 or more rows can be empty simultaneously. 

In general, If each row contains equal no. of squares then we can use this formula + inclusion-exclusion principle (if required) - 

$\binom{Total Number of squares}{Number of X's}-\binom{Number of rows}{1}*\binom{Remaining  Number Of Squares}{Number of X's}$ 

If more complex constraints are given then Generating Functions will be the best choice.

I will let you know if I find any better method

---

@Soumya, sorry , I edited my question some time ago after analyzed my mistake.. now, no row can have all empty boxes means each row has at least non-empty boxes...I tried this problem using putting balls into boxes but did not get the right answer that's why I asked...If u get the right answer at any time then please comment here :)..

Answer 2

$R1$ has $2$ squares, $R2$ has $4$ squares and $R3$ has $2$ squares

We need to place 6Xs, let's take all possibilities

R1	R2	R3
1	4	1
2	3	1
2	2	2
1	3	2

Total number of ways = $(_{1}^{2}\textrm{C}*_{4}^{4}\textrm{C}*_{1}^{2}\textrm{C})+(_{2}^{2}\textrm{C}*_{3}^{4}\textrm{C}*_{1}^{2}\textrm{C})+(_{2}^{2}\textrm{C}*_{2}^{4}\textrm{C}*_{2}^{2}\textrm{C})+(_{1}^{2}\textrm{C}*_{3}^{4}\textrm{C}*_{2}^{2}\textrm{C})$

         $= 2*1*2 +1*4*2 + 1*6*1 + 2*4*1$

         $ = 4 + 8 + 6 + 8$

         $ = 26$

Alternative way

Selecting $6$ squares out of $8$ squares can be done in $_{6}^{8}\textrm{C} = 28$ ways

This will contain the folwing combination $(R1, R2,R3)\rightarrow ( 2 , 4 , 0 ) $  and $(R1,R2,R3)\rightarrow ( 0 , 4 , 2 ) $, but according to the question we need atlast $1 X$ in each row

$\therefore$ we need to subtract these $2$ combinations from  $28$ to get the result.

So, the answer will be $28 - 2 = 26$