ปัญหา Combinatorics - $5$-digit code กับ $3,4,5$ นำเสนอ

Question

ฉันมีปัญหาเรื่องคอมบิเนเตอร์ที่ฉันกำลังดิ้นรน นี่คือ: "มีรหัส 5 หลักกี่หลักในแต่ละหลัก$3,4,5$?”

ฉันเข้าใจกลยุทธ์ทั่วไปซึ่งเราจะดูก่อนว่าเราจะอนุญาตได้อย่างไร $3,4,5$ กับช่องว่างอื่น ๆ ($\frac{5!}{2} = 60$ วิธี) แล้วเราคูณด้วย $10^2$ (ทั้งสองช่องอีกสองช่องสามารถมีไฟล์ $10$หลัก) อย่างไรก็ตามตอนนี้เราสิ้นสุดการนับสองครั้งเนื่องจากตัวเลขสองหลักอื่น ๆ บางส่วนจะเป็น$3,4,5$และจะส่งผลให้เกิดการผสมซ้ำระหว่างกัน ฉันกำลังดิ้นรนเพื่อหาสูตรสำหรับการยกเว้นสิ่งเหล่านี้

Answer 1

มีกลยุทธ์สองสามอย่างที่เราสามารถใช้ได้ที่นี่

วิธีที่ 1:พิจารณากรณีต่างๆขึ้นอยู่กับความถี่ที่ตัวเลขแต่ละตัวปรากฏ

กรณีที่ 1 : ตัวเลข$3$, $4$, $5$ แต่ละรายการจะปรากฏเพียงครั้งเดียว

เลือกหนึ่งในตำแหน่งสำหรับ $3$หนึ่งในสี่ตำแหน่งที่เหลือสำหรับ $4$และอีกหนึ่งในสามตำแหน่งที่เหลือสำหรับ $5$. จากนั้นแต่ละตำแหน่งที่เหลืออีกสองตำแหน่งอาจจะเต็มไปด้วยหนึ่งในตำแหน่งที่เหลือ$10 - 3 = 7$ตัวเลข ดังนั้นมี

$$5 \cdot 4 \cdot 3 \cdot 7^2$$

รหัสดังกล่าว

กรณีที่ 2 : หนึ่งในหลัก$3$, $4$, $5$ ปรากฏขึ้นสองครั้งและแต่ละรายการจะปรากฏเพียงครั้งเดียว

เลือกว่าตัวเลขใด $3$, $4$, $5$ปรากฏขึ้นสองครั้ง เลือกสองตำแหน่งสำหรับตัวเลขนั้น เลือกหนึ่งในสามตำแหน่งที่เหลือสำหรับตัวเลขสองหลักที่เหลือน้อยกว่าจากชุด$\{3, 4, 5\}$ และหนึ่งในสองตำแหน่งที่เหลือสำหรับตัวเลขที่เหลือจากเซต $\{3, 4, 5\}$. เลือกว่าตัวเลขเจ็ดหลักที่เหลือจะเติมตำแหน่งที่เหลือ มี

$$\binom{3}{1}\binom{5}{2}\cdot 3 \cdot 2 \cdot 7$$

รหัสดังกล่าว

กรณีที่ 3 : ตรงกับสองหลัก$3, 4, 5$ ปรากฏขึ้นสองครั้งและอีกรายการหนึ่งปรากฏขึ้นหนึ่งครั้ง

เลือกว่าตัวเลขสามหลักใด $3, 4, 5$ปรากฏขึ้นครั้งเดียว เลือกว่าตำแหน่งใดในห้าตำแหน่งที่เติมตัวเลข เลือกตำแหน่งที่เหลืออีกสองจากสี่ตำแหน่งที่เหลือสำหรับตำแหน่งที่เล็กกว่าของตัวเลขสองหลักที่เหลือจากชุด$\{3, 4, 5\}$จากนั้นเติมสองตำแหน่งที่เหลือด้วยตัวเลขที่เหลือจากชุด $\{3, 4, 5\}$. มี

$$\binom{3}{1}\binom{5}{1}\binom{4}{2}$$

รหัสดังกล่าว

