a too-short sequence related to Latin squares

[hv at crypt.org]

Brendan McKay <bdm at cs.anu.edu.au> wrote:
:and by now you are suspecting I have a formula.
:
: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) = sum( binomial(n,i)*(-1)^i*A(i)^(n-i)*B(i)^i, i=0..n ).

Super stuff. Thanks for letting me have my CPU back. :)

Coding this, I came up against a slight problem: the definition of B(i)
means that when n=2, B(0) involves 0^(-1) as a factor. Replacing the
term with any finite number is enough to fix it, since within the main
formula it is always used as B(0)^0, but perhaps there is a minor
reformulation that avoids the glitch. Easiest perhaps is to extract
the i=0 term:

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

Hugo van der Sanden