src/HOL/Library/Permutations.thy
changeset 59730 b7c394c7a619
parent 59669 de7792ea4090
child 60500 903bb1495239
equal deleted inserted replaced
59669:de7792ea4090 59730:b7c394c7a619
   188     have Fs: "card F = n - 1"
   188     have Fs: "card F = n - 1"
   189       using `x \<notin> F` H0 `finite F` by auto
   189       using `x \<notin> F` H0 `finite F` by auto
   190     from insert.hyps Fs have pFs: "card ?pF = fact (n - 1)"
   190     from insert.hyps Fs have pFs: "card ?pF = fact (n - 1)"
   191       using `finite F` by auto
   191       using `finite F` by auto
   192     then have "finite ?pF"
   192     then have "finite ?pF"
   193       using fact_gt_zero_nat by (auto intro: card_ge_0_finite)
   193       by (auto intro: card_ge_0_finite)
   194     then have pF'f: "finite ?pF'"
   194     then have pF'f: "finite ?pF'"
   195       using H0 `finite F`
   195       using H0 `finite F`
   196       apply (simp only: Collect_split Collect_mem_eq)
   196       apply (simp only: Collect_split Collect_mem_eq)
   197       apply (rule finite_cartesian_product)
   197       apply (rule finite_cartesian_product)
   198       apply simp_all
   198       apply simp_all
   256 qed
   256 qed
   257 
   257 
   258 lemma finite_permutations:
   258 lemma finite_permutations:
   259   assumes fS: "finite S"
   259   assumes fS: "finite S"
   260   shows "finite {p. p permutes S}"
   260   shows "finite {p. p permutes S}"
   261   using card_permutations[OF refl fS] fact_gt_zero_nat
   261   using card_permutations[OF refl fS] 
   262   by (auto intro: card_ge_0_finite)
   262   by (auto intro: card_ge_0_finite)
   263 
   263 
   264 
   264 
   265 subsection {* Permutations of index set for iterated operations *}
   265 subsection {* Permutations of index set for iterated operations *}
   266 
   266 
   277   moreover from `p permutes S` have "p ` S = S"
   277   moreover from `p permutes S` have "p ` S = S"
   278     by (rule permutes_image)
   278     by (rule permutes_image)
   279   ultimately show ?thesis
   279   ultimately show ?thesis
   280     by simp
   280     by simp
   281 qed
   281 qed
   282 
       
   283 lemma setsum_permute:
       
   284   assumes "p permutes S"
       
   285   shows "setsum f S = setsum (f \<circ> p) S"
       
   286   using assms by (fact setsum.permute)
       
   287 
       
   288 lemma setsum_permute_natseg:
       
   289   assumes pS: "p permutes {m .. n}"
       
   290   shows "setsum f {m .. n} = setsum (f \<circ> p) {m .. n}"
       
   291   using setsum_permute [OF pS, of f ] pS by blast
       
   292 
       
   293 lemma setprod_permute:
       
   294   assumes "p permutes S"
       
   295   shows "setprod f S = setprod (f \<circ> p) S"
       
   296   using assms by (fact setprod.permute)
       
   297 
       
   298 lemma setprod_permute_natseg:
       
   299   assumes pS: "p permutes {m .. n}"
       
   300   shows "setprod f {m .. n} = setprod (f \<circ> p) {m .. n}"
       
   301   using setprod_permute [OF pS, of f ] pS by blast
       
   302 
   282 
   303 
   283 
   304 subsection {* Various combinations of transpositions with 2, 1 and 0 common elements *}
   284 subsection {* Various combinations of transpositions with 2, 1 and 0 common elements *}
   305 
   285 
   306 lemma swap_id_common:" a \<noteq> c \<Longrightarrow> b \<noteq> c \<Longrightarrow>
   286 lemma swap_id_common:" a \<noteq> c \<Longrightarrow> b \<noteq> c \<Longrightarrow>