A180564 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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