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,5

Comments

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

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

Links

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

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.

Example

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

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 *)

Crossrefs

Cf. A000142, A000166, A180196, A184181.

Sequence in context: A305785 A367387 A185089 * A113822 A036250 A191491

Adjacent sequences: A180561 A180562 A180563 * A180565 A180566 A180567

Keyword

nonn

Author

Emeric Deutsch, Sep 09 2010

Extensions

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

Status

approved