Metamath Proof Explorer


Theorem hashrepr

Description: Develop the number of representations of an integer M as a sum of nonnegative integers in set A . (Contributed by Thierry Arnoux, 14-Dec-2021)

Ref Expression
Hypotheses hashrepr.a ( 𝜑𝐴 ⊆ ℕ )
hashrepr.m ( 𝜑𝑀 ∈ ℕ0 )
hashrepr.s ( 𝜑𝑆 ∈ ℕ0 )
Assertion hashrepr ( 𝜑 → ( ♯ ‘ ( 𝐴 ( repr ‘ 𝑆 ) 𝑀 ) ) = Σ 𝑐 ∈ ( ℕ ( repr ‘ 𝑆 ) 𝑀 ) ∏ 𝑎 ∈ ( 0 ..^ 𝑆 ) ( ( ( 𝟭 ‘ ℕ ) ‘ 𝐴 ) ‘ ( 𝑐𝑎 ) ) )

Proof

Step Hyp Ref Expression
1 hashrepr.a ( 𝜑𝐴 ⊆ ℕ )
2 hashrepr.m ( 𝜑𝑀 ∈ ℕ0 )
3 hashrepr.s ( 𝜑𝑆 ∈ ℕ0 )
4 2 nn0zd ( 𝜑𝑀 ∈ ℤ )
5 fzfid ( 𝜑 → ( 1 ... 𝑀 ) ∈ Fin )
6 fz1ssnn ( 1 ... 𝑀 ) ⊆ ℕ
7 6 a1i ( 𝜑 → ( 1 ... 𝑀 ) ⊆ ℕ )
8 1 4 3 5 7 hashreprin ( 𝜑 → ( ♯ ‘ ( ( 𝐴 ∩ ( 1 ... 𝑀 ) ) ( repr ‘ 𝑆 ) 𝑀 ) ) = Σ 𝑐 ∈ ( ( 1 ... 𝑀 ) ( repr ‘ 𝑆 ) 𝑀 ) ∏ 𝑎 ∈ ( 0 ..^ 𝑆 ) ( ( ( 𝟭 ‘ ℕ ) ‘ 𝐴 ) ‘ ( 𝑐𝑎 ) ) )
9 2 3 1 reprinfz1 ( 𝜑 → ( 𝐴 ( repr ‘ 𝑆 ) 𝑀 ) = ( ( 𝐴 ∩ ( 1 ... 𝑀 ) ) ( repr ‘ 𝑆 ) 𝑀 ) )
10 9 fveq2d ( 𝜑 → ( ♯ ‘ ( 𝐴 ( repr ‘ 𝑆 ) 𝑀 ) ) = ( ♯ ‘ ( ( 𝐴 ∩ ( 1 ... 𝑀 ) ) ( repr ‘ 𝑆 ) 𝑀 ) ) )
11 2 3 reprfz1 ( 𝜑 → ( ℕ ( repr ‘ 𝑆 ) 𝑀 ) = ( ( 1 ... 𝑀 ) ( repr ‘ 𝑆 ) 𝑀 ) )
12 11 sumeq1d ( 𝜑 → Σ 𝑐 ∈ ( ℕ ( repr ‘ 𝑆 ) 𝑀 ) ∏ 𝑎 ∈ ( 0 ..^ 𝑆 ) ( ( ( 𝟭 ‘ ℕ ) ‘ 𝐴 ) ‘ ( 𝑐𝑎 ) ) = Σ 𝑐 ∈ ( ( 1 ... 𝑀 ) ( repr ‘ 𝑆 ) 𝑀 ) ∏ 𝑎 ∈ ( 0 ..^ 𝑆 ) ( ( ( 𝟭 ‘ ℕ ) ‘ 𝐴 ) ‘ ( 𝑐𝑎 ) ) )
13 8 10 12 3eqtr4d ( 𝜑 → ( ♯ ‘ ( 𝐴 ( repr ‘ 𝑆 ) 𝑀 ) ) = Σ 𝑐 ∈ ( ℕ ( repr ‘ 𝑆 ) 𝑀 ) ∏ 𝑎 ∈ ( 0 ..^ 𝑆 ) ( ( ( 𝟭 ‘ ℕ ) ‘ 𝐴 ) ‘ ( 𝑐𝑎 ) ) )