Welcome to our community

Be a part of something great, join today!

Combination Problem

schinb65

New member
Jan 1, 2013
12
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

Administrator
Staff member
Jan 26, 2012
4,052
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
Feb 2, 2012
409
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

Administrator
Staff member
Jan 26, 2012
4,052
That was the thing I was missing, soroban! Thank you for pointing it out. We should divide by $3!$, not \(\displaystyle \binom{3}{1}\).