a too-short sequence related to Latin squares

[Hugo Pfoertner]

hv at crypt.org schrieb:
> 
> "N. J. A. Sloane" <njas at research.att.com> wrote:
> :Dear Seqfans,  is the following sequence already
> :in the OEIS?  one more term would be helpful!
> :Neil
> :
> :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?
> :
> :For n = 1 there is just 1,
> :
> :for n = 2 there seem to be 6
> :namely
> :
> :11 11 12 12 12 21
> :12 22 12 21 22 12
> 
> Naming the squares like:
> AB
> CD
> .. this is:
>   A =1,D =2: 4 (2B 2C, ie 2 options for B times 2 options for C)
>   A =1,D!=2: 1 (1B 1C)
>   A!=1,D =2: 1 (1B 1C)
>   A!=1,D!=2: 0
>             ==
>              6
> 
> For n = 3 and naming ABC/DEF/GHI, I make it:
>   A =1,E =2,I =3: 729 (3B 3C 3D 3F 3G 3H)
>   A =1,E =2,I!=3: 450 (3B 3D 2I 5(CF) 5(GH))
>   A =1,E!=2,I =3: 450
>   A!=1,E =2,I =3: 450
>   A =1,E!=2,I!=3: 196 (2E 2I 7(CDF) 7(BGH))
>   A!=1,E =2,I!=3: 196
>   A!=1,E!=2,I =3: 196
>   A!=1,E!=2,I!=3:  16 (2A 2E 2I 2(BCDFGH))
>                  ====
>                  2683
> 
> No sequence in the database matches (1, 6, 2683); I don't think I'd want
> to work out n = 4 without some programming.
> 
> Hugo

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.

Hugo Pfoertner