หลักหนึ่งต่อหนึ่งทั่วถึง

[Tony]

คือว่า ลองทำโจทย์ใน หนังสือ คอมบินาทอริก สอวน. แล้วทำไม่ค่อยได้เลยเอามาเลยเอามาขอแนวคิดดูครับ
1. โยนลูกเต๋า ที่ไม่ถ่วงลูกหนึ่ง $4$ ครั้ง จงหาความน่าจะเป็นที่แต้มขึ้นในการโยนสามครั้งสุดท้าย แต่ละครั้งมีค่าไม่น้อยกว่าแต้มที่ขึ้นในครั้งก่อนหน้า

2. ให้
$$ \prod_{n=1}^{1996}(1+nx^{3^{n}})=1+a_{1}x^{k_{1}}+a_{2}x^{k_{2}}+ \cdots + a_{m}x^{k_{m}} $$
โดยที่ $ a_{1},a_{2},....a_{m} \not= 0 $ และ $ k_{1}<k_{2}< \cdots < k_{m} $ จงหา $ a_{1234} $
ผมได้ $560$ ไม่รู้ถูกหรือผิด และอยากได้แนวคิดด้วยครับ ผมคิดไม่ค่อยเป็นระบบ

3. ให้ $A = \{ {a_{10},a_{2}, \cdots , a_{100}} \}$ และ $B = \{1,2, \cdots , 50\}$ จงหาจำนวนฟังก์ชันทั่วถึงจาก $A$ ไป $B$ โดยมีเงื่อนไขว่า $f(a_{1}) \leq f(a_{2}) \leq \cdots f(a_{100})$ ถ้า $f$ ไม่จำเป็นต้องทั่วถึง จะมีจำนวนฟังก์ชันได้เท่าไร

[passer-by]

ก่อนจะตอบข้อ 3 อยากให้สังเกต กรณีเลขน้อยๆ ก่อน เช่น

P= {a₁,a₂,...,a₁₀ } Q= {1,2,....,5}

ถ้ามีอักษร A อยู่ 5 ตัว และอักษร x อยู่ 10 ตัว

แล้วพิจารณาทุกการเรียงอักษรที่ A ต้องขึ้นหน้าเสมอนะครับว่า บ่งบอกอะไร เช่น

AxxAAxAxxxxxAxx

ถ้า x แต่ละตัว (นับจากซ้าย) บ่งบอกว่ามี A ผ่านมาแล้วกี่ตัว จะได้ว่า

ก่อนถึง x ตัวที่ 1 มี A อยู่แล้ว 1 ตัว = f(a₁)
ก่อนถึง x ตัวที่ 2 มี A อยู่แล้ว 1 ตัว = f(a₂)
ก่อนถึง x ตัวที่ 3 มี A อยู่แล้ว 3 ตัว = f(a₃)
ก่อนถึง x ตัวที่ 4 มี A อยู่แล้ว 4 ตัว = f(a₄)
ก่อนถึง x ตัวที่ 5 มี A อยู่แล้ว 4 ตัว= f(a₅)
ก่อนถึง x ตัวที่ 6 มี A อยู่แล้ว 4 ตัว= f(a₆)
ก่อนถึง x ตัวที่ 7 มี A อยู่แล้ว 4 ตัว= f(a₇)
ก่อนถึง x ตัวที่ 8 มี A อยู่แล้ว 4 ตัว= f(a₈)
ก่อนถึง x ตัวที่ 9 มี A อยู่แล้ว 5 ตัว= f(a₉)
ก่อนถึง x ตัวที่ 10 มี A อยู่แล้ว 5 ตัว= f(a₁₀)

ดังนั้นจำนวนวิธีการเรียงอักษร A 5 ตัวและ x 10 ตัว ให้ A นำหน้าเสมอ จะได้เท่ากับจำนวนฟังก์ชัน ที่เรียงเป็น nondecreasing order จาก P ไป Q

แต่ถ้าต้องการให้ onto ด้วย ก็ต้องเพิ่มเงื่อนไขเป็น ให้ Ax นำหน้า และลงท้ายด้วย x นอกจากนี้ A ทุกตัวแยกจากกันด้วย (ถ้า A บางตัวติดกัน จะไม่ onto)

หวังว่าจะนำหลักการนี้ ไปประยุกต์ใช้ในข้อ 3 ได้นะครับ

[gon]

ข้อ 1 น่าจะเป็นแบบนี้ครับ

ในการหาจำนวน Sample Space (ปริภูมิตัวอย่าง) จะมี (6)(6)(6)(6) วิธี
คือ (1, 1, 1, 1) ... (6, 6, 6, 6)

สำหรับเหตุการณ์ที่ต้องการ คือ
"แต้มขึ้นในการโยนสามครั้งสุดท้าย แต่ละครั้งมีค่าไม่น้อยกว่าแต้มที่ขึ้นในครั้งก่อนหน้า"

จะสามารถแบ่งออกได้เป็น 6 กรณีใหญ่ ๆ คือ

