การจัดหมู่ที่เลือกซ้ำได้
การจัดหมู่ที่เลือกซ้ำได้คล้ายกับการจัดหมู่ทั่วไป ต่างกันเพียงยอมให้สมาชิกจากเซต M ที่ใช้เลือกซ้ำกันได้
บทนิยามและสูตร
เริ่มจากตัวอย่างที่เห็นภาพง่าย ไปร้านค้าเพื่อซื้อเครื่องดื่มขวด 12 ขวดไว้ดื่มระหว่างไปเข้าค่าย บนชั้นมีเครื่องดื่มขวดอยู่สี่ชนิด จึงเลือกซื้อได้หลายแบบ เช่น ซื้อน้ำส้ม 5 ขวด น้ำมะพร้าว 2 ขวด ชาเขียว 1 ขวด และโซดา 4 ขวด หรือซื้อทุกชนิดชนิดละ 3 ขวด จะซื้อเครื่องดื่มให้ได้ 12 ขวดพอดีได้ทั้งหมดกี่แบบที่แตกต่างกัน
ดังนั้นมีเซต M = {น้ำส้ม, น้ำมะพร้าว, ชาเขียว, โซดา} และคำถามคือ มี k สิ่งอันดับที่ k = 12 ซึ่งมีสมาชิกจากเซต M และลำดับไม่มีผลอยู่กี่แบบ
ที่มาของสูตรนี้ซับซ้อนกว่าโจทย์การนับแบบอื่นพอสมควร ขั้นแรกให้มองการซื้อของเป็นลำดับของ 0 และ 1 โดยจำนวน 1 แทนจำนวนขวดของเครื่องดื่มแต่ละชนิด และ 0 คั่นระหว่างชนิด ดังนั้น 111011101111101 หมายความว่าซื้อน้ำส้ม 3 ขวด (1 สามตัวแรก) แล้วน้ำมะพร้าว 3 ขวด (0 เป็นตัวคั่น ตามด้วย 1 อีกสามตัว) แล้วชาเขียว 5 ขวด (0 เป็นตัวคั่น ตามด้วย 1 ห้าตัว) และสุดท้ายโซดา 1 ขวด หลักการทั้งหมดแสดงได้ดังนี้:
ถ้าต้องการซื้อน้ำส้ม 6 ขวด น้ำมะพร้าว 4 ขวด โซดา 2 ขวด และไม่ซื้อชาเขียวเลย ลำดับจะเป็นดังนี้:
สังเกตว่าลำดับนี้ยาว 15 เสมอ เพราะต้องมี 1 อยู่ 12 ตัวจึงจะซื้อเครื่องดื่มครบ 12 ขวด และต้องมีตัวคั่น 3 ตัวเพื่อแยกเครื่องดื่มสี่ชนิด จึงเหลือเพียงหาว่าลำดับยาว 15 ที่มี 0 สามตัวพอดีมีทั้งหมดกี่แบบ
เพียงหาตำแหน่งของ 0 ก็พอ เมื่อวาง 0 สามตัวแทรกระหว่าง 1 สิบสองตัวแล้ว จะได้การเลือกเครื่องดื่มที่ใช้ได้แบบหนึ่ง กล่าวอีกอย่างหนึ่งคือ มีช่องทั้งหมด 15 ช่อง และต้องใส่ 0 ลงใน 3 ช่อง ช่องที่เหลือจะเป็น 1 โดยอัตโนมัติ
ถึงตรงนี้ก็เป็นโจทย์การจัดหมู่ที่เลือกซ้ำไม่ได้แบบง่ายแล้ว ให้ช่องทั้ง 15 ช่องมีหมายเลข {1, …, 15} แล้วเลือกตัวเลขครั้งละ 3 ตัวจากเซตนี้ จะได้ตำแหน่งสามตำแหน่งสำหรับวาง 0 เช่น การจัดหมู่ {2, 4, 7} ให้ลำดับ 101011011111111 คือตำแหน่งที่ 2 ที่ 4 และที่ 7 เป็น 0 ที่เหลือเป็น 1 ดังนั้นจำนวนวิธีที่แตกต่างกันในการวาง 0 ลงในช่อง 15 ช่องคือ:
ดังนั้นจึงซื้อเครื่องดื่ม 12 ขวดได้ 455 แบบที่แตกต่างกันเมื่อมีเครื่องดื่มสี่ชนิด
ขยายเหตุผลข้างต้นเป็นกรณีทั่วไปได้ ถ้ามีเซต M ที่มีสมาชิก n ตัว และเลือก k สิ่งอันดับโดยสมาชิกแต่ละตัวซ้ำกันได้ จะสร้างลำดับของ 0 และ 1 ที่ยาว n + k − 1 (k ตัวเป็น 1 และ n − 1 ตัวเป็น 0) แล้วหาว่าวาง 0 จำนวน n − 1 ตัวได้กี่แบบ ดังนั้นจำนวนการจัดหมู่ที่เลือกซ้ำได้ของสิ่งของ n ชนิด ครั้งละ k สิ่ง เท่ากับ:
การจัดรูปขั้นสุดท้ายทำได้เพราะความสัมพันธ์พื้นฐานของสัมประสิทธิ์ทวินาม
ตัวอย่างพร้อมวิธีทำ
- จะแจกบัตรเข้าชมฟรี 20 ใบสำหรับการแสดงลิเกรอบปฐมทัศน์ให้คุณยาย 10 คนได้กี่วิธี ข้อนี้เป็นการจัดหมู่ที่เลือกซ้ำได้ เพราะคุณยายคนหนึ่งอาจได้บัตรหลายใบ หรืออาจได้บัตรทั้งหมดก็ได้ เพียงต้องเข้าใจให้ถูกว่าอะไรคือ n และอะไรคือ k ที่จริงแล้วเป็นการจัดหมู่ครั้งละ 20 สิ่งจากคุณยาย 10 คน กล่าวอีกอย่างหนึ่งคือสร้างลำดับของ 0 และ 1 ที่ยาว 29 โดยมี 1 อยู่ 20 ตัวและ 0 อยู่ 9 ตัว ดังนั้น n = 10, k = 20 จะได้คำตอบ:
สารบัญ: คณิตศาสตร์เชิงการจัด, การเรียงสับเปลี่ยนโดยเลือกมาบางส่วน, การเรียงสับเปลี่ยน, การจัดหมู่, การเรียงสับเปลี่ยนที่เลือกซ้ำได้, การจัดหมู่ที่เลือกซ้ำได้, รหัส PIN ที่แตกต่างกันมีทั้งหมดกี่แบบ