1056 apply (auto simp add: algebra_simps) |
1056 apply (auto simp add: algebra_simps) |
1057 apply (metis fact_fact_dvd_fact dvd_trans nat_mult_dvd_cancel_disj) |
1057 apply (metis fact_fact_dvd_fact dvd_trans nat_mult_dvd_cancel_disj) |
1058 done |
1058 done |
1059 also have "\<dots> = |
1059 also have "\<dots> = |
1060 (fact (m + r + k) div (fact k * fact (m + r)) * (fact (m + r) div (fact r * fact m)))" |
1060 (fact (m + r + k) div (fact k * fact (m + r)) * (fact (m + r) div (fact r * fact m)))" |
1061 apply (subst div_mult_div_if_dvd) |
1061 by (auto simp: div_mult_div_if_dvd fact_fact_dvd_fact algebra_simps) |
1062 apply (auto simp: fact_fact_dvd_fact algebra_simps) |
|
1063 done |
|
1064 finally show ?thesis |
1062 finally show ?thesis |
1065 by (simp add: binomial_altdef_nat mult.commute) |
1063 by (simp add: binomial_altdef_nat mult.commute) |
1066 qed |
1064 qed |
1067 |
1065 |
1068 text \<open>The "Subset of a Subset" identity.\<close> |
1066 text \<open>The "Subset of a Subset" identity.\<close> |
1177 have 1: "xs \<noteq> [] \<Longrightarrow> x = hd xs \<Longrightarrow> x # tl xs = xs" for x :: nat and xs |
1175 have 1: "xs \<noteq> [] \<Longrightarrow> x = hd xs \<Longrightarrow> x # tl xs = xs" for x :: nat and xs |
1178 by simp |
1176 by simp |
1179 have 2: "xs \<noteq> [] \<Longrightarrow> sum_list(tl xs) = sum_list xs - hd xs" for xs :: "nat list" |
1177 have 2: "xs \<noteq> [] \<Longrightarrow> sum_list(tl xs) = sum_list xs - hd xs" for xs :: "nat list" |
1180 by (auto simp add: neq_Nil_conv) |
1178 by (auto simp add: neq_Nil_conv) |
1181 have f: "bij_betw ?f ?A ?A'" |
1179 have f: "bij_betw ?f ?A ?A'" |
1182 apply (rule bij_betw_byWitness[where f' = tl]) |
1180 by (rule bij_betw_byWitness[where f' = tl]) (use assms in \<open>auto simp: 2 1 simp flip: length_0_conv\<close>) |
1183 using assms |
|
1184 apply (auto simp: 2 length_0_conv[symmetric] 1 simp del: length_0_conv) |
|
1185 done |
|
1186 have 3: "xs \<noteq> [] \<Longrightarrow> hd xs + (sum_list xs - hd xs) = sum_list xs" for xs :: "nat list" |
1181 have 3: "xs \<noteq> [] \<Longrightarrow> hd xs + (sum_list xs - hd xs) = sum_list xs" for xs :: "nat list" |
1187 by (metis 1 sum_list_simps(2) 2) |
1182 by (metis 1 sum_list_simps(2) 2) |
1188 have g: "bij_betw ?g ?B ?B'" |
1183 have g: "bij_betw ?g ?B ?B'" |
1189 apply (rule bij_betw_byWitness[where f' = "\<lambda>l. (hd l - 1) # tl l"]) |
1184 apply (rule bij_betw_byWitness[where f' = "\<lambda>l. (hd l - 1) # tl l"]) |
1190 using assms |
1185 using assms |
1191 by (auto simp: 2 length_0_conv[symmetric] intro!: 3 |
1186 by (auto simp: 2 simp flip: length_0_conv intro!: 3) |
1192 simp del: length_greater_0_conv length_0_conv) |
|
1193 have fin: "finite {xs. size xs = M \<and> set xs \<subseteq> {0..<N}}" for M N :: nat |
1187 have fin: "finite {xs. size xs = M \<and> set xs \<subseteq> {0..<N}}" for M N :: nat |
1194 using finite_lists_length_eq[OF finite_atLeastLessThan] conj_commute by auto |
1188 using finite_lists_length_eq[OF finite_atLeastLessThan] conj_commute by auto |
1195 have fin_A: "finite ?A" using fin[of _ "N+1"] |
1189 have fin_A: "finite ?A" using fin[of _ "N+1"] |
1196 by (intro finite_subset[where ?A = "?A" and ?B = "{xs. size xs = m - 1 \<and> set xs \<subseteq> {0..<N+1}}"]) |
1190 by (intro finite_subset[where ?A = "?A" and ?B = "{xs. size xs = m - 1 \<and> set xs \<subseteq> {0..<N+1}}"]) |
1197 (auto simp: member_le_sum_list less_Suc_eq_le) |
1191 (auto simp: member_le_sum_list less_Suc_eq_le) |