src/HOL/Library/Permutations.thy
changeset 67399 eab6ce8368fa
parent 66486 ffaaa83543b2
child 67408 4a4c14b24800
equal deleted inserted replaced
67398:5eb932e604a2 67399:eab6ce8368fa
  1259   assumes q: "q permutes S"
  1259   assumes q: "q permutes S"
  1260   shows "sum f {p. p permutes S} = sum (\<lambda>p. f(q \<circ> p)) {p. p permutes S}"
  1260   shows "sum f {p. p permutes S} = sum (\<lambda>p. f(q \<circ> p)) {p. p permutes S}"
  1261   (is "?lhs = ?rhs")
  1261   (is "?lhs = ?rhs")
  1262 proof -
  1262 proof -
  1263   let ?S = "{p. p permutes S}"
  1263   let ?S = "{p. p permutes S}"
  1264   have *: "?rhs = sum (f \<circ> (op \<circ> q)) ?S"
  1264   have *: "?rhs = sum (f \<circ> ((\<circ>) q)) ?S"
  1265     by (simp add: o_def)
  1265     by (simp add: o_def)
  1266   have **: "inj_on (op \<circ> q) ?S"
  1266   have **: "inj_on ((\<circ>) q) ?S"
  1267   proof (auto simp add: inj_on_def)
  1267   proof (auto simp add: inj_on_def)
  1268     fix p r
  1268     fix p r
  1269     assume "p permutes S"
  1269     assume "p permutes S"
  1270       and r: "r permutes S"
  1270       and r: "r permutes S"
  1271       and rp: "q \<circ> p = q \<circ> r"
  1271       and rp: "q \<circ> p = q \<circ> r"
  1272     then have "inv q \<circ> q \<circ> p = inv q \<circ> q \<circ> r"
  1272     then have "inv q \<circ> q \<circ> p = inv q \<circ> q \<circ> r"
  1273       by (simp add: comp_assoc)
  1273       by (simp add: comp_assoc)
  1274     with permutes_inj[OF q, unfolded inj_iff] show "p = r"
  1274     with permutes_inj[OF q, unfolded inj_iff] show "p = r"
  1275       by simp
  1275       by simp
  1276   qed
  1276   qed
  1277   have "(op \<circ> q) ` ?S = ?S"
  1277   have "((\<circ>) q) ` ?S = ?S"
  1278     using image_compose_permutations_left[OF q] by auto
  1278     using image_compose_permutations_left[OF q] by auto
  1279   with * sum.reindex[OF **, of f] show ?thesis
  1279   with * sum.reindex[OF **, of f] show ?thesis
  1280     by (simp only:)
  1280     by (simp only:)
  1281 qed
  1281 qed
  1282 
  1282