OFFSET
1,2
COMMENTS
This problem arose because I misunderstood a question that Mira Bernstein asked me!
FORMULA
Formula from Brendan McKay, Sep 08 2004:
"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).
"Then a(n) = (n^n - (n-1)^n)^n + sum( binomial(n, i)*(-1)^i*A(i)^(n-i)*B(i)^i, i=1..n )
"Interpretation: 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] do not have R[k[m]]=k[m] for any m.
"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] do not 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.
"The given formula for a(n) is just inclusion-exclusion over the erroneous columns, always working with matrices having valid rows."
EXAMPLE
a(2) = 6:
11 11 12 12 12 21
12 22 12 21 22 12
Naming the squares AB/CD, ... these are:
A =1,D =2: 4 (2B 2C, i.e., 2 options for B times 2 options for C)
A =1,D!=2: 1 (1B 1C)
A!=1,D =2: 1 (1B 1C)
A!=1,D!=2: 0, for a total of 6.
For n = 3 and names ABC/DEF/GHI, we get
A =1,E =2,I =3: 729 (3B 3C 3D 3F 3G 3H)
A =1,E =2,I!=3: 450 (3B 3D 2I 5(CF) 5(GH))
A =1,E!=2,I =3: 450
A!=1,E =2,I =3: 450
A =1,E!=2,I!=3: 196 (2E 2I 7(CDF) 7(BGH))
A!=1,E =2,I!=3: 196
A!=1,E!=2,I =3: 196
A!=1,E!=2,I!=3: 16 (2A 2E 2I 2(BCDFGH)), for a total of 2683. - Hugo van der Sanden
MATHEMATICA
a[n_] := (n^n - (n-1)^n)^n + Sum[ (-1)^i*((n-1)^i*n^(n-i) - (n-2)^i*(n-1)^(n-i))^(n-i)*((n-1)^i*n^(n-i) - (n-2)^(i-1)*(n-1)^(n-i+1))^i * Binomial[n, i], {i, 1, n}]; a[1] = 1; a[2] = 6; Table[ a[n], {n, 1, 9}] (* Jean-François Alcover, Dec 20 2011, from formula *)
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
N. J. A. Sloane, Sep 03 2004
EXTENSIONS
a(3) from Hugo van der Sanden, Sep 03 2004
a(4) from Hugo Pfoertner, Sep 06 2004
a(4) confirmed by Hugo van der Sanden, Sep 07 2004
a(5) and a(6) from Guenter Stertenbrink (Sterten(AT)aol.com), using a method suggested by Brendan McKay, Sep 07 2004
Formula and further terms from Brendan McKay, Sep 08 2004
STATUS
approved