Theorem ballotlemfg

Description: Express the value of ( FC ) in terms of .^ . (Contributed by Thierry Arnoux, 21-Apr-2017)

	Ref	Expression
Hypotheses	ballotth.m	⊢ 𝑀 ∈ ℕ
	ballotth.n	⊢ 𝑁 ∈ ℕ
	ballotth.o	⊢ 𝑂 = { 𝑐 ∈ 𝒫 ( 1 ... ( 𝑀 + 𝑁 ) ) ∣ ( ♯ ‘ 𝑐 ) = 𝑀 }
	ballotth.p	⊢ 𝑃 = ( 𝑥 ∈ 𝒫 𝑂 ↦ ( ( ♯ ‘ 𝑥 ) / ( ♯ ‘ 𝑂 ) ) )
	ballotth.f	⊢ 𝐹 = ( 𝑐 ∈ 𝑂 ↦ ( 𝑖 ∈ ℤ ↦ ( ( ♯ ‘ ( ( 1 ... 𝑖 ) ∩ 𝑐 ) ) − ( ♯ ‘ ( ( 1 ... 𝑖 ) ∖ 𝑐 ) ) ) ) )
	ballotth.e	⊢ 𝐸 = { 𝑐 ∈ 𝑂 ∣ ∀ 𝑖 ∈ ( 1 ... ( 𝑀 + 𝑁 ) ) 0 < ( ( 𝐹 ‘ 𝑐 ) ‘ 𝑖 ) }
	ballotth.mgtn	⊢ 𝑁 < 𝑀
	ballotth.i	⊢ 𝐼 = ( 𝑐 ∈ ( 𝑂 ∖ 𝐸 ) ↦ inf ( { 𝑘 ∈ ( 1 ... ( 𝑀 + 𝑁 ) ) ∣ ( ( 𝐹 ‘ 𝑐 ) ‘ 𝑘 ) = 0 } , ℝ , < ) )
	ballotth.s	⊢ 𝑆 = ( 𝑐 ∈ ( 𝑂 ∖ 𝐸 ) ↦ ( 𝑖 ∈ ( 1 ... ( 𝑀 + 𝑁 ) ) ↦ if ( 𝑖 ≤ ( 𝐼 ‘ 𝑐 ) , ( ( ( 𝐼 ‘ 𝑐 ) + 1 ) − 𝑖 ) , 𝑖 ) ) )
	ballotth.r	⊢ 𝑅 = ( 𝑐 ∈ ( 𝑂 ∖ 𝐸 ) ↦ ( ( 𝑆 ‘ 𝑐 ) “ 𝑐 ) )
	ballotlemg	⊢ ↑ = ( 𝑢 ∈ Fin , 𝑣 ∈ Fin ↦ ( ( ♯ ‘ ( 𝑣 ∩ 𝑢 ) ) − ( ♯ ‘ ( 𝑣 ∖ 𝑢 ) ) ) )
Assertion	ballotlemfg	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → ( ( 𝐹 ‘ 𝐶 ) ‘ 𝐽 ) = ( 𝐶 ↑ ( 1 ... 𝐽 ) ) )

Proof

