0,5

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 (callan(AT)stat.wisc.edu), Nov 04 2003

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

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

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

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

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.

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.

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

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

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

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

Eric Weisstein's World of Mathematics, Permutation

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

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 (maxale(AT)gmail.com), 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 (vladeta(AT)eunet.rs), Nov 24 2007

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)

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;

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

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: A139183 A109113 A081959 this_sequence A020063 A072148 A033169

Adjacent sequences: A002461 A002462 A002463 this_sequence A002465 A002466 A002467

nonn,nice,easy

N. J. A. Sloane (njas(AT)research.att.com).

Merged with the old A001100, Aug 19 2003.

Kaplansky reference from David Callan (callan(AT)stat.wisc.edu), Oct 29 2003

Tauraso reference from Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Dec 21 2006