L11 – Catalan number and T-routes

Discrete Mathematics2026年4月8日发布 芮和
178.7K 900
5,680字
24–36 分钟

Catalan Number

Triangulation of Convex Polygons

𝒫n+2{\mathcal{P}_{n+2}}(n≥0)(n \geq 0): convex (n+2)(n+2)-polygons (interior angles ≤180∘\leq 180^\circ, vertices point outward)

DEFINITION: A triangulation of 𝒫n+2\mathcal{P}_{n+2}(n≥0)(n \geq 0) is a set of n−1n-1 diagonals of 𝒫n+2\mathcal{P}_{n+2} which do not cross in their interiors.

The nnth Catalan NumberCnC_n (Euler, 1751): # of triangulations of 𝒫n+2\mathcal{P}_{n+2}(C0=1)(C_0 = 1)

Earlier findings: Ming Antu (1692-1763) in Qing court (China), established the following formula in “Quick Methods for Accurate Values of Circle Segments”:

sin⁡(2α)=2sin⁡α−∑n=1∞Cn−14n−1sin2n+1⁡α\sin(2\alpha) = 2 \sin \alpha – \sum_{n=1}^\infty \frac{C_{n-1}}{4^{n-1}} \sin^{2n+1} \alpha

Recurrence Relation: Cn+1=∑k=0nCkCn−kC_{n+1} = \sum_{k=0}^n C_k C_{n-k}, C0=1C_0 = 1

  • 𝒫n+3\mathcal{P}_{n+3} has Cn+1C_{n+1} triangulations
  • After removing an edge ee, each triangulation of 𝒫n+3\mathcal{P}_{n+3} gives
    • a triangulation for 𝒫a+2\mathcal{P}_{a+2} and a triangulation for 𝒫b+2\mathcal{P}_{b+2}
    • a+b=na + b = n

Binary Trees

DEFINITION: A binary tree is defined recursively as follows.

  • The empty set ∅\emptyset is a binary tree.
  • Otherwise, a binary tree has a root vertex vv, a left subtree T1T_{1}, and a right subtree T2T_{2}, both of which are binary trees.
    • left child: the root of T1T_{1} ; right child: the root of T2T_{2}
EXAMPLE: the binary trees with three vertices

THEOREM: The number of binary trees with nn vertices is CnC_{n}

  • proof is omitted

Plane Trees

DEFINITION: A plane tree (ordered tree) is defined recursively as follows.

  • A single vertex vv is a plane tree. And the vertex is called the root of the tree.
  • Otherwise, a plane tree has a root vertex vv, and a sequence (P1,…,Pm)(P_{1}, \dots, P_{m}) of subtrees, each of which is a plane tree.
EXAMPLE: the plane trees with four vertices

THEOREM: The number of plane trees with n+1n+1 vertices is CnC_{n}.

  • proof is omitted

Parenthesization

DEFINITION: A parenthesization (or bracketing) of a string of n+1n+1 symbols x0,x1,…,xnx_{0}, x_{1}, \dots, x_{n} consists of the insertion of nn left parentheses and nn right parentheses that define nn binary operations on the string.

  • Eugêne Charles Catalan (1814-1894) studied this problem in 1838

EXAMPLE: There are five parenthesizations on four symbols x0,x1,x2,x3x_{0},x_{1},x_{2},x_{3}

  • (((x0x1)x2)x3)\left(\left(\left(x_{0} x_{1}\right) x_{2}\right) x_{3}\right);
  • ((x0x1)(x2x3))\left(\left(x_{0} x_{1}\right)\left(x_{2} x_{3}\right)\right);
  • ((x0(x1x2))x3)\left(\left(x_{0}\left(x_{1} x_{2}\right)\right) x_{3}\right);
  • (x0((x1x2)x3))\left(x_{0}\left(\left(x_{1} x_{2}\right) x_{3}\right)\right);
  • (x0(x1(x2x3)))\left(x_{0}\left(x_{1}\left(x_{2} x_{3}\right)\right)\right)

THEOREM: The number of parenthesizations of a string of n+1n+1 symbols is CnC_{n}.

  • proof is omitted

Ballot sequence

DEFINITION: A ballot sequence of length 2n2n is a sequence of 11‘s and −1-1‘s, where

  • the number of 11‘s is equal to the number of −1-1‘s; and
  • the sum of every prefix of the sequence is nonnegative.

