%I A002464 M2070 N0818
%S A002464 1,1,0,0,2,14,90,646,5242,47622,479306,5296790,63779034,831283558,11661506218,
%T A002464 175203184374,2806878055610,47767457130566,860568917787402,16362838542699862,
%U A002464 327460573946510746,6880329406055690790,151436547414562736234,3484423186862152966838
%N 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.
%C A002464 Permutations of 12...n such that none of the following occur: 12, 23,
..., (n-1)n, 21, 32, ..., n(n-1).
%C A002464 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
%C A002464 This sequence was also derived by the late D. P. Robbins. - David Callan
(callan(AT)stat.wisc.edu), Nov 04 2003
%C A002464 Another interpretation: number of permutations of n containing exactly
n different patterns of size n-1. - Olivier GERARD, Nov 05 2007
%D A002464 M. Abramson and W. O. J. Moser, Permutations without rising or falling
w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254.
%D A002464 W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig,
Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271.
%D A002464 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied
Tables, Cambridge, 1966, p. 263.
%D A002464 Irving Kaplansky, The asymptotic distribution of runs of consecutive
elements, Ann. Math. Statistics, 16 (1945), 200-203
%D A002464 P. Poulet, Reply to Query 4750, Permutations, L'Interm\'{e}diaire des
Math\'{e}maticiens, 26 (1919), 117-121.
%D A002464 J. Riordan, A recurrence for permutations without rising or falling successions.
Ann. Math. Statist. 36 (1965), 708-710.
%D A002464 D. P. Robbins, The probability that neighbors remain neighbors after
random rearrangements. Amer. Math. Monthly 87 (1980), 122-124.
%D A002464 L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schroeder problems
and the n-kings problem, SIAM J. Discrete Math., 4 (1991), 275-280.
%D A002464 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A002464 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A002464 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see
Problem 6.40.
%D A002464 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.
%H A002464 N. J. A. Sloane, <a href="b002464.txt">Table of n, a(n) for n = 0..500</
a>
%H A002464 W. Ahrens, <a href="http://gallica.bnf.fr/scripts/ConsultationTout.exe?E=0&O=N099446">
Mathematische Unterhaltungen und Spiele</a>, Leipzig: B. G. Teubner,
1901.
%H A002464 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
Publications/books.html">Analytic Combinatorics</a>, 2009; see page
373
%H A002464 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Permutation.html">Permutation</a>
%F A002464 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).
%F A002464 G.f.: Sum_{n >= 0} n!*x^n*(1-x)^n/(1+x)^n. - Philippe Flajolet
%F A002464 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].
%F A002464 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
%F A002464 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
%e A002464 a(4) = 2: 2413, 3142.
%e A002464 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)
%p A002464 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;
%t A002464 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)
%Y A002464 Equals 2*A001266(n) for n >= 2. A diagonal of A001100. Cf. A010028.
%Y A002464 Cf. A086852, A086853, A086854, A086855, A000130, A000349, A001267, A001268,
A010028, A002493.
%Y A002464 Cf. A089222.
%Y A002464 Sequence in context: A139183 A109113 A081959 this_sequence A020063 A072148
A033169
%Y A002464 Adjacent sequences: A002461 A002462 A002463 this_sequence A002465 A002466
A002467
%K A002464 nonn,nice,easy
%O A002464 0,5
%A A002464 N. J. A. Sloane (njas(AT)research.att.com).
%E A002464 Merged with the old A001100, Aug 19 2003.
%E A002464 Kaplansky reference from David Callan (callan(AT)stat.wisc.edu), Oct
29 2003
%E A002464 Tauraso reference from Parthasarathy Nambi (PachaNambi(AT)yahoo.com),
Dec 21 2006
|
