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

1, 1, 1, 3, 7, 23, 83, 405, 2113, 12657, 82297, 596483, 4698655, 40071743, 367854835, 3622508685, 38027715185, 424060091065, 5006620130753, 62395131973755, 818456924866815, 11271715349614463

Offset

0,4

Comments

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.

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

From Emeric Deutsch, Nov 28 2008: (Start)

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.

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.

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

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

References

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

Links

Table of n, a(n) for n=0..21.

N. J. Cavenagh and I. M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math. 158 (2010), 136-146.

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 672, 732-736.

G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.

Kevin Pratt, Closed-Form Expressions for the n-Queens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.

W. Schubert, N-Queens page

Eduard C. Taganap and Rainier D. Almuete, n-Rooks and n-queens problem on planar and modular chessboards with hexagonal cells, Notes Num. Theor. Disc. Math. (2023) Vol. 29, No. 4, 774-788. See p. 778.

Mathematica

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}]];
a[n_] := Coefficient[b[1, Range[n], {}], x, n];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 12}] (* Jean-François Alcover, Aug 07 2018, after Alois P. Heinz *)

Crossrefs

Cf. A125182. [From Emeric Deutsch, Nov 28 2008]

Sequence in context: A346771 A136508 A184935 * A289317 A113860 A080355

Adjacent sequences: A099149 A099150 A099151 * A099153 A099154 A099155

Keyword

nonn,nice,more

Author

Cecilia Bebeacua and Simone Severini, Nov 16 2004

Extensions

More terms from Ivica Kolar, Nov 23 2004

a(14)-a(18) from Ian Wanless, Jul 30 2010, from the Cavenagh-Wanless paper.

a(19),a(20) from W. Schubert, May 27 2011

a(21) from W. Schubert, Feb 26 2012

a(0) = 1 prepended by Joerg Arndt, Sep 16 2018

Status

approved