#1
|
||||
|
||||
ช่วยหน่อยครับ
Prove,by a combinatorail argument,that for all $n>=2$ we have
$D(n)=(n-1)(D(n-1)+D(n-2))$ |
#2
|
||||
|
||||
$$RHS = (n-1)(n-1)!\sum_{i = 0}^{n-1}\frac{(-1)^i}{i!}+(n-1)(n-2)!\sum_{i = 0}^{n-2}\frac{(-1)^i}{i!}$$
$$=n(n-1)!\sum_{i = 0}^{n-1}\frac{(-1)^i}{i!}-(n-1)!\sum_{i = 0}^{n-1}\frac{(-1)^i}{i!}+(n-1)!\sum_{i = 0}^{n-2}\frac{(-1)^i}{i!}$$ $$=(n-1)![\sum_{i = 0}^{n-2}\frac{(-1)^i}{i!}-\sum_{i = 0}^{n-1}\frac{(-1)^i}{i!}]+n!\sum_{i = 0}^{n-1}\frac{(-1)^i}{i!}$$ $$=(-1)^n+n!\sum_{i = 0}^{n-1}\frac{(-1)^i}{i!}=n!\sum_{i = 0}^{n}\frac{(-1)^i}{i!}$$ $$=LHS $$ |
#3
|
||||
|
||||
ขอบคุณครับ สุดยอดเลยครับ
|
#4
|
||||
|
||||
ลองทำข้อนี้ดูครับ
จงพิสูจน์เอกลักษณ์ต่อไปนี้โดยใช้การพิสูจน์เชิงคอมบินาืทอริก $n!=\binom{n}{0}D_{n}+\binom{n}{1}D_{n-1}+...+\binom{n}{n}D_{0}$ |
#5
|
||||
|
||||
สุดยอดทั้งนั้นเลย
__________________
นากทะเลน้อย |
#6
|
||||
|
||||
เหมือนข้างบน ไม่เรียกว่า Prove,by a combinatorail นะครับ น่าจะเรียกว่า algebra prove
ตัวอย่างการ พิสูจน์แบบคอมบินาืทอริก จงแสดงว่า $\binom{n}{m} \binom{m}{r} =\binom{n}{r} \binom{n-r}{m-r} $ เมื่อ $n\geqslant m\geqslant r\geqslant 0$. พิสูจน์ : สมมติ เหตุการ แล้ว ก็ นับ 2 แบบ เรียกว่า double counting สมมติครู ต้องการเลือก นักเรียน $m$ คน จาก นักเรียน $n$ คน และ เลือก กรรมการ $r$ คน จาก $m$ คน. LHS: ได้จากสถานะการ เลย ครับ $\binom{n}{m} \binom{m}{r}$ RHS: ขั้นที่ 1. ครูเลือก กรรมการ $r$ คน จาก ทั้งหมด $n$ คน ได้ $\binom{n}{r}$. ขั้นที่ 2. ครูเลือก $m-r$ คน (เพื่อให้ครบ $m$ คน) จากนักเรียนที่เหลือ $n-r$ คน ได้ $\binom{n-r}{m-r}$ ดังนั้น ได้ RHS คือ $\binom{n}{r} \binom{n-r}{m-r} $ โดย double counting , $\binom{n}{m} \binom{m}{r} =\binom{n}{r} \binom{n-r}{m-r} $
__________________
คาราวะ |
#7
|
||||
|
||||
อ้างอิง:
คือ การจัดเรียงเลขโดยที่ เลข 1 ห้ามอยู่ตำแหน่งที่ 1 เลข 2 ห้ามอยู่ตำแหน่งที่ 2 ไปเรื่อยๆนะครับ เช่น $D_1=0$ $D_2=1$ $D_3=2$ $D_4=9$ The derangements สำหรับ n = 4 คือ 2 1 4 3 2 3 4 1 2 4 1 3 3 1 4 2 3 4 1 2 3 4 2 1 4 1 2 3 4 3 1 2 4 3 2 1 คุณสมบัติต่างๆ 1. $D_n=n!(1-\frac{1}{1!} +\frac{1}{2!} -\frac{1}{!} +\cdot+(-1)^n\frac{1}{n!} )$. 2. $D_n=(n-1)(D_{n-2}+D_{n-1})$ ; n= 3,4,5,... 3. $D_n=nD_{n-1}+(-1)^n$ ; n= 3,4,5,... 4. $D_n$ เป็นเลขคู่ ก็ต่อเมื่อ $n$ เป็นเลขคี่ 5. อีกเยอะครับ จำได้ คร่าวๆๆ
__________________
คาราวะ 01 มิถุนายน 2008 12:53 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ expol |
|
|