Catalan number 練習題

hbghlyj

以下是三個與 Catalan numbers 相關的問題

• 有一隻跳蚤在數線上來回跳躍，它每一步的長度都正好是 1。在某段時間內，這隻跳蚤由原點出發後總共跳了 2n 步，其中有 n 步是向右，n 步是向左。
  (1) 試證它最後的位置一定是在原點。
  (2) 有多少種跳法會使得它在跳躍過程中所有的落腳點都是非負整數？
• 小明帶著 2n 支冰棒到街上販賣，每支賣五元；在一段時間內，有 2n 人陸續向他買走了所有的冰棒。已知小明出門時身上並沒帶錢，而販賣過程中有 n 人是直接拿五元向他買，另外 n 人拿的則是十元（因此須找五元）；所幸販賣過程中始終未曾發生該找五元卻找不出五元的情形。請問可能的販賣過程有多少種？
• 有 2n 人圍著一張圓桌而坐。請問：有幾種方式可以讓每個人同時伸出一支手與另一人相握，而且不會發生手臂互相重疊的情形？以 n = 3 為例，總共有 5 種可能的握法，如下圖所示：
  

hbghlyj

第1、2題明顯是 $C_n$

第3题与 kuing.cjhb.site/forum.php?mod=viewthread&tid=6410、stackoverflow.com/questions/18076480/puzzle-n … shakes-without-cross有关

hbghlyj

kuing 发表于 2024-10-31 10:43
图真丑，建议用 tikz 画，应该很容易且方便

但TikZ图不会在首页的“最新图片”中展出，也不会在移动版的帖子预览中展出，对于点击率有不利影响

kuing

hbghlyj 发表于 2024-10-31 18:46
但TikZ图不会在首页的“最新图片”中展出，也不会在移动版的帖子预览中展出，对于点击率有不利影响 ...

笑死，在这论坛，你跟我说点击率😂

hbghlyj

kuing 发表于 2024-10-31 10:59
笑死，在这论坛，你跟我说点击率😂

是的，点击率会影响问题是否解决的概率。

kuing

hbghlyj 发表于 2024-10-31 19:05
是的，点击率会影响问题是否解决的概率。

这里有几个人会看你的主题帖子，你心里没数吗？

hbghlyj

kuing 发表于 2024-10-31 11:09
这里有几个人会看你的主题帖子，你心里没数吗？

虽然很少，但我会尽力让它更多的