1

Say you have a 3x3 grid, and 3 objects to work with. Each occupies one space. How would I go about solving the amount of ways they can lay on the grid.

Example: (pardon my bad ASCII art)
[][][]
[][][]
[x][x][x]

Any help would be much appreciated, thanks!

Scrub
  • 13
  • Title explains most of it , does it? – Qwerty Jun 19 '16 at 04:21
  • Welcome to Math.SE. Your title doesn't explain most of it. The question as it stands is unclear and likely to get closed quickly. – Shailesh Jun 19 '16 at 04:22
  • Alright, I'll attempt to revise it. Sorry. – Scrub Jun 19 '16 at 04:23
  • If your question is this: you have a $3\times 3$ oriented grid (where there is a specific "up" and "left", etc...) and you wish to place three identical objects in the grid, in how many ways can you place them. This is the same question as "How many subsets of size three exist of the set ${1,2,\dots,9}$". If your question is instead where rotations and/or reflections are considered the same, then approach via burnside's lemma. – JMoravitz Jun 19 '16 at 04:33
  • 1
    In the first case, approach via binomial coefficients. If the second case, approach by that and burnside's lemma. – JMoravitz Jun 19 '16 at 04:34
  • Thanks, I'll look into it. – Scrub Jun 19 '16 at 04:35

1 Answers1

1

To reiterate what was said in the comments, imagine temporarily that your grid has its positions labeled.

$\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}$

A specific arrangement of the objects will then correspond to a selection of three numbers from $1$ to $9$.

$\begin{bmatrix}\circ&\times&\circ\\\circ&\circ&\times\\\circ&\circ&\times\end{bmatrix}$ would correspond to the set $\{2,6,9\}$

Assuming you consider $\begin{bmatrix}\circ&\times&\circ\\\circ&\circ&\times\\\circ&\circ&\times\end{bmatrix}$ to be a different arrangement than $\begin{bmatrix}\circ&\times&\times\\\times&\circ&\circ\\\circ&\circ&\circ\end{bmatrix}$, one can move freely between the set of desired arrangements and the set of subsets of size three of $\{1,2,\dots,9\}$ via a natural bijection.

The fact that there is a bijection between the sets in question implies that if we know how to count how many arrangements one of these questions has, we know how to count both.

We have thus boiled the question down to asking the question, "How many size three subsets exist of the set $\{1,2,\dots,9\}$?"

This is one of the many problems that binomial coefficients were designed to answer. The answer being $\binom{9}{3}=\frac{9!}{3!6!}=\frac{9\cdot 8\cdot 7}{3\cdot 2\cdot 1} = 84$ possible arrangements.

If you consider rotations and/or reflections of your grids to be considered "the same", for example the two arrangements pictured above, the question becomes harder since we will have over counted. Approach instead by Burnside's lemma.

JMoravitz
  • 79,518