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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002464 Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.
(Formerly M2070 N0818)
34
1, 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, 831283558, 11661506218, 175203184374, 2806878055610, 47767457130566, 860568917787402, 16362838542699862, 327460573946510746, 6880329406055690790, 151436547414562736234, 3484423186862152966838 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Permutations of 12...n such that none of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

This sequence is also the solution to the 'toast problem' devised by my house-mates and me as maths undergraduates some 27 years ago. Given a toast rack with n slots, how many ways can the slices be removed so that a subsequent slices are never removed from a adjacent slots. - David Jones (david.jones(AT)zetnet.co.uk), Oct 24 2003

This sequence was also derived by the late D. P. Robbins. - David Callan, Nov 04 2003

Another interpretation: number of permutations of n containing exactly n different patterns of size n-1. - Olivier Gérard, Nov 05 2007

REFERENCES

W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.

P. Poulet, Reply to Query 4750, Permutations, L'Interm\'{e}diaire des Math\'{e}maticiens, 26 (1919), 117-121.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..500

M. Abramson and W. O. J. Moser, Permutations without rising or falling w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254.

W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373

C. Homberger, Counting Fixed Length Permutation Patterns, Online Journal of Analytic Combinatorics, 7 (2012)

Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014

Irving Kaplansky, The asymptotic distribution of runs of consecutive elements, Ann. Math. Statistics, 16 (1945), 200-203

Sergey Kitaev, Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], (2013)

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 625-635

J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.

L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schroeder problems and the n-kings problem, SIAM J. Discrete Math., 4 (1991), 275-280.

Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. See Column 3 in the table on page 3.

B. E. Tenner, Mesh patterns with superfluous mesh, arXiv preprint arXiv:1302.1883, 2013

Eric Weisstein's World of Mathematics, Permutation

Multiple authors, Discussion at the Art Of Problem Solving forum

FORMULA

If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1)-(n-2)*a(n-2)-(n-5)*a(n-3)+(n-3)*a(n-4).

G.f.: Sum_{n >= 0} n!*x^n*(1-x)^n/(1+x)^n. - Philippe Flajolet

G.f.: e^((1 + x)/((-1 + x) * x)) * (1 + x) * Gamma(0, (1 + x)/((-1 + x) * x))/((-1 + x) * x). - Eric W. Weisstein, May 16 2014

Let S_{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} S_{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; for n >= 4, S[n] = (n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4].

a(n) = n! + Sum_{k=1..n} (-1)^k * Sum_{t=1..k} binomial(k-1,t-1) * binomial(n-k,t) * 2^t * (n-k)! - Max Alekseyev, Jan 29 2006

a(n) = Sum_{k=0..n} (-1)^(n-k)*k!*b(n,k), where g.f. for b(n,k) is (1-x)/(1-(1+y)*x-y*x^2), cf. A035607. - Vladeta Jovovic, Nov 24 2007

Asymptotic (M. Abramson and W. Moser, 1966): a(n)/n! ~ (1 - 2/n^2 - 10/3/n^3 - 6/n^4 - 154/15/n^5)/e^2. - Vaclav Kotesovec, Apr 19 2011

EXAMPLE

a(4) = 2: 2413, 3142.

a(5) = 14 corresponds to these 14 permutations of length 5: 13524, 14253, 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142.

MAPLE

A002464 := proc(n) options remember; if n <= 1 then 1 elif n <= 3 then 0 else (n+1)*A002464(n-1)-(n-2)*A002464(n-2)-(n-5)*A002464(n-3)+(n-3)*A002464(n-4); fi; end;

MATHEMATICA

(* computation from the permutation class *)

g[ L_ ] := Apply[ And, Map[ #>1&, L ] ]; f[ n_ ] := Length[ Select[ Permutations[ Range[ n ] ], g[ Rest[ Abs[ RotateRight[ # ]-# ] ] ]& ] ]; Table[ f[ n ], {n, 1, 8} ] (* Erich Friedman *)

(* or direct computation of terms *)

Table[n! + Sum[(-1)^r*(n-r)!*Sum[2^c *Binomial[r-1, c-1] *Binomial[n-r, c], {c, 1, r}], {r, 1, n-1}], {n, 1, 30}] (* Vaclav Kotesovec, Mar 28 2011 *)

PROG

(PARI)

N = 66;  x = 'x + O('x^N);

gf = sum(n=0, N, n!*(x*(1-x))^n/(1+x)^n );

v = Vec(gf) /* Joerg Arndt, Apr 17 2013 */

CROSSREFS

Equals 2*A001266(n) for n >= 2. A diagonal of A001100. Cf. A010028.

Cf. A086852, A086853, A086854, A086855, A000130, A000349, A001267, A001268, A010028, A002493.

Cf. A089222.

Sequence in context: A174705 A109113 A081959 * A020063 A072148 A033169

Adjacent sequences:  A002461 A002462 A002463 * A002465 A002466 A002467

KEYWORD

nonn,nice,easy,changed

AUTHOR

N. J. A. Sloane, Apr 30 1991

EXTENSIONS

Merged with the old A001100, Aug 19 2003

Kaplansky reference from David Callan, Oct 29 2003

Tauraso reference from Parthasarathy Nambi, Dec 21 2006

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 23 08:59 EDT 2014. Contains 248443 sequences.