Re: [理工] [離散] 遞迴 98北大資工

[lock7863701 (Ayo)]

※ 引述《annheilong (方格子)》之銘言：
: D_n = (n-1)(D_n-1 + D_n-2), n>=3, D_1=0, D_2=1

亂序禁位

假設{1,2...n}個數


考慮位置1和其中一個數x

假設x放在位置1，那整數1就有剩下n-1個可能

而剩下的n-2個做亂序為Dn-2

所以(n-1)Dn-2

再來考慮x原本是在位置1

則x扣掉位置1有n-1種可能

剩下的n-1做亂序為Dn-1

所以(n-1)Dn-1

Dn = (n-1)(Dn-1 + Dn-2)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.33.16.90
推 annheilong:所以...這題該怎麼解呢?s
推 pigcat1315:我猜答案應該就是亂序的排列吧 Dn=n!(1-1/1!+1/2!...)
→ DavyBlue:暴力展開吧 這沒有close form吧
推 rnbjacky:這題超麻煩....Orz.......
→ lock7863701:原來是要解出來喔會錯意了XD  好像是用暴力法沒錯
→ lock7863701:展開然後假設An=Dn-nDn-1去帶
推 DavyBlue:我真的覺得北大的離散不是人寫的
推 pigcat1315:一 一"不過今年幾乎所有所有全部都換老師出題
→ pigcat1315:希望能跳脫這機車的題目XD
→ pigcat1315:0.0少打學校    所幾乎所有"學校"
→ showyoulovex:暨南 輔大 題目也不知道在難啥
推 annheilong:小弟是北大生 北大理論上不會換老師出題...XD
→ annheilong:還是感謝各位大大的解說~
推 lubu:直接去問張老師好了XD
推 annheilong:其實...我自己暴力解完之後解出來了...
→ sneak: 一 一"不過今年幾乎所 https://daxiv.com