# Combination Problem

#### schinb65

##### New member
Thirty items are arranged in a 6-by-5 array. Calculate the number of ways to form a set of three distinct items such that no two of the selected items are in the same row or same column.

I am told the answer is 1200.

I do not believe that I am able to use the standard combination formula.

This is what I did which I got the correct answer but do not really believe I am able to do this every time.

The first Number I can chose from 30.
The Second #, Chose from 20.
The 3rd #, Chose from 12.
So 30*20*12= 7200
7200/6= 1200
I divided by 6 since I am choosing 3 numbers and I multiplied that by 2 since I have to get rid of each row and column when a number is chosen.

Will this always work? Does an easier way exist?

#### Jameson

Staff member
I'm not sure what the correct answer is but $$\displaystyle \frac{30*20*12}{\binom{3}{1}}=2400$$ is my first thought. I don't see a reason to divide by 2 at the end. Hopefully someone else can provide some insight but that's my first thought on the problem.

Let's look at a simpler case of a 3x3 grid where we want to arrange 3 items that can't be in the same row or column. The first item has 9 slots, the second has 4 and the last one just has 1. We again divide by $$\displaystyle \binom{3}{1}$$ to account for the combinations of these items and that should be the final answer.

Anyway, that's my reasoning for now. Not promising it's correct unfortunately #### soroban

##### Well-known member
Hello, schinb65!

Thirty items are arranged in a 6-by-5 array.
Calculate the number of ways to form a set of three distinct items
such that no two of the selected items are in the same row or same column.

I am told the answer is 1200.

I do not believe that I am able to use the standard combination formula.

This is what I did which I got the correct answer,
but do not really believe I am able to do this every time.

The first number I can chose from 30.
The second #, choose from 20.
The third #, choose from 12.

So: 30*20*12= 7200

7200/6 = 1200 . Correct!

The first can be any of the 30 items.
Select, say, #7; cross out all items in its row and column.

. . $\begin{array}{|c|c|c|c|c|} \hline 1 & \times & 3 & 4 & 5 \\ \hline \times & \bullet & \times & \times & \times \\ \hline 11 & \times & 13 & 14 & 15 \\ \hline 16 & \times & 18 & 19 & 20 \\ \hline 21 & \times & 23 & 24 & 25 \\ \hline 26 & \times & 28 & 29 & 30 \\ \hline \end{array}$

The second can be any of the remaining 20 items.
Select, say, #24; cross out all items in its row and column.

. . $\begin{array}{|c|c|c|c|c|} \hline 1 & \times & 3 & \times & 5 \\ \hline \times & \bullet & \times & \times & \times \\ \hline 11 & \times & 13 & \times & 15 \\ \hline 16 & \times & 18 & \times & 20 \\ \hline \times & \times & \times& \bullet & \times \\ \hline 26 & \times & 28 & \times & 30 \\ \hline \end{array}$

The third can be any of the remaining 12 items.
Select, say, #28.

. . $\begin{array}{|c|c|c|c|c|} \hline 1 & \times & \times & \times & 5 \\ \hline \times & \bullet & \times & \times & \times \\ \hline 11 & \times & \times & \times & 15 \\ \hline 16 & \times & \times & \times & 20 \\ \hline \times & \times & \times& \bullet & \times \\ \hline \times & \times & \bullet & \times & \times \\ \hline \end{array}$

There are: .$30\cdot20\cdot12 \,=\,7200$ ways to select 3 items.

Since the order of the selections is not considered,
. . we divide by $3!$

Answer: .$\dfrac{7200}{3!} \;=\;1200$

#### Jameson

That was the thing I was missing, soroban! Thank you for pointing it out. We should divide by $3!$, not $$\displaystyle \binom{3}{1}$$.