กรณีที่ 1 : ครั้งที่ 1 ขึ้นแต้ม 1 , กรณีที่ 2 : ครั้งที่ 1 ขึ้นแต้ม 2 , ... , กรณีที่ 6 : ครั้งที่ 1 ขึ้นแต้ม 6 ,

ลองพิจารณากรณีที่ 1 ก็จะสามารถแบ่งออกได้เป็น 3 กรณีย่อยคือ
กรณีที่ 1.1 แต้มทั้งสามครั้งสุดท้ายต่างกันทั้งหมด เช่น 2, 1, 5
กรณีที่ 1.2 แต้มทั้งสามครั้งสุดท้ายซ้ำ 1 คู่ เช่น 6, 4, 4
กรณีที่ 1.3 แต้มทั้งสามครั้งสุดท้ายเหมือนกันหมด เช่น 1, 1, 1

ไม่ว่ากรณีใดก็ตาม เมื่อได้จำนวนมาแล้วก็ต้องเรียงลำดับจาก มากไปน้อยน้อยไปมากโดยอัตโนมัติ เช่น ถ้าได้ 2, 1, 5 มาก็ต้องเขียนเป็น (1, 1, 2, 5) เป็นต้น.

กรณีที่ 1.1 + กรณีที่ 1.2 + กรณีที่ 1.3 = ${6 \choose 3} + {6 \choose 1}{5 \choose 1} + {6 \choose 1}$

กรณีที่ 2.1 + กรณีที่ 2.2 + กรณีที่ 2.3 = ${5 \choose 3} + {5 \choose 1}{4 \choose 1} + {5 \choose 1}$

....

สำหรับกรณีที่ 5 จะมีเพียง 2 กรณีย่อย และ กรณีที่ 6 เป็นไปได้้แค่แบบเดียว คือ (6, 6, 6, 6)

เมื่อรวมทั้งหมด ก็จะได้ .... ดังนั้นความน่าจะเป็นเท่ากับ $\frac{7}{72}$

[gon]

สำหรับข้อ 3 วิธีคิดของผมเป็นแบบนี้ครับ ลองพิจารณาดูตัวอย่าง

สมมติว่า A = {a, b, c, d, e} , B = {1, 2, 3}

จำนวนฟังก์ชันจาก A ไปทั่วถึง B โดยที่ $f(a) \le f(b) \le f(c) \le f(d) \le f(e) $ เท่ากับ ?

เริ่มต้นให้เรียง a, b, c, d, e หลังจากนั้นให้เลือกว่าจะนำ แท่ง (bar) , | | มาสองอัน โดยเลือกว่าจะวางอยู่ระหว่างตรงรูไหนของ a, b, c, d, e และ ห้ามเลือกรูหน้าสุดหรือหลังสุด

เช่น ถ้าเป็น a | b c d | e ก็จะหมายถึง
f(a) = 1, f(b) = f(c) = f(d) = 2 , f(e) = 3

ดังนั้นจำนวนฟังก์ชันจาก A ไปทั่วถึง B โดยที่ $f(a) \le f(b) \le f(c) \le f(d) \le f(e) $ เท่ากับ ${4 \choose 2} = 6$ ฟังก์ชัน

---

สำหรับกรณีที่ำไม่จำเป็นที่ว่า ฟังก์ชันต้องทั่วถึง พิจารณาได้จากตัวอย่างนี้ครับ

ถ้าเขียน || x x x x x จะหมายถึง 1 กับ 2 ไม่มีคู่ที่จะจับ ส่วน f(a) = f(b) = f(c) = f(d) = f(e) = 3
หรือ ถ้าเป็น x x || x x x จะหมายถึง f(a) = f(b) = 1, ส่วน 2 ไม่มีคู่จับ และ f(c) = f(d) = f(e) = 3
หรือ ถ้าเ็ป็น x | x x x | x จะหมายถึง f(a) = 1, f(b) = f(c) = f(d) = 2, f(e) = 3

นั่นก็คือ จำนวนฟังก์ชันจาก A ไปยัง B โดยที่ $f(a) \le f(b) \le f(c) \le f(d) \le f(e) $ จะีมีค่าเท่ากับจำนวนวิธีการเรียงสับเปลี่ยนของซ้ำ 2 ชุด คือ xxxxx กับ || ซึ่งทำได้ $\frac{6!}{4! \cdot 2!} = {6 \choose 2} = 15$ ฟังก์ชัน

[passer-by]

ข้อความเดิมของคุณ gon :
นั่นก็คือ จำนวนฟังก์ชันจาก A ไปยัง B โดยที่ $ f(a) \leq f(b) \leq f(c) \leq f(d) \leq f(e)$ จะีมีค่าเท่ากับจำนวนวิธีการเรียงสับเปลี่ยนของซ้ำ 2 ชุด คือ xxxxx กับ || ซึ่งทำได้ $\frac{6!}{4!2!}={6 \choose 2}=15$ฟังก์ชัน

มันต้องเป็น $ { 7\choose 2} $ ไม่ใช่หรือครับ เพราะมี x 5 ตัว และมี bar 2 ตัว