Bertrand’s Ballot Problem (special case): There are two candidates A and B in an election. Each receives nn votes. What is the probability pnp_{n} that A will never trail B during the count of votes?

  • First published by W. A. Whitworth (1840-1905) in 1878
  • Named after Joseph Louis Francois Bertrand (1822-1900) who rediscovered it in 1887.

EXAMPLE: AABABBBAAB is bad, since among the first 7 votes, A receives 3 but B receives 4 , which is greater than 3.

THEOREM: The number of Ballot sequences of length 2n2n is CnC_{n}.

  • proof is omitted

Dyck path

DEFINITION: A Dyck path of length 2n2n is a sequence P0=(x0,y0)=(0,0)P_{0}=(x_{0}, y_{0})=(0,0), Pi=(xi,yi)P_{i}=(x_{i}, y_{i})(1≤i<2n)(1\leq i<2n), P2n=(x2n,y2n)=(2n,0)P_{2n}=(x_{2n}, y_{2n})=(2n, 0) of 2n+12n+1 lattice points (points with integral entries) such that

  • (xi+1,yi+1)−(xi,yi)∈{(1,1),(1,−1)}(x_{i+1}, y_{i+1})-(x_{i}, y_{i}) \in \{(1,1),(1,-1)\} for all i=0,1,…,2n−1i=0,1, \dots, 2n-1
  • yi≥0y_{i}\geq 0 for all i=0,1,…,2ni=0,1, \dots, 2n
EXAMPLE: The Dyck paths of length 6 (n=3)(n=3)

THEOREM: The number of Dyck paths of length 2n2n is CnC_{n}.

REMARK: Dyck path may be called T-route generally. The name of “Dyck path” is in memory of German mathematician Walther von Dyck (1856-1934)


Shortest Path

DEFINITION: A 𝒑×𝒒\boldsymbol{p \times q}-grid is a collection of pqpq squares of side length 1, organized as a rectangle of side length pp and qq.

THEOREM: The number of shortest paths from (0,0)(0,0) to (p,q)(p,q) is (p+q)!p!q!\displaystyle\frac{(p+q)!}{p!q!}.

  • Let A={p⋅→,q⋅↑}A = \{p \cdot \rightarrow, q \cdot \uparrow\} be a (p+q)(p+q)-multiset.
  • The number of shortest paths == the number of permutations of AA.

T-Route

DEFINITION: Let A=(x,y),B∈ℤ2A = (x, y), B \in \mathbb{Z}^2. // integral (lattice) points

  • A T-Step at AA is a segment from AA to (x+1,y+1)(x + 1, y + 1) or (x+1,y−1)(x + 1, y – 1).
  • A T-Route from AA to BB is a route where each step is a T-step.

THEOREM: There is a T-route from A=(a,α)A = (a, \alpha) to B=(b,β)B = (b, \beta) only if (1) b>ab > a; (2) b−a≥|β−α|b – a \geq |\beta – \alpha|; and (3) 2|(b+β−a−α)2 \mid (b + \beta – a – \alpha).

  • Let A=P0,P1,…,Pk=BA = P_0, P_1, \dots, P_k = B be a T-route from AA to BB, where Pi=(xi,yi)P_i = (x_i, y_i).
    • x0=a,y0=αx_0 = a, y_0 = \alpha; xk=b,yk=βx_k = b, y_k = \beta;
    • xi−xi−1=1x_i – x_{i-1} = 1; yi−yi−1∈{±1}y_i – y_{i-1} \in \{\pm 1\} for every i=1,2,…,ki = 1,2, \dots, k
  • b−a=xk−x0=(xk−xk−1)+(xk−1−xk−2)+⋯+(x1−x0)=k>0b – a = x_k – x_0 = (x_k – x_{k-1}) + (x_{k-1} – x_{k-2}) + \dots + (x_1 – x_0) = k > 0
  • β−α=yk−y0=(yk−yk−1)+(yk−1−yk−2)+⋯+(y1−y0)\beta – \alpha = y_k – y_0 = (y_k – y_{k-1}) + (y_{k-1} – y_{k-2}) + \dots + (y_1 – y_0)
    • |β−α|≤|yk−yk−1|+|yk−1−yk−2|+⋯+|y1−y0|=k=b−a|\beta – \alpha| \leq |y_k – y_{k-1}| + |y_{k-1} – y_{k-2}| + \dots + |y_1 – y_0| = k = b – a
  • b+β−a−α=∑i=1k(yi−yi−1+xi−xi−1)b + \beta – a – \alpha = \sum_{i=1}^k (y_i – y_{i-1} + x_i – x_{i-1})
    • yi−yi−1+xi−xi−1∈{0,2}y_i – y_{i-1} + x_i – x_{i-1} \in \{0,2\}
    • 2|(b+β−a−α)2 \mid (b + \beta – a – \alpha)

