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> |