Re: [問題] CS touring center : stepping stone (遞迴？)

[tkcn (小安)]

※ 引述《KitWoolsey (難得好天氣)》之銘言：
: 其實這站很多歸類於程式題的好像都會被數學做法秒殺....
: 這題的話，當n=2 時應該就是等價於高中排列組合學的
: ＂兩候選人開票　Ａ票數一路領先Ｂ的方法數＂此類題目　是有公式解的

說得非常正確，這叫作 Catalan Number，
不只是一路領先問題，其他的應用也非常多，
如果你繼續寫這些題目，相信未來還很有機會遇到。

建議把各種應用讀一下
http://en.wikipedia.org/wiki/Catalan_number

: 其實以前我就有想過要是不只兩個人怎麼辦....不過一直沒有得到解答
: 也有請教ㄧ些學長　不過好像也沒什麼想法＠＠　
: 所以我猜這題沒有數學做法（？）不過應該有遞迴式....但我想不太到@@@@?

Catalan Number 可以延伸至多維: http://oeis.org/A060854

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.114.78.231
推 KitWoolsey:                  (￣▽￣＃)/
→ KitWoolsey:@@ 按錯 = =
→ KitWoolsey:感謝回應 我打包回去仔細瞧瞧@_@
推 ledia:推 A060854 ... XD
推 ledia:程式題用 bc 還真好解
推 miraculouswi:這東西沒有遞迴公式(就人數而言和票數而言都一樣)
→ miraculouswi:例如三個人開票是Motzkin numbers
推 KitWoolsey:看半天找不到多維的有什麼推倒ＱＱ
→ KitWoolsey:代值進去過了 不過還是搞不懂qqqqq
→ tkcn:要推導什麼? 證明? 可以先看 2 維(catalan), 3 維
推 KitWoolsey:2維的看完了 3維以上的呢@@@
推 miraculouswi:三維以上的可以看RP Stanley的Enumerative Combinato
→ miraculouswi:-rics, 裡面有到五個人的公式,他長的很醜而且數學家
→ miraculouswi:已經大致上接受他就是長那麼醜,推導用表現理論,很難
→ miraculouswi:我的研究領域是這一個category,最近在寫paper這樣
→ miraculouswi:講那麼多就是想勸你放棄推導他XD除非你想花時間徹底
→ miraculouswi:研究類似的東東~如果還有相關問題很樂意回答=)
推 KitWoolsey:噢@@@@ 感謝^^"