推 thisistang4 : 感謝指導！ 06/16 00:20
※ 引述《thisistang4 (睡眠障礙者)》之銘言：
: https://lurl.cc/zVLqa
: 先謝過各位前輩了
← ← 1,2,...,n
─────┐┌─────
││
││ last in first out
││
└┘
每下去一個,記+
每上來一個,記-
Eg.n=3
+-+-+- => 123
+-++-- => 132
++--+- => 213
++-+-- => 231
+++--- => 321
從1,...,n用此方法,每個可排出來的順序一一對應到n個+與n個-的排列
且過程中+的個數≧-的個數
故所求個數=由(0,0)到(n,n)每次可向上或向右一格且過程中x≧y
因此方法數為C(2n,n)-C(2n,n+1)=(1/(n+1))C(2n,n) (Catalan數)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.97.38 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1718459193.A.3A8.html