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

ข้อ 1

มีจำนวนเต็มบวกที่มีตัวเลขอยู่ 4 ตัว (กล่าวคือจำนวนเต็มบวกที่อยู่ระหว่าง 1000 และ 9999) กี่ตัวที่

1. 9 หารลงตัว?
2. เป็นจำนวนคู่
3. 3 หารไม่ลงตัว?
4. 5 หรือ 7 หารลงตัว?
5. ทั้ง 5 และ 7 หารไม่ลงตัว?
6. 5 หรือ 7 หรือ 11 หารลงตัว?
7. 5 และ 7 หารลงตัวแต่ 11 หารไม่ลงตัว?

ข้อ 2

ในงานแต่งงานของคู่บ่าวสาวคู่หนึ่ง ช่างภาพจะทำการถ่ายภาพคน 6 คนจากกลุ่มคน 10 คน โดยที่กลุ่มคน 10 คนนี้รวมเจ้าบ่าวและเจ้าสาวอยู่ด้วย มีวิธีกี่วิธีที่เจ้าภาพจะจัดคนให้ยืนเรียงหน้ากระดานเพื่อถายรูปโดยที่

1. เจ้าสาวจะต้องอยู่ในรูป
2. ทั้งเจ้าสาวและเจ้าบ่าวจะต้องอยู่ในภาพ
3. เจ้าสาวหรือเจ้าบ่าวเพียงแค่คนเดียวเท่านั้นอยู่ในรูป
4. เจ้าสาวจะต้องอยู่ข้างเจ้าบ่าว
5. เจ้าสาวจะต้องไม่อยู่ติดกับเจ้าบ่าว
6. เจ้าสาวจะต้องยืนอยู่ทางด้านซ้ายของเจ้าบ่าว แต่ไม่จำเป็นต้องอยู่ติดกัน

ข้อ 3

ตัวอักษรภาษาอังกฤษมีพยัญชนะอยู่ 21 ตัวและมีสระอยู่ 5 ตัว

มีสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษตัวเลข กี่ตัวที่:

1. มีสระ 1 ตัว
2. มีสระ 2 ตัว
3. มีสระอย่างน้อย 1 ตัว
4. มีสระอย่างน้อย 2 ตัว
5. ไม่มีสระใดๆ ปรากฎมากกว่า 1 ครั้ง
6. ไม่มีตัวอักษรใดๆ ปรากฏมากกว่า 1 ครั้ง

ข้อ 4

1. มีบิตสตริงกี่ตัวที่ประกอบด้วยเลขศูนย์ 8 ตัวและเลขหนึ่ง 10 ตัวโดยที่เลขศูนย์ทุกตัวจะต้องมีเลขหนึ่งอยู่ทางด้านขวาของมันเสมอ
2. มีบิตสตริงกี่ตัวที่ประกอบด้วยเลขศูนย์ 5 ตัวและเลขหนึ่ง 14 ตัวโดยที่เลขศูนย์ทุกตัวจะต้องมีเลขหนึ่งอยู่ทางด้านขวาของมันอย่างน้อย 2 ตัวเสมอ
3. มีบิตสตริงกี่ความยาว 10 กี่ตัวที่ประกอบด้วยเลขศูนย์อย่างน้อย 3 ตัวและเลขหนึ่งอย่างน้อย 3 ตัว

ข้อ 5

ในปัญหาข้อนี้เราจะนับจำนวนวิธีการเดินจากจุด (0,0) ไปยังจุด (m,n) ในระนาบ xy โดยที่เส้นทางเดินจะประกอบด้วยการเดินเป็นก้าวๆ แต่ละก้าวจะเป็นการเดินไปทางด้านซ้าย (กล่าวคือเดินจากจุด (x,y) ไปยังจุด (x+1,y)) หรือเดินขึ้นด้านบน (กล่าวคือเดินจากจุด (x,y) ไปยังจุด (x,y+1))

1. จงแสดงว่าเส้นทางเดินที่ว่านี้สามารถแทนด้วยบิตสตริงความยาว m+n ที่มีเลขศูนย์ m ตัวและเลขหนึ่ง n ตัว
2. จงแสดงว่ามีเส้นทางเดินที่แตกต่างกันทั้งหมด ${m+n \choose m}$