|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
|
|
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:
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|