แล้วก็ แถม กรณีทั่วไป ให้เลยดีกว่า สำหรับข้อ 3

ถ้า A มีสมาชิก N ตัว และ B={1,2,3,...,n} โดย $ N \geq n $
ถ้าต้องการสร้างฟังก์ชัน จาก A ไป B ให้เกิด nondecreasing order อย่างเดียว จะได้
$\frac{(N+n-1)!}{N!(n-1)!} $ วิธี

แต่ถ้าเพิ่มเงื่อนไข onto ด้วย จะได้ $ {N-1 \choose n-1} $ วิธี

[gon]

ข้อความเดิมของคุณ passer-by:
มันต้องเป็น $ { 7\choose 2} $ ไม่ใช่หรือครับ เพราะมี x 5 ตัว และมี bar 2 ตัว

เบลออย่างแรง ขอบคุณครับ.

อ้อ. ข้อ 2 น้อง Tony ต้องแก้โจทย์ก่อนมั้งครับ

[Tony]

ข้อ 2.แก้โจทย์ให้แล้วนะครับ

ขอบคุณ แนวคิดมากนะครับ รู้สึกมีกำลังใจทำโจทย์มากขึ้นเยอะ

[Tony]

$4$. ให้ $n$ เป็นจำนวนเต็มบวกและ $n \geq 12 $ จงหาชุดคำตอบ $(a,b,c,d)$ ที่ $a,b,c,d$ เป็นจำนวนเต็มและ $a+b+c+d=n$ ที่สอดคล้องกับเงื่อนไขต่อไปนี้
4.1 $a=b \geq 1$ และ $1 \geq c \geq d$
4.2 $a \geq 1,\ b \geq 1,\ 1 \leq c ,\ 1 \leq d \leq 5$
4.3 $a \geq 1$ และ $1 \leq b,c,d \leq 6$
4.4 $1 \leq a \leq b \leq c \leq d$

[warut]

ข้อความเดิมของคุณ Tony:
2. ให้
$$ \prod_{n=1}^{1996}(1+nx^{3^{n}})=1+a_{1}x^{k_{1}}+a_{2}x^{k_{2}}+ \cdots + a_{m}x^{k_{m}} $$
โดยที่ $ a_{1},a_{2},....a_{m} \not= 0 $ และ $ k_{1}<k_{2}< \cdots < k_{m} $ จงหา $ a_{1234} $
ผมได้ $560$ ไม่รู้ถูกหรือผิด และอยากได้แนวคิดด้วยครับ ผมคิดไม่ค่อยเป็นระบบ

จะเห็นว่าค่าของ $k_i,i=1,\dots,m$ จะต้องสามารถเขียนได้ในรูปเลขฐาน 3 ที่ประกอบขึ้นด้วยเลข 1 กับ 0 เท่านั้น (ไม่มี 2) และหลักสุดท้ายจะต้องเป็น 0 เสมอ นั่นคือ

$k_1=10_3=3$
$k_2=100_3=9$
$k_3=110_3=12$
$k_4=1000_3=27$
$k_5=1010_3=30$
$k_6=1100_3=36$
$k_7=1110_3=39$
$k_8=10000_3=81$
$k_9=10010_3=84$
$\vdots$
$k_{1234}=100110100100_3$

(เวลาไล่ก็ทำโดยใช้เลขฐาน 2 ช่วย อย่างเช่น เนื่องจาก $1234=10011010010_2$ เราจึงได้ค่า $k_{1234}$ ดังกล่าวครับ)

จากที่ $k_{1234}= 100110100100_3= 3^{11}+3^8+3^7+3^5+3^2$
ดังนั้น $a_{1234}= 11\cdot 8 \cdot7 \cdot5 \cdot2=6160$ ครับ

ป.ล. ผมไม่รู้ว่าจะอธิบายยังไงให้ดีกว่านี้ ก็ลองพยายามคิดตามดูนะครับ ถ้าไม่เข้าใจคงต้องให้คนอื่นช่วยอธิบายเพิ่มแล้วล่ะ จริงๆตั้งใจจะทำข้อนี้นานแล้วครับ แต่ดันลืมเพราะมัวแต่หมกมุ่นอยู่กับโจทย์ของคุณ passer-by

[Tony]

จาก $k_{1234}= 100110100100_3= 3^{11}+3^8+3^7+3^5+3^2$
ดังนั้น $a_{1234}= 11\cdot 8 \cdot7 \cdot5 \cdot2=6160$ ครับ

ไม่ทราบว่ามายังไงหรอครับ

และผมอยากรู้ แนวคิดของ ข้อ4 ด้วยครับ
ขอบคุณครับ

[warut]

เพราะว่าพจน์ $\large a_{1234}x^{k_{1234}}$ มาจากผลคูณต่อไปนี้ครับ $$ \large (11x^{3^{11}}) (8x^{3^8}) (7x^{3^7}) (5x^{3^5}) (2x^{3^2}) $$