Step	Hyp	Ref	Expression
1		ballotth.m	⊢ 𝑀 ∈ ℕ
2		ballotth.n	⊢ 𝑁 ∈ ℕ
3		ballotth.o	⊢ 𝑂 = { 𝑐 ∈ 𝒫 ( 1 ... ( 𝑀 + 𝑁 ) ) ∣ ( ♯ ‘ 𝑐 ) = 𝑀 }
4		ballotth.p	⊢ 𝑃 = ( 𝑥 ∈ 𝒫 𝑂 ↦ ( ( ♯ ‘ 𝑥 ) / ( ♯ ‘ 𝑂 ) ) )
5		ballotth.f	⊢ 𝐹 = ( 𝑐 ∈ 𝑂 ↦ ( 𝑖 ∈ ℤ ↦ ( ( ♯ ‘ ( ( 1 ... 𝑖 ) ∩ 𝑐 ) ) − ( ♯ ‘ ( ( 1 ... 𝑖 ) ∖ 𝑐 ) ) ) ) )
6		ballotth.e	⊢ 𝐸 = { 𝑐 ∈ 𝑂 ∣ ∀ 𝑖 ∈ ( 1 ... ( 𝑀 + 𝑁 ) ) 0 < ( ( 𝐹 ‘ 𝑐 ) ‘ 𝑖 ) }
7		ballotth.mgtn	⊢ 𝑁 < 𝑀
8		ballotth.i	⊢ 𝐼 = ( 𝑐 ∈ ( 𝑂 ∖ 𝐸 ) ↦ inf ( { 𝑘 ∈ ( 1 ... ( 𝑀 + 𝑁 ) ) ∣ ( ( 𝐹 ‘ 𝑐 ) ‘ 𝑘 ) = 0 } , ℝ , < ) )
9		ballotth.s	⊢ 𝑆 = ( 𝑐 ∈ ( 𝑂 ∖ 𝐸 ) ↦ ( 𝑖 ∈ ( 1 ... ( 𝑀 + 𝑁 ) ) ↦ if ( 𝑖 ≤ ( 𝐼 ‘ 𝑐 ) , ( ( ( 𝐼 ‘ 𝑐 ) + 1 ) − 𝑖 ) , 𝑖 ) ) )
10		ballotth.r	⊢ 𝑅 = ( 𝑐 ∈ ( 𝑂 ∖ 𝐸 ) ↦ ( ( 𝑆 ‘ 𝑐 ) “ 𝑐 ) )
11		ballotlemg	⊢ ↑ = ( 𝑢 ∈ Fin , 𝑣 ∈ Fin ↦ ( ( ♯ ‘ ( 𝑣 ∩ 𝑢 ) ) − ( ♯ ‘ ( 𝑣 ∖ 𝑢 ) ) ) )
12		eldifi	⊢ ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) → 𝐶 ∈ 𝑂 )
13	12	adantr	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → 𝐶 ∈ 𝑂 )
14		elfzelz	⊢ ( 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) → 𝐽 ∈ ℤ )
15	14	adantl	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → 𝐽 ∈ ℤ )
16	1 2 3 4 5 13 15	ballotlemfval	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → ( ( 𝐹 ‘ 𝐶 ) ‘ 𝐽 ) = ( ( ♯ ‘ ( ( 1 ... 𝐽 ) ∩ 𝐶 ) ) − ( ♯ ‘ ( ( 1 ... 𝐽 ) ∖ 𝐶 ) ) ) )
17		fzfi	⊢ ( 1 ... ( 𝑀 + 𝑁 ) ) ∈ Fin
18	1 2 3	ballotlemelo	⊢ ( 𝐶 ∈ 𝑂 ↔ ( 𝐶 ⊆ ( 1 ... ( 𝑀 + 𝑁 ) ) ∧ ( ♯ ‘ 𝐶 ) = 𝑀 ) )
19	18	simplbi	⊢ ( 𝐶 ∈ 𝑂 → 𝐶 ⊆ ( 1 ... ( 𝑀 + 𝑁 ) ) )
20		ssfi	⊢ ( ( ( 1 ... ( 𝑀 + 𝑁 ) ) ∈ Fin ∧ 𝐶 ⊆ ( 1 ... ( 𝑀 + 𝑁 ) ) ) → 𝐶 ∈ Fin )
21	17 19 20	sylancr	⊢ ( 𝐶 ∈ 𝑂 → 𝐶 ∈ Fin )
22	13 21	syl	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → 𝐶 ∈ Fin )
23		fzfid	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → ( 1 ... 𝐽 ) ∈ Fin )
24	1 2 3 4 5 6 7 8 9 10 11	ballotlemgval	⊢ ( ( 𝐶 ∈ Fin ∧ ( 1 ... 𝐽 ) ∈ Fin ) → ( 𝐶 ↑ ( 1 ... 𝐽 ) ) = ( ( ♯ ‘ ( ( 1 ... 𝐽 ) ∩ 𝐶 ) ) − ( ♯ ‘ ( ( 1 ... 𝐽 ) ∖ 𝐶 ) ) ) )
25	22 23 24	syl2anc	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → ( 𝐶 ↑ ( 1 ... 𝐽 ) ) = ( ( ♯ ‘ ( ( 1 ... 𝐽 ) ∩ 𝐶 ) ) − ( ♯ ‘ ( ( 1 ... 𝐽 ) ∖ 𝐶 ) ) ) )
26	16 25	eqtr4d	⊢ ( ( 𝐶 ∈ ( 𝑂 ∖ 𝐸 ) ∧ 𝐽 ∈ ( 0 ... ( 𝑀 + 𝑁 ) ) ) → ( ( 𝐹 ‘ 𝐶 ) ‘ 𝐽 ) = ( 𝐶 ↑ ( 1 ... 𝐽 ) ) )