Theorem derangval

Description: Define the derangement function, which counts the number of bijections from a set to itself such that no element is mapped to itself. (Contributed by Mario Carneiro, 19-Jan-2015)

	Ref	Expression
Hypothesis	derang.d	⊢ 𝐷 = ( 𝑥 ∈ Fin ↦ ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) )
Assertion	derangval	⊢ ( 𝐴 ∈ Fin → ( 𝐷 ‘ 𝐴 ) = ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝐴 –1-1-onto→ 𝐴 ∧ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) )

Proof

Step	Hyp	Ref	Expression
1		derang.d	⊢ 𝐷 = ( 𝑥 ∈ Fin ↦ ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) )
2		f1oeq2	⊢ ( 𝑥 = 𝐴 → ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ↔ 𝑓 : 𝐴 –1-1-onto→ 𝑥 ) )
3		f1oeq3	⊢ ( 𝑥 = 𝐴 → ( 𝑓 : 𝐴 –1-1-onto→ 𝑥 ↔ 𝑓 : 𝐴 –1-1-onto→ 𝐴 ) )
4	2 3	bitrd	⊢ ( 𝑥 = 𝐴 → ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ↔ 𝑓 : 𝐴 –1-1-onto→ 𝐴 ) )
5		raleq	⊢ ( 𝑥 = 𝐴 → ( ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ↔ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) )
6	4 5	anbi12d	⊢ ( 𝑥 = 𝐴 → ( ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) ↔ ( 𝑓 : 𝐴 –1-1-onto→ 𝐴 ∧ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) ) )
7	6	abbidv	⊢ ( 𝑥 = 𝐴 → { 𝑓 ∣ ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } = { 𝑓 ∣ ( 𝑓 : 𝐴 –1-1-onto→ 𝐴 ∧ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } )
8	7	fveq2d	⊢ ( 𝑥 = 𝐴 → ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝑥 –1-1-onto→ 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) = ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝐴 –1-1-onto→ 𝐴 ∧ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) )
9		fvex	⊢ ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝐴 –1-1-onto→ 𝐴 ∧ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) ∈ V
10	8 1 9	fvmpt	⊢ ( 𝐴 ∈ Fin → ( 𝐷 ‘ 𝐴 ) = ( ♯ ‘ { 𝑓 ∣ ( 𝑓 : 𝐴 –1-1-onto→ 𝐴 ∧ ∀ 𝑦 ∈ 𝐴 ( 𝑓 ‘ 𝑦 ) ≠ 𝑦 ) } ) )