จำนวนคีย์ที่ไม่สมัครใจในรหัสเรียงสับเปลี่ยน

ฉันมาพร้อมกับปัญหาต่อไปนี้จาก ทฤษฎีและปฏิบัติ หนังสือของสตินสัน-แพตเตอร์สัน มันระบุต่อไปนี้:

2.17

(a) พิสูจน์ว่ามีการเปลี่ยนแปลง $\pi$ ใน Permutation Cipher คือ kei iff โดยไม่สมัครใจ (ถ้าและเฉพาะในกรณีที่) $\pi(i) = j$ หมายถึง $\pi(ญ) = > i$, สำหรับทุกอย่าง $i,j \in \{1,...,m \}$.

(b) กำหนดจำนวนของคีย์ที่ไม่เกี่ยวข้องใน การเปลี่ยนแปลง รหัส สำหรับ $m = 2,3,4,5, $ และ 6.

ฉันได้พิสูจน์ข้อแรกแล้ว โดยแสดงว่าดัชนีของ $x's$ และ $y's$ ยังคงเหมือนเดิม แต่ฉันไม่มีคำใบ้ในการพิจารณารายการที่สอง b นี่คือฉันไม่แน่ใจเกี่ยวกับบทบาทของคีย์ในรหัสประเภทนี้ การชี้แจงใด ๆ แน่นอนคำตอบเดียวที่ชัดเจนจะดี

การมีส่วนร่วมอยู่ในการติดต่อแบบหนึ่งต่อหนึ่งกับการเรียงสับเปลี่ยนผันตัวเอง (กล่าวคือ การเรียงสับเปลี่ยนที่เป็นการเปลี่ยนรูปผกผันของตัวเอง)

ซีรีส์ได้รับใน OEIS A000085.

เดอะ สูตร สำหรับจำนวนของการสลับสับเปลี่ยนที่เกี่ยวข้อง $n$ ตัวอักษรคือ;

$$I(n) = 1 + \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \frac{1}{(k+1)!} \prod_{i=0} ^k \binom{n-2i}{2}$$

การคำนวณด้วยมือเล็กน้อย

ประการแรก การเรียงสับเปลี่ยนตัวตน $\varepsilon$ มีส่วนร่วมอยู่เสมอ ที่นี่เราจะใช้ สัญกรณ์หนึ่งบรรทัด.

• $m = 2 $ แล้ว $\varepsilon = (1,2)$ และ $(2,1)$ เป็นการมีส่วนร่วม

• $m = 3 $ แล้ว $\varepsilon = (1,2,3)$, $(1,3,2)$,$(3,2,1)$, และ $(2,1,3)$ เป็นไปได้ 4 อย่าง

• $m = 4 $ แล้ว $\varepsilon = (1,2,3,4)$ และ

  • แก้ไขก่อน $(1,ก,ข,ค)$ จากนั้นเรามี 3 โดยกรณีก่อนหน้า $(1,2,4,3),(1,4,3,2),(1,3,2,4)$
  • แก้ไขที่สอง $(ก,2,ค,ง)$ แล้วเรามี 2 $(3,2,1,4),(4,2,3,1)$ (มีอยู่ในกรณีก่อนหน้านี้)
  • แก้ไขที่สาม $(ก,ข,3,ง)$ แล้วเรามี 1 $(2,1,3,4)$
  • แก้ไขที่สี่ $(ก,ข,ค,4)$ แล้วเรามี 0; ล้วนมีมาก่อน
  • แก้ไขสองครั้งแล้ว $(4,2,3,1)$
  • เพิ่มเป็นสองเท่า $(3, 4, 1, 2),(2,1,4,3)$

รหัส Sagemath สำหรับ 5

p = การเปลี่ยนแปลง ([1, 2,3,4,5])
สำหรับ i ในช่วง (0, แฟคทอเรียล (5)):
    ถ้า p == p.inverse():
        พิมพ์(หน้า)
    p = p.ถัดไป()

ด้วยเอาต์พุต

[1, 2, 3, 4, 5]
[1, 2, 3, 5, 4]
[1, 2, 4, 3, 5]
[1, 2, 5, 4, 3]
[1, 3, 2, 4, 5]
[1, 3, 2, 5, 4]
[1, 4, 3, 2, 5]
[1, 4, 5, 2, 3]
[1, 5, 3, 4, 2]
[1, 5, 4, 3, 2]
[2, 1, 3, 4, 5]
[2, 1, 3, 5, 4]
[2, 1, 4, 3, 5]
[2, 1, 5, 4, 3]
[3, 2, 1, 4, 5]
[3, 2, 1, 5, 4]
[3, 4, 1, 2, 5]
[3, 5, 1, 4, 2]
[4, 2, 3, 1, 5]
[4, 2, 5, 1, 3]
[4, 3, 2, 1, 5]
[4, 5, 3, 1, 2]
[5, 2, 3, 4, 1]
[5, 2, 4, 3, 1]
[5, 3, 2, 4, 1]
[5, 4, 3, 2, 1]