Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-06-23 13:47:32

Ed Barr
Guest

A special form of squares

Hi all,

Imagine a 3x3 grid and 3 each of the letters A, B, and C.
The question is: in how many different ways can the letters be placed in the cells of the grid in such a way that each row and each column contains exactly one of each?

The answer is not difficult to find by simply trying.
Put ABC in the first line, then the second line can be either BCA or CAB. In either case, the third line has to be the other one - so there are 2 possible solutions if the first line reads ABC.
As we can create 6 different first lines (the 6 permutations of the letters A, B, and C) the total number of grids fulfilling the requirements is 6 * 2 = 12.

The number of solutions for a 4x4 grid (and the letters A, B, C, and D) is already a lot more difficult to determine.
It turns out that the first line ABCD can lead to 9 possible second lines, and each of the possible second lines can lead to 4 possible 3rd lines. The fourth line is trivial, by then only 1 possible permutation is left.
Given that there are 24 possible first lines, the total number of grids fulfilling the requirements is 24 * 9 * 4 = 864.

I'm fairly sure that the number of possible valid 5*5 grids is 120 * 44 * 12 * 2 = 126720.

However, I've not (yet) been able to find a formula to calculate the possible solutions for a grid of any size.
Can anyone help?

Thanks in advance,
Ed

#2 2015-06-23 14:21:47

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: A special form of squares

Hi;

I think you want Latin Squares:

https://en.wikipedia.org/wiki/Latin_square

I do not think there is a formula for n x n Latin Squares. You have to use a computer.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB