全错排递推公式的简单推理_星河_风语的博客

设f(x)为全错排公式，
设g(x)为差一位的全错排公式

由
g(1)	a					=1	
		b
		
g(2)	a	b				=1
		b	c

g(3)	a	b	c			=3
		b	c	d
		c	d	b
		d	c 	b	
		
g(4)	a b c d				=3*g(3)+f(3)
		3*g(3)
		e*f(3)
		
得g(n) = (n-1)*g(n-1) + f(n-1)	n>=2

由
f(1)	a				=0

f(2) 	a	b			=1
		b	a

f(3)	a	b	c		=2
		b	a	c
		c	a	b
		
f(4)	a	b	c	d	=3*g(3)
		3*g(3)
得f(n) = (n-1)*g(n-1)			n>=2

综上	f(1) = 0
		f(2) = 1
		f(n) = (n-1)( f(n-1) + f(n-2) )		n>=3

设f(x)为全错排公式，
设g(x)为差一位的全错排公式

由
g(1)	a