การเรียงสับเปลี่ยนที่เลือกซ้ำได้
การเรียงสับเปลี่ยนที่เลือกซ้ำได้คล้ายกับการเรียงสับเปลี่ยนโดยเลือกมาบางส่วนทั่วไป ต่างกันเพียงยอมให้สมาชิกจากเซต M ที่ใช้เลือกซ้ำกันได้
บทนิยามและสูตร
เริ่มจากตัวอย่างทั่วไป จากตัวอักษรภาษาอังกฤษ (abc … xyz ซึ่งมี 26 ตัว) จะสร้างคำที่ยาว 6 ตัวอักษรได้กี่คำที่แตกต่างกัน หกตัวอักษรไม่มากนัก แต่จำนวนคำจะมากพอสมควร ที่นี่ไม่สนใจความหมายของคำ ดังนั้น “weqrww” ก็นับเป็นคำยาวหกตัวอักษรที่ใช้ได้
การคำนวณใช้เพียงหลักการคูณ มีตัวอักษรที่แตกต่างกันให้ใช้ทั้งหมด 26 ตัว ตำแหน่งแรกจึงใส่ตัวอักษรได้ 26 ตัว ตำแหน่งที่สองก็ใส่ได้ 26 ตัวเช่นกัน เพราะไม่ได้กำหนดว่าตัวอักษรห้ามซ้ำ ดังนั้นทุกตำแหน่งเลือกจากตัวอักษร 26 ตัว และตามหลักการคูณ จำนวนการเรียงสับเปลี่ยนทั้งหมดคือ 266 = 308,915,776 ซึ่งถือว่ามากทีเดียวเมื่อใช้ตัวอักษรเพียง 26 ตัว
การเรียงสับเปลี่ยนที่เลือกซ้ำได้ของสิ่งของ k สิ่งจากเซต M ที่มีสมาชิก n ตัว คือ k สิ่งอันดับใด ๆ ที่มีสมาชิกมาจากเซต M และสมาชิกแต่ละตัวปรากฏใน k สิ่งอันดับได้ถึง k ครั้ง ดังนั้นถ้ามีเซต M = {1, 2, 3} สี่สิ่งอันดับต่อไปนี้เป็นการเรียงสับเปลี่ยนที่เลือกซ้ำได้ทั้งหมด (1, 1, 1, 1) (1, 2, 3, 1) และ (2, 2, 3, 3) จำนวนการเรียงสับเปลี่ยนที่เลือกซ้ำได้ลักษณะนี้เท่ากับ:
ตัวอย่างพร้อมวิธีทำ
-
จากเลขโดด {2, 4, 6, 8} จะสร้างจำนวนหกหลักได้กี่จำนวน ถ้าเลขโดดซ้ำกันได้ เพียงแทนค่าลงในสูตร เซตมีสมาชิก 4 ตัว และเลือกหกสิ่งอันดับ:
-
คอมพิวเตอร์ใช้ระบบเลขฐานสองเป็นปกติ คือระบบที่ใช้เลขโดดเพียง 0 และ 1 ในระบบนี้มีหน่วยเฉพาะ เช่น หนึ่งบิต (bit) เปรียบเหมือนช่องหนึ่งช่องที่เก็บได้เพียงศูนย์หรือหนึ่ง หน่วยที่ใหญ่กว่าคือไบต์ (byte) ซึ่งประกอบด้วย 8 บิต ดังนั้น 1 คือหนึ่งบิต ส่วน 01110001 คือหนึ่งไบต์ จะเติมบิต 8 บิตลงในหนึ่งไบต์ได้กี่แบบที่แตกต่างกัน
เลือกจากเซต {0, 1} ซึ่งมีสมาชิกสองตัว และเลือก k สิ่งอันดับที่ k = 8 จำนวนแบบทั้งหมดจึงเท่ากับ:
-
จากตัวอย่างก่อนหน้า หนึ่งไบต์แยกค่าที่แตกต่างกันได้ถึง 256 ค่า จะเติมข้อมูลลงใน 4 ไบต์ได้กี่แบบ
สี่ไบต์มี 4 × 8 = 32 บิต และยังคงเลือกจากเซตที่มีสมาชิก 2 ตัว ผลลัพธ์จึงเป็น:
จะเห็นว่าเพียงสี่ไบต์ก็แยกค่าได้มากกว่าสี่พันล้านค่า เพื่อให้เห็นภาพ คอมพิวเตอร์ในปัจจุบันมีดิสก์ขนาดหลายร้อยกิกะไบต์หรือหลายเทราไบต์ หนึ่งเทราไบต์มี 1,000,000,000,000 ไบต์ จึงมี 8,000,000,000,000 บิต ดิสก์ขนาดหนึ่งเทราไบต์จึงเก็บค่าที่แตกต่างกันได้ถึง 28,000,000,000,000 ค่า
หมายเหตุ ปัจจุบันคำว่ากิโลไบต์ (เมกะไบต์ และอื่น ๆ) ยังสับสนกันอยู่บ้าง ด้วยเหตุผลทางเทคนิค หนึ่งกิโลไบต์เคยไม่ได้มี 1,000 ไบต์ตามธรรมเนียมของหน่วยอื่น (หนึ่งกิโลกรัมเท่ากับหนึ่งพันกรัม) แต่หนึ่งกิโลไบต์เท่ากับ 210 ไบต์ ซึ่งคือ 1024 ไบต์ และหนึ่งเมกะไบต์เท่ากับ 220 ไบต์ หรือ 210 กิโลไบต์
ในปัจจุบันจึงแยกการเขียนเป็นสองแบบ คือ 1 kB (อ่านว่ากิโลไบต์) เท่ากับ 1,000 ไบต์ และ 1 KiB (อ่านว่าคิบิไบต์) เท่ากับ 210 = 1024 ไบต์
-
ตัวอย่างเพิ่มเติมอยู่ในบทความแยกเรื่องความปลอดภัยของรหัสผ่าน
สารบัญ: คณิตศาสตร์เชิงการจัด, การเรียงสับเปลี่ยนโดยเลือกมาบางส่วน, การเรียงสับเปลี่ยน, การจัดหมู่, การเรียงสับเปลี่ยนที่เลือกซ้ำได้, การจัดหมู่ที่เลือกซ้ำได้, รหัส PIN ที่แตกต่างกันมีทั้งหมดกี่แบบ