a too-short sequence related to Latin squares

[Sterten at aol.com]

>> 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?

Brendan wrote:

>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.

I get  1248696.

>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.

m(K) is a product of n*n factors  each of which is 1,n-2,n-1,or n

>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).

only 1,3,22,115,415,1165 different products for  n=1,2,..,6.
n=7 takes some hours. I feel, that we could get another  speed-factor of n! ?!
Also, we could first determine the number of ks, where  the row and column
positions of the first appearance coincide. I.e. which lie  on the diagonal
and no other k appears in the (k-1)*2 cells before it in  that
row or  column.

1,6,2683,223041730,6009583845720101,81562450515482338061230306,  different 
matrices
1,5,120,8831,1248696,275064055, different  Ks
1,3,22,115,415,1165, different products



Guenter.