A173103 The number of possible borders of Latin squares with the top row fixed.

1, 1, 2, 26, 924, 81624, 13433520, 3706068240, 1582042381920, 987057348842880, 861632512758823680, 1016677874552767660800, 1576819957670934809817600, 3140963381712726319842892800, 7880571655922780897709237811200, 24492587962448960350527019884595200

Offset: 1

Author

Johan de Ruiter, Feb 09 2010

Keywords

• nonn

Comments

The definition is not quite right, and should be corrected.

Examples

			The only two configurations for n=3, given the top row is 123:
  123   123
  2 1   3 2
  312   231
Two arbitrary configurations for n=4, given the top row is 1234:
  1234   1234
  2  1   4  3
  3  2   3  2
  4123   2341
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..100
• J. de Ruiter, On Jigsaw Sudoku Puzzles and Related Topics, Bachelor Thesis, Leiden Institute of Advanced Computer Science, 2010.

Crossrefs

Related to A000166. Equals A173104 divided by n!.

Programs

Maple

d:= proc(n) d(n):= `if`(n<=1, 1-n, (n-1)*(d(n-1)+d(n-2))) end:
a:= proc(n) a(n):= `if`(n<4, [1, 1, 2][n], (n-2)!*((n-1)/
       (n-2)*d(n-1)^2+2*d(n-1)*d(n-2)+(2*n-5)/(n-3)*d(n-2)^2))
    end:
seq(a(n), n=1..20);  # Alois P. Heinz, Aug 18 2013

Mathematica

d = Subfactorial;
a[n_] := If[n <= 3, {1, 1, 2}[[n]], (n-2)! (((2n-5) d[n-2]^2)/(n-3) + 2d[n-1] d[n-2] + ((n-1) d[n-1]^2)/(n-2))];
Array[a, 20] (* Jean-François Alcover, Nov 10 2020 *)

Formula

For n>3, a(n)=(n-2)!((n-1)/(n-2)d[n-1]^2+2d[n-1]d[n-2]+(2n-5)/(n-3)d[n-2]^2), where d[k] is the number of derangements of k elements (A000166).