

A099152


Number of n X n permutation matrices in which the sums of the entries of each NorthEastSouthWest diagonal are 0 or 1.


16



1, 1, 1, 3, 7, 23, 83, 405, 2113, 12657, 82297, 596483, 4698655, 40071743, 367854835, 3622508685, 38027715185, 424060091065, 5006620130753, 62395131973755, 818456924866815, 11271715349614463
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Numbers of solutions to a modified version of the nqueens problem, in which two queens do not attack each other if they are in the same NorthWestSouthEast diagonal.
Number of perfect extremal Skolemtype 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. [CavenaghWanless]


REFERENCES

D. E. Knuth, The Art of Computer Programming, Volume 4, Prefascicle 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), 136146.
V. Kotesovec, Nonattacking chess pieces, 6ed, 2013, p. 672, 732736.
G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.
Kevin Pratt, ClosedForm Expressions for the nQueens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.
W. Schubert, NQueens page


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}] (* JeanFrançois Alcover, Aug 07 2018, after Alois P. Heinz *)


CROSSREFS

Cf. A125182. [From Emeric Deutsch, Nov 28 2008]
Sequence in context: A169650 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 CavenaghWanless 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



