login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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).
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
Sequence in context: A164511 A184256 A105050 * A100102 A208202 A206482
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Feb 13 2011
STATUS
approved