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