กรณีที่ 4 : หนึ่งในสามหลัก$3, 4, 5$ปรากฏสามครั้งและแต่ละรายการจะปรากฏขึ้นหนึ่งครั้ง เลือกว่าตัวเลขสามหลักใดปรากฏขึ้นสามครั้งจากนั้นเลือกสามในห้าตำแหน่งสำหรับตัวเลขนั้น เลือกหนึ่งในสองตำแหน่งที่เหลือสำหรับตัวเลขที่เล็กกว่าที่เหลือจากชุด$\{3, 4, 5\}$จากนั้นเติมตำแหน่งสุดท้ายด้วยหลักอื่น ๆ มี

$$\binom{3}{1}\binom{5}{3}\binom{2}{1}$$

รหัสดังกล่าว

ทั้งหมด : เนื่องจากตำแหน่งเหล่านี้เป็นตำแหน่งพิเศษและครบถ้วนสมบูรณ์ให้เพิ่มกรณีข้างต้น

วิธีที่ 2:เราใช้หลักการรวม - ยกเว้น

มี $10^5$รหัส เราต้องการแยกออกจากตัวเลขเหล่านี้ซึ่งมีอย่างน้อยหนึ่งหลัก$3, 4, 5$ ที่ขาดหายไป.

เราเลือกว่าสามหลักใด $3, 4, 5$เพื่อไม่รวมซึ่งทำให้มีเก้าวิธีในการเติมแต่ละตำแหน่งทั้งห้า ดังนั้นเราจึงลบ

$$\binom{3}{1}9^5$$

จากทั้งหมด

อย่างไรก็ตามหากเราทำเช่นนั้นเราจะลบแต่ละกรณีซึ่งมีสองหลัก $3, 4, 5$หายไปสองครั้งในแต่ละวิธีเราสามารถกำหนดหนึ่งในหลักเหล่านั้นเป็นตัวเลขที่ขาดหายไป เราต้องการลบกรณีดังกล่าวเพียงครั้งเดียวดังนั้นเราจึงต้องบวกลงในผลรวม

เราเลือกสองในสามหลัก $3, 4, 5$ที่จะไม่รวมซึ่งทำให้เรามีแปดวิธีในการเติมตำแหน่งแต่ละตำแหน่งจากห้าตำแหน่ง ดังนั้นเราจึงเพิ่ม

$$\binom{3}{2}8^5$$

กับยอดรวมการวิ่งของเรา

อย่างไรก็ตามหากเราลบกรณีที่มีหนึ่งในหลักก่อน $3, 4, 5$ ถูกแยกออกจากนั้นเพิ่มกรณีที่มีตัวเลขสองหลัก $3, 4, 5$ ได้รับการยกเว้นเราจะไม่รวมกรณีเหล่านั้นซึ่งตัวเลขทั้งสามหลัก $3, 4, 5$ได้รับการยกเว้นเลย นี่เป็นเพราะเราลบมันสามครั้งครั้งแรกสำหรับแต่ละวิธีเราสามารถกำหนดหนึ่งในสามหลักนั้นเป็นตัวเลขที่ยกเว้นได้ จากนั้นเราได้เพิ่มกรณีเหล่านี้สามครั้งหนึ่งครั้งสำหรับแต่ละกรณี$\binom{3}{2}$วิธีที่เรากำหนดให้สองในสามหลักนั้นเป็นตัวเลขที่ยกเว้นได้ ดังนั้นเราต้องพวกเขาจากทั้งหมด

ถ้าทั้งสามหลัก $3, 4, 5$ได้รับการยกเว้นจากนั้นเรามีตัวเลือกเจ็ดตัวสำหรับแต่ละตำแหน่งจากห้าตำแหน่ง ดังนั้นจึงมี

$$\binom{3}{3}7^5$$

กรณีที่ตัวเลขทั้งหมด $3, 4, 5$ ได้รับการยกเว้น

ตามหลักการรวม - ยกเว้นมี

$$10^5 - \binom{3}{1}9^5 + \binom{3}{2}8^5 - \binom{3}{3}7^5$$

รหัสที่ยอมรับได้

ดังที่คุณตรวจสอบได้ทั้งสองวิธีให้คำตอบเดียวกัน