A180564 Number of permutations of [n] having no isolated entries. An entry j of a permutation p is isolated if it is not preceded by j-1 and not followed by j+1. For example, the permutation 23178564 has 2 isolated entries: 1 and 4.

1, 0, 1, 1, 2, 3, 7, 14, 35, 81, 216, 557, 1583, 4444, 13389, 40313, 128110, 409519, 1366479, 4603338, 16064047, 56708713, 206238116, 759535545, 2870002519, 10986716984, 43019064953, 170663829777, 690840124506, 2832976091771, 11831091960887, 50040503185030

Offset: 0

Author

Emeric Deutsch, Sep 09 2010

Keywords

• nonn

Comments

a(n) = A180196(n,0).

a(n) = n! - A184181(n).

Examples

			a(5)=3 because we have 12345, 34512, and 45123.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..893

Crossrefs

Cf. A000142, A000166, A180196, A184181.

Programs

Maple

d[ -1] := 0: d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-j-1, j-1)*(d[j]+d[j-1]), j = 1 .. floor((1/2)*n)) end proc:a(0):=1: seq(a(n), n = 0 .. 32);
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 0, 1, 1][n+1],
      (3*a(n-1)+(n-3)*a(n-2)-(n-3)*a(n-3)+(n-4)*a(n-4))/2)
    end:
seq(a(n), n=0..31);  # Alois P. Heinz, Feb 17 2024

Mathematica

a[n_] := If[n == 0, 1, With[{d = Subfactorial}, Sum[Binomial[n-j-1, j-1]* (d[j] + d[j-1]), {j, 1, Floor[n/2]}]]];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Sep 17 2024 *)

Formula

a(n) = Sum_{j=1..floor(n/2)} binomial(n-j-1, j-1)*(d(j) + d(j-1)), where d(i) = A000166(i) are the derangement numbers; a(0)=1.

Extensions

a(0)=1 prepended by Alois P. Heinz, Feb 17 2024