418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงการจัด/เฉลยข้อ 4

ข้อ 1

เนื่องจากเลข 0 ทุกตัวจะต้องมี 1 ตามหลังอยู่ 1 ตัว เราสามารถแ่บ่งบิตสตริงออกเป็นช่วงๆ ได้ดังนี้

__ 01 __ 01 __ 01 __ 01 __ 01 __ 01 __ 01 __ 01 __

โดยที่ช่องว่าง __ แต่ละช่องสามารถบรรจุเลข 1 ที่เหลืออีก 2 ตัวได้อยู่

ดังนั้นมีบิตสตริงตามเงื่อนไขทั้งหมดเท่ากับวิธีกระจายเลข 1 ที่เหลือ 2 ตัวลงในช่องว่างทั้งหมด 9่ ช่อง ซึ่งมีอยู่ทั้งหมด ${9+2-1 \choose 2}={10 \choose 2}=45\,$ วิธี

ข้อ 2

เนื่องจากเลข 0 ทุกตัวจะต้องมี 2 ตามหลังอยู่ 1 ตัว เราสามารถแ่บ่งบิตสตริงออกเป็นช่วงๆ ได้ดังนี้

__ 011 __ 011 __ 011 __ 011 __ 011 __

โดยที่ช่องว่าง __ แต่ละช่องสามารถบรรจุเลข 1 ที่เหลืออีก 4 ตัวได้อยู่

ดังนั้นมีบิตสตริงตามเงื่อนไขทั้งหมดเท่ากับวิธีกระจายเลข 1 ที่เหลือ 4 ตัวลงในช่องว่างทั้งหมด 6่ ช่อง ซึ่งมีอยู่ทั้งหมด ${6+4-1 \choose 4}={9 \choose 4}=126\,$ วิธี

ข้อ 3

บิตสตริงที่มีเลข 0 อย่างน้อย 3 ตัวและเลข 1 อย่างน้อย 3 ตัวสามารถแบ่งออกได้เป็้น 5 กรณี ดังไปนี้

1. มีเลข 0 อยู่ 3 ตัวและมีเลข 1 อยู่ 7 ตัว ในกรณีนี้มีทั้งหมด ${10 \choose 3}=120$ ตัว
2. มีเลข 0 อยู่ 4 ตัวและมีเลข 1 อยู่ 6 ตัว ในกรณีนี้มีทั้งหมด ${10 \choose 4}=210$ ตัว
3. มีเลข 0 อยู่ 5 ตัวและมีเลข 1 อยู่ 5 ตัว ในกรณีนี้มีทั้งหมด ${10 \choose 5}=252$ ตัว
4. มีเลข 0 อยู่ 6 ตัวและมีเลข 1 อยู่ 4 ตัว ในกรณีนี้มีทั้งหมด ${10 \choose 6}=210$ ตัว
5. มีเลข 0 อยู่ 7 ตัวและมีเลข 1 อยู่ 3 ตัว ในกรณีนี้มีทั้งหมด ${10 \choose 7}=120$ ตัว

ดังนั้นมีบิตสตริงตามที่โจทย์ต้องการอยู่ทั้งหมด 912 ตัว