作者XII (Mathkid)
看板Math
标题Re: [其他] 一题 排列组合 请教
时间Sat Jun 15 21:46:30 2024
※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1718459193.A.3A8.html
1F:推 thisistang4 : 感谢指导! 06/16 00:20