REMARK: The T-condition (1)+(2)+(3) is sufficient for the existence of a T-route.


THEOREM: Let A=(a,α),B=(b,β)∈ℤ2A = (a, \alpha), B = (b, \beta) \in \mathbb{Z}^2 satisfy the T-condition, where α,β>0\alpha, \beta > 0. Then # of T-routes from AA to BB that do not intersect the x-axis is

(b−a)!(b−a2+β−α2)!(b−a2−β−α2)!−(b−a)!(b−a2+β+α2)!(b−a2−β+α2)!\frac{(b – a)!}{\left( \frac{b – a}{2} + \frac{\beta – \alpha}{2} \right)! \left( \frac{b – a}{2} – \frac{\beta – \alpha}{2} \right)!}–\frac{(b – a)!}{\left( \frac{b – a}{2} + \frac{\beta + \alpha}{2} \right)! \left( \frac{b – a}{2} – \frac{\beta + \alpha}{2} \right)!}
© 版权声明

相关文章

90 条评论

  • 纸面具幻想家
    纸面具幻想家 读者

    括号匹配那个例子列举得挺全,数起来不累

    日本
    回复
  • 不发声的鲸
    不发声的鲸 读者

    T-route就是德克路径吧

    中国北京
    回复
  • 无声的浪
    无声的浪 读者

    递归公式看着眼熟,组合数学老面孔了

    美国
    回复
  • 穿睡衣逛街的皇帝
    穿睡衣逛街的皇帝 读者

    投票问题那个例子挺形象,一下就看懂了

    韩国
    回复
  • 迷途之梦
    迷途之梦 读者

    明安图居然比欧拉还早?清朝数学这么猛的吗

    美国
    回复
  • 凛音晴美
    凛音晴美 读者

    全是 proof omitted 算了直接背

    澳大利亚
    回复
  • 旧人旧事
    旧人旧事 读者

    二叉树和括号化居然都是卡特兰数,太巧了

    摩尔多瓦
    回复
    • 贪睡的蜗牛
      贪睡的蜗牛 读者

      我也被这个巧合吸引了

      美国@ 旧人旧事
      回复
  • 黯夜猎魂
    黯夜猎魂 读者

    T-route 那个公式看着好复杂

    丹麦
    回复
    • 蹦迪的螺丝钉
      蹦迪的螺丝钉 读者

      同感,公式看着头大

      中国福建@ 黯夜猎魂
      回复
  • 话语废墟
    话语废墟 读者

    原来Dyck路径就是T-route,之前一直没搞懂

    智利
    回复
  • 异梦之主
    异梦之主 读者

    Catalan数在组合数学里应用真广

    南非
    回复
  • 蓝鲸计算
    蓝鲸计算 读者

    原来选票问题和二叉树也是Catalan数,数学真奇妙

    巴西
    回复
  • 心灵回响
    心灵回响 读者

    原来平面树和括号表达式也是Catalan数

    印度
    回复
  • yue了
    yue了 读者

    原来迪克路径也是Catalan数的一种表现

    韩国
    回复
    • 梦中人
      梦中人 读者

      组合数学的魅力

      中国吉林@ yue了
      回复
  • Hellspawn666
    Hellspawn666 读者

    原来平面树也是Catalan数,之前只知道括号匹配

    中国河南
    回复
  • 舞动节拍
    舞动节拍 读者

    Catalan数在这么多领域都有应用,有点震撼

    中国河北
    回复
  • 阳光微笑
    阳光微笑 读者

    原来选票问题和二叉树也是Catalan数,数学真奇妙

    中国上海
    回复
  • 暗紫幽兰
    暗紫幽兰 读者

    原来选票问题和二叉树也是Catalan数,数学真奇妙

    中国江苏
    回复
  • 暖风微醺
    暖风微醺 读者

    原来选票问题和括号匹配都是Catalan数,神奇

    韩国
    回复
  • 潮流指挥官
    潮流指挥官 读者

    原来选票问题也是Catalan数,数学无处不在啊

    中国湖南
    回复
  • 云隐清风
    云隐清风 读者

    原来括号匹配和树结构都跟Catalan数有关

    中国台湾
    回复