login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A099152 Number of n X n permutation matrices in which the sums of the entries of each NorthEast-SouthWest 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 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.

V. 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

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: 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 15:28 EDT 2018. Contains 316528 sequences. (Running on oeis4.)