|
| |
|
|
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)
|
|
32
|
|
|
|
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 GERARD, Nov 05 2007
|
|
|
REFERENCES
|
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.
C. Homberger, Counting Fixed Length Permutation Patterns, Online Journal of Analytic Combinatorics, 7 (2012)
Irving Kaplansky, The asymptotic distribution of runs of consecutive elements, Ann. Math. Statistics, 16 (1945), 200-203
Sergey Kitaev, Jeffrey Remmel, <a href="http://arxiv.org/abs/1304.4286">(a,b)-rectangle patterns in permutations and words</a>, arXiv:1304.4286 [math.CO], (2013)
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.
B. E. Tenner, Mesh patterns with superfluous mesh, arXiv preprint arXiv:1302.1883, 2013
|
|
|
LINKS
|
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
|
|
|
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
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} ] (* from 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
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
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
|
| |
|
|
