# a too-short sequence related to Latin squares

Sterten at aol.com Sterten at aol.com
Wed Sep 8 14:04:25 CEST 2004

```Brendan wrote:

>> How many n X n squares are  there,  filled with
>> the numbers 1...n, such that in row  or column  k,

in row k and in column k

>> for all  k = 1...n, the number k appears at least   once?
>
>1
>6
>2683
>223041730
>6009583845720101
>81562450515482338061230306
>801231178966121521807378920617005246471
>7747118609267949193978742640152633949388622796278760450
>96260050927125657231057045653340232713369826309730222706933915414681058441
>...
>and  a(100) has 19961 digits,
>
>and by now you are  suspecting I have a formula.

no, by then I was suspecting you only had  found a recursion

>Define
>   A(i) =  (n-1)^i*n^(n-i) -  (n-2)^i*(n-1)^(n-i)           (i=0..n)
>   B(i) = (n-1)^i*n^(n-i) -  (n-2)^(i-1)*(n-1)^(n-i+1)    (i=1..n)

so it's A(n,i),  B(n,i)

>Then
>   a(n) = sum(  binomial(n,i)*(-1)^i*A(i)^(n-i)*B(i)^i, i=0..n ).

nice.
hmm, someone  should generate all such similar formulae.
Without knowing about the  latin-squares problem,
what rank would we have given this formula in the  space
of all formulae sorted by "interestingness"  ?

>Interprettation:
>   A(i) is the number  of ways of choosing row j, say R, such that  it
>      has at least one j, and i  specified positions R[k[1]], ...,  R[k[i]]
>      that DO NOT include position  R[j] don't have R[k[m]]=k[m] for any m.

I don't understand. A(i) doesn't  depend on j, and what's k[i].
Can you give it with symbols rather than words  ?

>   B(i) is the number of ways of choosing row j,  say R, such that it
>      has at least one  j, and i specified positions R[k[1]], ...,  R[k[i]]
>      that DO include position  R[j] don't have R[k[m]]=k[m] for any m.
>
>    Now  A(i)^(n-i) * B(i)^i  is the number of ways of choosing all  the
>   rows such that row j has at least one j for each  j, and such that
>   a specified set of i columns each do  not have an entry equal to the
>   column  number.

who specifies it ?

>   Now you can see  that the given formula for a(n) is just
>    inclusion-exclusion over the erroneous columns, always working  with
>   matrices having valid rows.

shouldn't  there also be formula with treating row+columns simultaneously
giving n sets  of (n+n-1) cells ?

>Can someone do the OEIS thing with this  please?

.. thus stealing your idea and giving it to ATT so ATT can claim  copyright
for it and punish people who make more than two copies of it on  their HD
etc.?
And also making the submitter responsible for eventual  problems
arising from the sequence. (see terms and conditions)
Is this why  you want someone else to submit ?

>Cheers, Brendan.

now,  count the isomorphism classes !

what's with 3d ?
what's with  pandiagonals (row#k,column#k,SW-NE-pandiagonal#k,
SE-NW-pandiagonal#k  all have at least one k) ?
what's with 13directions having this property in  cubes ?
what's with rectangles instead of squares ?

Cheers,  Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20040908/c99b246b/attachment-0001.htm>
```