login
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.
2
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
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Sep 09 2010
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Feb 17 2024
STATUS
approved