A134316 a(n) = index of first derangement of 1..n (n>=2).

2, 4, 8, 28, 128, 748, 5168, 41068, 368048, 3669868, 40284848, 482671468, 6267305648, 87660962668, 1313941673648, 21010450850668, 357001369769648, 6423384156578668, 122002101778601648, 2439325392333218668

Offset

2,1

Links

Table of n, a(n) for n=2..21.

Formula

a(0)=1, a(1)=2, a(n)=a(n-2)+(n-1)!; a(n)=a(n-1)=abs(A058006(n)).

Example

n=2: permutations are
per={{1,2},{2,1}},
per(2)={2,1} is the first derangement, hence a(2)=2;
n=3: permutations are
per={{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}},
per(3)= {2,1,3} is the first derangement, hence a(3)=2;
n=4: permutations are
per={{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,2,3},{1,4,3,2},{2,1,3,4},{2,1,4,3},{2,3,1,4},{2,3,4,1},{2,4,1,3},{2,4,3,1},{3,1,2,4},{3,1,4,2},{3,2,1,4},{3,2,4,1},{3,4,1,2},{3,4,2,1},{4,1,2,3},{4,1,3,2},{4,2,1,3},{4,2,3,1},{4,3,1,2},{4,3,2,1}},
per(8)= {2,1,4,3} is the first derangement, hence a(4)=8.

Mathematica

c[0]=1; c[1]=2; c[n_]:=c[n]=c[n-2]+(n-1)!; A1=Table[c[n], {n, 2, 20}]

Crossrefs

Cf. A058006.

Sequence in context: A034919 A298682 A151340 * A049461 A103791 A269569

Adjacent sequences: A134313 A134314 A134315 * A134317 A134318 A134319

Keyword

nonn

Author

Zak Seidov, Jan 16 2008

Status

approved