อ้างอิง:
ข้อความเดิมเขียนโดยคุณ Art_ninja
ขอบคุณมากครับที่ช่วยแนะนำที่ผิดให้ ถ้าเป็นอย่างนั้นก็คงจะหาค่าของ M และ N ไม่ได้จริงครับ ว่าแต่วิธีของพี่ Onasdi ผมไม่เข้าใจน่ะครับว่าจะทำอย่างไร ขอพี่ Onasdi แสดงให้ดูด้วยได้ไหมครับ
|
ก็คือเราสร้างฟังก์ชั่น f จาก A(เซตของลำดับแบบแรก) ไปยัง B(เซตของลำดับแบบที่สอง) โดยส่ง $a_1a_2\dots a_k$ ไปยัง $b_1b_2\dots b_k$ โดยที่ $b_i$ เป็นเศษเหลือจากการหาร $a_i$ ด้วย $n$ (ยกเว้นถ้า $a_i=n$ เราให้ $b_i=n$)
นั่นก็คือ ถ้า $a_i=j\le n$ แล้ว $b_i=j$ และ ถ้า $a_i=n+j$ แล้ว $b_i=j$
ชัดเจนว่า $b_1b_2\dots b_k\in B$ เพราะ ใน $a_1a_2\dots a_k$ มี $j$ อยู่คี่ตัว และมี $n+j$ อยู่คู่ตัว ดังนั้น ใน $b_1b_2\dots b_k$ มี $j$ อยู่คี่ตัว
จะเห็นว่า สำหรับ $b\in B$ จะมี $a\in A$ อยู่ $2^{k-n}$ ตัวที่ทำให้ $f(a)=b$ เพราะว่า
สมมติให้ $b$ ประกอบด้วย $j$ อยู่ $x_j$ ตัว ($1\le j\le n$) ดังนั้น $\sum_{j=1}^{n} x_j=k$
เราต้องการนับว่ามีลำดับ $a\in A$ ที่จะถูกส่งมายัง $b$ กี่ลำดับ
สำหรับแต่ละ $j$ เราเลือกที่จะเปลี่ยนเป็น $n+j$ หรือว่าคงไว้เป็น $j$ ดังเดิม โดยที่จะต้องมี $j$ คี่ตัว $n+j$ คู่ตัว (เราทำได้เพราะ $x_j$ เป็นคี่) มีวิธีทั้งหมด $\dbinom{x_j}{1}+\dbinom{x_j}{3}+\dots +\dbinom{x_j}{x_j}=2^{x_j-1}$ (เหมือนกับนับสับเซตที่มีสมาชิกคี่ตัว)
ดังนั้นมีลำดับ $a$ อยู่ $\prod_{j=1}^{n} 2^{x_j-1}=2^{k-n}$ ตัว
และเนื่องจาก $k-n=0,2,4,\dots$ จึงได้ว่า A,B ไม่เป็นเซตว่าง ดังนั้น $N/M=2^{k-n}$