cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

Original entry on oeis.org

1, 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, 831283558, 11661506218, 175203184374, 2806878055610, 47767457130566, 860568917787402, 16362838542699862, 327460573946510746, 6880329406055690790, 151436547414562736234, 3484423186862152966838
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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 math undergraduates some 27 years ago: Given a toast rack with n slots, how many ways can the slices be removed so that no two consecutive slices are removed from 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
Number of directed Hamiltonian paths in the complement of the n-path graph P_n. - Andrew Howroyd, Mar 16 2016
There is an obvious connection between the two descriptions of the sequence: Replace the chessboard with a n X n zero-matrix and each king with "1". This matrix will transform the vector (1,2,..,n) into a permutation such that adjacent components do not differ by 1. The reverse is also true: Any such transformation is a solution of the king problem. - Gerhard Kirchner, Feb 10 2017
A formula of Poulet (1919) relates this to A326411: a(n) = T(n+2,1)/(n+2) + 2*T(n+1,1)/(n+1) + T(n,1)/n, where T(i,j) = A326411(i,j). - N. J. A. Sloane, Mar 08 2022
For the number of these permutations without fixed points see A288208. - Wolfdieter Lang, May 22 2025

Examples

			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.

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

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, A104698, A288208.
Column k=1 of A333706.

Programs

  • 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 *)
(* or from g.f. *)
M = 30; CoefficientList[Sum[n!*x^n*(1-x)^n/(1+x)^n, {n, 0, M}] + O[x]^M, x] (* Jean-François Alcover, Jul 07 2015 *)
CoefficientList[Series[Exp[(1 + x)/((-1 + x) x)] (1 + x) Gamma[0, (1 + x)/((-1 + x) x)]/((-1 + x) x), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 11 2018 *)
RecurrenceTable[{a[n] == (n + 1) a[n - 1] - (n - 2) a[n - 2] - (n - 5) a[n - 3] + (n - 3) a[n - 4], a[0] == a[1] == 1, a[2] == a[3] == 0}, a, {n, 0, 20}] (* Eric W. Weisstein, Apr 11 2018 *)
  • 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 */
  • Python
    from math import factorial, comb
def A002464(n): return factorial(n)+sum((-1 if k&1 else 1)*factorial(n-k)*sum(comb(k-1,t-1)*comb(n-k,t)<Chai Wah Wu, Feb 19 2024

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) - 88/(9*n^6) + 5336/(105*n^7) + 1612/(3*n^8) + 2098234/(567*n^9) + 36500686/(1575*n^10) + ... )/e^2. - Vaclav Kotesovec, Apr 19 2011, extended Dec 27 2020
Conjecture: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. - John Keith, Nov 02 2020
Proof: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. Since a(n) = Sum_{k=0..n-1} (-1)^k*(n-k)!*Sum_{i=0..k} binomial(n-k,i)*binomial(n-1-i,k-i) (M. Abramson and W. Moser, 1966) which is Sum_{k=1..n} (-1)^(k-1)(n-k+1)!*Sum{i=0..k-1} binomial(n-k+1,i)*binomial(n-1-i,k-1-i) = Sum_{k=1..n} (-1)^(n-k)(k!)*Sum_{i=0..n-k} binomial(k,i)*binomial(n-1-i,n-k-i) = k!*A080246(n-1, k-1) as (-1)^(n-k) = (-1)^(n+k) and binomial(n-1-i,k-1) = binomial(n-1-i,n-k-i). - Alex McGaw, Apr 13 2023
a(n+2) = (n+2)! - Sum_{j=0..n} (-1)^j*(n+1-j)!*2*A104698(n, j), for n >= 0 (Abramson and Moser, p. 1250, (III), N_0(n+2), last line, rewritten). - Wolfdieter Lang, May 14 2025

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
Edited by Jon E. Schoenfield, Jan 31 2015

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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