a too-short sequence related to Latin squares

[Brendan McKay]

* Hugo Pfoertner <all at abouthugo.de> [040907 06:12]:
> > :
> > :How many n X n squares are there, filled with
> > :the numbers 1...n, such that in row or column k,
> > :for all k = 1...n, the number k appears at least once?
> 
> I wrote a little program, which confirms a(3)=2683 and gets
> a(4)=223041730 after checking the 4^16 possible matrices. Getting the
> next term by brute force would require 5^25~=2.98*10^17 checks, which is
> a good reason to defer the computation until better ideas become
> available.

For each k, decide where the first k in row k will be, and where
the first k in column k will be.  Suppose this partial matrix is K.
The number of such Ks for n=5 is about a million, perhaps less.

For each K, the number of ways m(K) to fill in the remaining positions is
the product over the remaining positions of the number of available values
in that position.  The rule is that the positions on row k before the
k in row k of K cannot contain k (got that?) and similarly for columns.
So m(K) is a simple calculation with no searching.

Now sum m(K) over K and you got it.  Piece of cake.  n=6 can be
done too (at most a few hundred million Ks).

Brendan.