<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=US-ASCII">
<META content="MSHTML 6.00.2800.1141" name=GENERATOR></HEAD>
<BODY id=role_body style="FONT-SIZE: 10pt; COLOR: #000000; FONT-FAMILY: Arial"
bottomMargin=7 leftMargin=7 topMargin=7 rightMargin=7><FONT id=role_document
face=Arial color=#000000 size=2><FONT id=role_document face=Arial color=#000000
size=2>Brendan wrote:<BR><BR> >> How many n X n squares are
there, filled with<BR> >> the numbers 1...n, such that in row
or column k,<BR><BR>in row k and in column k<BR><BR> >> for all
k = 1...n, the number k appears at least
once?<BR> ><BR> >1<BR> >6<BR> >2683<BR> >223041730<BR> >6009583845720101<BR> >81562450515482338061230306<BR> >801231178966121521807378920617005246471<BR> >7747118609267949193978742640152633949388622796278760450<BR> >96260050927125657231057045653340232713369826309730222706933915414681058441<BR> >...<BR> >and
a(100) has 19961 digits,<BR> ><BR> >and by now you are
suspecting I have a formula.<BR><BR>no, by then I was suspecting you only had
found a recursion<BR><BR> >Define<BR> > A(i) =
(n-1)^i*n^(n-i) -
(n-2)^i*(n-1)^(n-i)
(i=0..n)<BR> > B(i) = (n-1)^i*n^(n-i) -
(n-2)^(i-1)*(n-1)^(n-i+1) (i=1..n)<BR><BR>so it's A(n,i),
B(n,i)<BR><BR> >Then<BR> > a(n) = sum(
binomial(n,i)*(-1)^i*A(i)^(n-i)*B(i)^i, i=0..n ).<BR><BR>nice.<BR>hmm, someone
should generate all such similar formulae.<BR>Without knowing about the
latin-squares problem,<BR>what rank would we have given this formula in the
space<BR>of all formulae sorted by "interestingness"
?<BR><BR> >Interprettation:<BR> > A(i) is the number
of ways of choosing row j, say R, such that
it<BR> > has at least one j, and i
specified positions R[k[1]], ...,
R[k[i]]<BR> > that DO NOT include position
R[j] don't have R[k[m]]=k[m] for any m.<BR><BR>I don't understand. A(i) doesn't
depend on j, and what's k[i]. <BR>Can you give it with symbols rather than words
?<BR><BR> > B(i) is the number of ways of choosing row j,
say R, such that it<BR> > has at least one
j, and i specified positions R[k[1]], ...,
R[k[i]]<BR> > that DO include position
R[j] don't have R[k[m]]=k[m] for any m.<BR> ><BR> >
Now A(i)^(n-i) * B(i)^i is the number of ways of choosing all
the<BR> > rows such that row j has at least one j for each
j, and such that<BR> > a specified set of i columns each do
not have an entry equal to the<BR> > column
number.<BR><BR>who specifies it ?<BR><BR> > Now you can see
that the given formula for a(n) is just<BR> >
inclusion-exclusion over the erroneous columns, always working
with<BR> > matrices having valid rows.<BR><BR>shouldn't
there also be formula with treating row+columns simultaneously<BR>giving n sets
of (n+n-1) cells ?<BR><BR> >Can someone do the OEIS thing with this
please?<BR><BR>.. thus stealing your idea and giving it to ATT so ATT can claim
copyright<BR>for it and punish people who make more than two copies of it on
their HD etc.?<BR>And also making the submitter responsible for eventual
problems<BR>arising from the sequence. (see terms and conditions)<BR>Is this why
you want someone else to submit ?<BR><BR> >Cheers, Brendan.<BR><BR>now,
count the isomorphism classes !<BR><BR>what's with 3d ?<BR>what's with
pandiagonals (row#k,column#k,SW-NE-pandiagonal#k,<BR> SE-NW-pandiagonal#k
all have at least one k) ?<BR>what's with 13directions having this property in
cubes ?<BR>what's with rectangles instead of squares ?<BR><BR><BR><BR>Cheers,
Guenter. </FONT></FONT></BODY></HTML>