# 前言——为什么要写这篇文章

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 105
int a[N],vis[N],n,k;
long long ans;
void out(){
if(!k){
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}
void dfs(int dep){
if(dep==n+1){ans++;return ;}
for(int i=1;i<=n;i++){
if(!vis[i] && i!=dep){
vis[i]=1;
a[dep]=i;
dfs(dep+1);
vis[i]=0;
}
}
}
int main(){
k=0;
while(1){
cin>>n;
ans=0;
memset(vis,0,sizeof(vis));
if(n==0){cout<<0<<endl;continue;}
if(n==1){cout<<0<<endl;continue;}
dfs(1);
printf("所求n值为 %d 时的解个数: %lld \n",n,ans);
}
/*cin>>k;
for(int i=0;i<=k;i++){
n=i;
ans=0;
if(n==0){cout<<0<<endl;continue;}
if(n==1){cout<<0<<endl;continue;}
dfs(1);
printf("所求n值为 %d 时的解个数: %lld \n",n,ans);
}
*/
return 0;
}
/*

*/


1 4 9 44 265 1854 14833 133496 1334961

# BZOJ 4563:

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 454 Solved: 298

2
0 1
1 0

1

# RPG的错排

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 14066 Accepted Submission(s): 5733

Problem Description

Input

Sample Input

1
2
0


Sample Output

1
1


# 这并不是今天的重点

### 推导公式：

F(n)=(n-1)*(f(n-1)+f(n-2))


### 推导

F(1)=0

F(2)=1

1. 从中任取一个元素，不妨取1号元素，还剩n-1个元素，再从这n-1个元素对应的位置中选一个，共n-1种方法
2. 假设选取的位置是2号位，以下分两种情况

F[n]=(n-1)*(f[n-1]+f[n-2])

# Number of derangements

There are no approved revisions of this page, so it may not have been reviewed.

The number of (complete) derangements, or number of permutations with no rencontres[1] of distinct objects (i.e. the number of permutations of distinct objects with no fixed point) is given by the subfactorial of . The derangement numbers are given by the subfactorial numbers.

## Subfactorial numbers

A000166 Subfactorial or rencontres numbers,[2] or derangements: number of permutations of n elements with no fixed points.

The last digit (base 10) of seems to follow the pattern (of length 10)

## Example

You have 6 balls in 6 different colors, and for every ball you have a box of the same color. How many derangements do you have, if no ball is in a box of the same color?

## Comparison of derangement, permutation and arrangement numbers

Number of derangements Number of permutations Number of arrangements
0 1 1 1
1 0 1 2
2 1 2 5
3 2 6 16
4 9 24 65
5 44 120 326
6 265 720 1957
7 1854 5040 13700
8 14833 40320 109601
9 133496 362880 986410
10 1334961 3628800 9864101
11 14684570 39916800 108505112
12 176214841 479001600 1302061345
13 2290792932 6227020800 16926797486
14 32071101049 87178291200 236975164805
15 481066515734 1307674368000 3554627472076
16 7697064251745 20922789888000 56874039553217
17 130850092279664 355687428096000 966858672404690
18 2355301661033953 6402373705728000 17403456103284421
19 44750731559645106 121645100408832000 330665665962404000
20 895014631192902121 2432902008176640000 6613313319248080001

## Recurrences

Note that the factorial has a similar recurrence

So, for

## Other formulae

where (Cf. A001113) is Euler’s number and is the incomplete gamma function.

A very good approximation is given by

If rounded, you get a perfect formula for

If you add 1 to the factorial, before dividing, you can truncate instead of rounding to get a perfect formula for

0 1 0,3679 0 0,7358 0
1 0 0,3679 0 0,7358 0
2 1 0,7358 1 1,1036 1
3 2 2,2073 2 2,5752 2
4 9 8,8291 9 9,1970 9
5 44 44,1455 44 44,5134 44
6 265 264,8732 265 265,2411 265
7 1854 1854,1124 1854 1854,4803 1854
8 14833 14832,8991 14833 14833,2669 14833
9 133496 133496,0916 133496 133496,4595 133496

where is the round function and is the floor function.

There is a sequence (Cf. A000255) with the members , and the recursive rule:

With this sequence you can calculate the subfactorial

1 0 1 2 9 44 265 1854 14833 133496 1334961
0 1 2 3 4 5 6 7 8 9 10
1 1 3 11 53 309 2119 16687 148329 1468457 16019531

## Generating function

### Ordinary generating function

where is the exponential integral.

## Asymptotic behaviour

The limit of the quotient of factorial and subfactorial converges to (Cf. A001113 and Euler’s number)

Proof:

The limit of the quotient of the number of arrangements of any subset of distinct objects over the number of derangements of distinct objects converges to (Cf. A072334)

The geometric mean of the number of arrangements and the number of derangements is asymptotic to the number of permutations

## Permutations having at least one fixed point

The number of permutations having at least one fixed point, thus not being (complete) derangements is given by

where the second summation gives the empty sum (defined as the additive identity, i.e. 0) for .

## Sequences

The subfactorial numbers (or rencontres numbers, or derangements: number of permutations of elements with no fixed points) (Cf. A000166) are

(Cf. A000255) gives

The number of permutations of , having a fixed point (Cf. A002467) are