「琐记」卡特兰数

📅 Last Updated: 2021-01-19
📊 Word Count: 756
⏱️ Estimated Reading Time: 5 minutes
📄 PDF 📝 Source

卡特兰数的证明能够扩展到处理一类括号序列的问题上。不仅仅只是为了应付 sb 初赛。

卡特兰数

基本定义

使用 C(n)C(n) 表示卡特兰数的第 nn 项。

通项： C(n)=(2nn)−(2nn−1)=1n+1(2nn)=1n+1∑i=0n(ni)2 C(n) = \dbinom{2n}{n} - \dbinom{2n}{n-1} =\frac{1}{n+1}\dbinom{2n}{n}=\frac{1}{n+1}\sum_{i=0}^{n}\dbinom{n}{i}^2 递推式： C(n)=∑i=0n−1C(i)C(n−1−i) C(n)=\sum_{i=0}^{n-1}C(i)C(n-1 - i)

通项的推导

考虑通项公式的推导：

第 nn 项卡特兰数的定义之一就是 nn 对括号的合法配对方案。

将括号序列中的 ( 看成 +1 将 ( 看成 -1 ，合法的括号序列方案不仅仅是代数和等于 00 这么简单。

如果某一个位置的前缀和变成负数，那么这个括号是不可能合法了。

所以，按照上面括号向数字的映射定义，这个序列的任意一个位置的前缀和都应该不小于 00。

可以将问题转化为从平面上 (0,0)(0, 0) 走到 (2n,0)(2n, 0)，每一个位置都需要决策是沿着右上对角线走还是沿着右下对角线走。 走的过程中不能越过 y=0y=0 这条线。

考虑没有最后一条限制，方案数就是 (2nn)\dbinom{2n}{n}。

考虑哪些方案不合法，必然是到达过 y=−1y=-1 这条线的方案都不合法，考虑算出这部分不合法的方案。

可以强制一定要穿过 y=−1y=-1 这条线，只需要把终点设置为原终点 (2n,0)(2n, 0) 关于 y=−1y=-1 的对称点 (2n,−2)(2n, -2)，然后格路计数，考虑这样统计的所有方案一定穿过了若干次 y=−1y=-1 ，考虑最后一次穿过的点，到终点这一段路径全部翻着之后就是走到原终点的方案。不难发现，之前所计入的不合法方案和走到 (2n,−2)(2n, -2) 的方案一一对应。

这样就能得到不合法的方案数为 (2nn−1)\dbinom{2n}{n-1}

《组合数学》 中给出的证明只是把 最后一次穿越 改成了 第一次穿越，没有引入格点计数的转换，本质相同。

应用

卡特兰数的几个应用如下：

  • nn对括号的合法配对方案数.

  • nn 个节点的有根二叉树的形态数.这个对应了递推式.

  • nn 个数入栈后出栈的排列总数

  • 对凸 n+2n+2 边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)

  • nn 层的阶梯切割为 nn 个矩形的切法数 P2532 [AHOI2012]树屋阶梯

  • n+1n+1 个叶子（nn 个非叶子）的满二叉树形态数，这个对应了递推式.

这里的满二叉树指满足 结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点 的二叉树。

美国以及国际上所定义的满二叉树，即 full binary tree ,和国内的定义不同，美国 NIST 给出的定义为：A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.

前几项为：1,1,2,5,14,42,132

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 908edcf43a38d2bf955cb059d4a191e466e2c1042a8c7e59430b4e3e7da1ac84
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「琐记」卡特兰数.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「琐记」卡特兰数.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../4fcd408785.pdf.md', '-o', 'cache/4fcd408785.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \ifLuaTeX
    \usepackage{luacolor}
    \usepackage[soul]{lua-ul}
  \else
    \usepackage{soul}
    \ifXeTeX
      % soul's \st doesn't work for CJK:
      \usepackage{xeCJKfntef}
      \renewcommand{\st}[1]{\sout{#1}}
    \fi
  \fi
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「琐记」卡特兰数},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「琐记」卡特兰数}
  \author{Jiayi Su (ShuYuMo)}
  \date{2021-01-19 15:35:06}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  卡特兰数的证明能够扩展到处理一类括号序列的问题上。不仅仅只是为了应付
  \st{sb} 初赛。
  
  \subsection{卡特兰数}\label{ux5361ux7279ux5170ux6570}
  
  \subsubsection{基本定义}\label{ux57faux672cux5b9aux4e49}
  
  使用 \(C(n)\) 表示卡特兰数的第 \(n\) 项。
  
  通项： \[
  C(n) = \dbinom{2n}{n} - \dbinom{2n}{n-1} =\frac{1}{n+1}\dbinom{2n}{n}=\frac{1}{n+1}\sum_{i=0}^{n}\dbinom{n}{i}^2
  \] 递推式： \[
  C(n)=\sum_{i=0}^{n-1}C(i)C(n-1 - i)
  \]
  
  \subsubsection{通项的推导}\label{ux901aux9879ux7684ux63a8ux5bfc}
  
  考虑通项公式的推导：
  
  第 \(n\) 项卡特兰数的定义之一就是 \(n\) 对括号的合法配对方案。
  
  将括号序列中的 \texttt{(} 看成 \texttt{+1} 将 \texttt{(} 看成
  \texttt{-1} ，合法的括号序列方案不仅仅是代数和等于 \(0\) 这么简单。
  
  如果某一个位置的前缀和变成负数，那么这个括号是不可能合法了。
  
  所以，按照上面括号向数字的映射定义，这个序列的任意一个位置的前缀和都应该不小于
  \(0\)。
  
  可以将问题转化为从平面上 \((0, 0)\) 走到
  \((2n, 0)\)，每一个位置都需要决策是沿着右上对角线走还是沿着右下对角线走。
  走的过程中不能越过 \(y=0\) 这条线。
  
  考虑没有最后一条限制，方案数就是 \(\dbinom{2n}{n}\)。
  
  考虑哪些方案不合法，必然是到达过 \(y=-1\)
  这条线的方案都不合法，考虑算出这部分不合法的方案。
  
  可以强制一定要穿过 \(y=-1\) 这条线，只需要把终点设置为原终点 \((2n, 0)\)
  关于 \(y=-1\) 的对称点
  \((2n, -2)\)，然后格路计数，考虑这样统计的所有方案一定穿过了若干次
  \(y=-1\)
  ，考虑最后一次穿过的点，到终点这一段路径全部翻着之后就是走到原终点的方案。不难发现，之前所计入的不合法方案和走到
  \((2n, -2)\) 的方案一一对应。
  
  这样就能得到不合法的方案数为 \(\dbinom{2n}{n-1}\)
  
  《组合数学》 中给出的证明只是把 \textbf{最后一次穿越} 改成了
  \textbf{第一次穿越}，没有引入格点计数的转换，本质相同。
  
  \subsubsection{应用}\label{ux5e94ux7528}
  
  卡特兰数的几个应用如下：
  
  \begin{itemize}
  \item
    \(n\)对括号的合法配对方案数.
  \item
    \(n\) 个节点的有根二叉树的形态数.这个对应了递推式.
  \item
    \(n\) 个数入栈后出栈的排列总数
  \item
    对凸 \(n+2\)
    边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)
  \item
    \(n\) 层的阶梯切割为 \(n\) 个矩形的切法数
    \href{https://www.luogu.com.cn/problem/P2532}{P2532
    {[}AHOI2012{]}树屋阶梯}
  \item
    \(n+1\) 个叶子（\(n\) 个非叶子）的满二叉树形态数，这个对应了递推式.
  \end{itemize}
  
  这里的满二叉树指满足
  \textbf{结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点}
  的二叉树。
  
  \begin{quote}
  美国以及国际上所定义的满二叉树，即 full binary tree
  ,和国内的定义不同，美国 NIST 给出的定义为：A binary tree in which each
  node has exactly zero or two children. In other words, every node is
  either a leaf or has two children. For efficiency, any Huffman coding is
  a full binary tree.
  \end{quote}
  
  前几项为：1,1,2,5,14,42,132
  
  \begin{itemize}
  \tightlist
  \item
    \href{https://loj.ac/p/10238}{BZOJ 3907 网格}
  \end{itemize}
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 90.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (2 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 90.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (2 pages).
  Transcript written on .../input.log.