login
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

%I #8 Nov 10 2019 20:26:15

%S 1,0,2,3,13,56,325,2193,17133,151403,1492804,16236705,193055170,

%T 2490573878,34643194357,516777941500,8228894996020,139306002813141,

%U 2498256515693495,47311260905613040,943450588439096803,19760190063791826195,433686706399407670577

%N 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.

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

%F 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.

%e 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).

%p 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);

%Y Cf. A000166, A184178.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Feb 13 2011