%I #53 Nov 30 2023 11:14:52

%S 1,1,1,3,7,23,83,405,2113,12657,82297,596483,4698655,40071743,

%T 367854835,3622508685,38027715185,424060091065,5006620130753,

%U 62395131973755,818456924866815,11271715349614463

%N Number of n X n permutation matrices in which the sums of the entries of each NorthEast-SouthWest diagonal are 0 or 1.

%C Numbers of solutions to a modified version of the n-queens problem, in which two queens do not attack each other if they are in the same NorthWest-SouthEast diagonal.

%C Number of perfect extremal Skolem-type sequences of order n.

%C From _Emeric Deutsch_, Nov 28 2008: (Start)

%C a(n) is also the number of permutations p of {1,2,...,n} for which the numbers p(i)-i (i=1,2,...,n) are distinct. Example: a(4)=7 because we have 4132, 3142, 2413, 4213, 2431, 3241 and 4321.

%C a(n) is also the number of permutations p of {1,2,...,n} for which the numbers p(i)+i (i=1,2,...,n) are distinct. Example: a(4)=7 because we have 1423, 2413, 3142, 1342, 3124, 2314 and 1234.

%C a(n) = A125182(n,n). (End)

%C Also number of transversals in the n X n matrix M defined by M_{ij} = i+j. [Cavenagh-Wanless]

%D D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.

%H N. J. Cavenagh and I. M. Wanless, <a href="http://dx.doi.org/10.1016/j.dam.2009.09.006">On the number of transversals in Cayley tables of cyclic groups</a>, Disc. Appl. Math. 158 (2010), 136-146.

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 672, 732-736.

%H G. Nordh, <a href="http://arXiv.org/abs/math.NT/0506155">Perfect Skolem sequences</a>, arXiv:math/0506155 [math.CO], 2005.

%H Kevin Pratt, <a href="https://arxiv.org/abs/1609.09585">Closed-Form Expressions for the n-Queens Problem and Related Problems</a>, arXiv:1609.09585 [cs.DM], 2016.

%H W. Schubert, <a href="http://web.archive.org/web/20130708134012/http://m29s20.vlinux.de/~wschub/nqueen.html">N-Queens page</a>

%H Eduard C. Taganap and Rainier D. Almuete, <a href="https://doi.org/10.7546/nntdm.2023.29.4.774-788">n-Rooks and n-queens problem on planar and modular chessboards with hexagonal cells</a>, Notes Num. Theor. Disc. Math. (2023) Vol. 29, No. 4, 774-788. See p. 778.

%t b[i_, p_, s_] := b[i, p, s] = If[p == {}, x^Length[s], Sum[b[i+1, p ~Complement~ {t}, s ~Union~ {t+i}], {t, p}]];

%t a[n_] := Coefficient[b[1, Range[n], {}], x, n];

%t Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 12}] (* _Jean-François Alcover_, Aug 07 2018, after _Alois P. Heinz_ *)

%Y Cf. A125182. [From _Emeric Deutsch_, Nov 28 2008]

%K nonn,nice,more

%O 0,4

%A Cecilia Bebeacua and _Simone Severini_, Nov 16 2004

%E More terms from _Ivica Kolar_, Nov 23 2004

%E a(14)-a(18) from _Ian Wanless_, Jul 30 2010, from the Cavenagh-Wanless paper.

%E a(19),a(20) from _W. Schubert_, May 27 2011

%E a(21) from _W. Schubert_, Feb 26 2012

%E a(0) = 1 prepended by _Joerg Arndt_, Sep 16 2018