src/HOL/Binomial.thy
changeset 71720 1d8a1f727879
parent 71699 8e5c20e4e11a
child 72302 d7d90ed4c74e
equal deleted inserted replaced
71699:8e5c20e4e11a 71720:1d8a1f727879
  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)