A184179 Number of permutations of {1,2,...,n} having no isolated fixed points. A fixed point j of a permutation is said to be isolated if neither j-1 nor j+1 is a fixed point. For example, 4135267 has only 3 as an isolated fixed point.

1, 0, 2, 3, 13, 56, 325, 2193, 17133, 151403, 1492804, 16236705, 193055170, 2490573878, 34643194357, 516777941500, 8228894996020, 139306002813141, 2498256515693495, 47311260905613040, 943450588439096803, 19760190063791826195, 433686706399407670577

Offset

0,3

Comments

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

Links

Table of n, a(n) for n=0..22.

Formula

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

Example

a(3)=3 because we have 123, 231, and 312. The permutations (1)32, 21(3), and 3(2)1 do have isolated fixed points (shown between parentheses).

Maple

d[0] := 1: d[1] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: add(d[n-j]*add(binomial(j-m-1, m-1)*binomial(n+1-j, m), m = 0 .. floor((1/2)*j)), j = 0 .. n) end proc: seq(a(n), n = 0 .. 22);

Crossrefs

Cf. A000166, A184178.

Sequence in context: A164511 A184256 A105050 * A100102 A208202 A206482

Adjacent sequences: A184176 A184177 A184178 * A184180 A184181 A184182

Keyword

nonn

Author

Emeric Deutsch, Feb 13 2011

Status

approved