5
$\begingroup$

If I have $8$ red balls and $8$ blue balls, what are the total number of arrangements possible where each row and each column have $2$ red and $2$ blue balls in a $4 \times 4$ grid?

How will this answer differ if all the ball were distinct?

For the first part, an idea was to find the solutions to $\sum_{i = 1}^4 x_{ij}= 0$, $j = 1, \cdots, 4$, $\sum_{j = 1}^4 x_{ij} = 0$, $i = 1, \cdots, 4$ where $x_{**} = \pm 1$, but that doesn't seem simple to solve.

$\endgroup$
  • 3
    $\begingroup$ I dare not post this as an answer but I just thought I'd share the oeis link to this relevant sequence: 0,1,6,90,2040,... which generalises the problem to $n\times n$ matrices with exactly two "1"s in each row and column and the remaining entries "0"s. In particular, on the oeis page, the link called "Deranged Socks" by Sally Cockburn and Joshua Lesperance will tell you all you need to know about this lovely problem. I won't spoil it for you here :) $\endgroup$ – N. Shales Feb 17 '18 at 3:41
2
$\begingroup$

We can ignore the blue balls and just place two red balls in each row and column.

Place two balls in the first column, $\binom 42 = 6$ options.

Chose which column holds the other ball of the lower row, $\binom 31 =3$ options.

Then $2$ cases:

  • the second ball in this column also matches the first column row ($1$ option); this determines the remaining ball positions.
  • the second ball is in one of the other two positions, $2$ options. Then choose which of the remaining columns also holds a ball in the same position as one of those in the first column, $2$ options, and the grid is determined.

Thus we have $6\times 3\times (1+2\times 2) = 90$ options to place the red balls.

If the balls are all distinct, we simply choose a ball for each space in succession and get $16!$ options.

$\endgroup$
1
$\begingroup$

I can't see any better approach than to count them systematically. Your system has equations in 16 unknowns, so even if you try to solve it over the field with two elements, to take care of $x_{ij} = \pm 1,$ there isn't much hope.

There are 6 possible arrangements for a row:

  1. RRBB
  2. RBRB
  3. RBBR
  4. BBRR
  5. BRBR
  6. BRRB

Note that the last three are "inverses" of the first three, obtained by swapping red and blue. Since the first column has two reds and two blues we must choose two rows from the first three, and two rows from the last three.

When we choose the two rows the start with R, we can either choose the same row twice, or choose two different rows. If we choose the same row twice, then a moment's thought shows we also have to choose the inverse twice. We have six ways to arrange the two copies of the row and its inverse, and three ways to choose the row, so this gives $18$ ways if we choose the same row twice.

Now suppose we we choose row 1 and row 2. Then we have two reds in column 1, 2 blues in column 4, and a blue and a red in columns 2 and 3. To fulfill the conditions, we must choose rows 4 and 5. There are 24 ways to arrange these 4 rows. A similar analysis shows obtains whenever we choose two different rows from among the first 3 (check this), so we have $72$ arrangements, giving a total of $90$ arrangements.

Notice that this analysis shows that whenever we pick a row, we must also pick its inverse. There's probably a quick way to see that at once, which would shorten the argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.