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>
More information about the SeqFan
mailing list