a too-short sequence related to Latin squares
Sterten at aol.com
Sterten at aol.com
Tue Sep 7 19:12:11 CEST 2004
>> 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.
More information about the SeqFan
mailing list