2016年理科 课标全国卷III 第12题（规范01数列）科普

hbghlyj

凸多邊形的三角化問題 考慮以下動作：在一個凸多邊形的內部畫上一些互不相交的對角線（即頂點間的連線），使得多邊形內部被分割成許多三角形，每個三角形的每一邊皆為多邊形的一邊或是多邊形的一條對角線；以上動作稱為多邊形的「三角化」（triangulation）。舉例來說，下面是將一個凸五邊形三角化的所有可能情形（總共有五種可能）：

請問：對任意一個大於 2 的正整數 $n$ 而言，將一個凸 $n$ 邊形三角化的方法總共有幾種？
這個問題可以用遞迴的方式來解決。假設 $a_n$ 代表將一個凸 $n$ 邊形三角化的方法數，上圖顯示了 $a_5=5$；我們希望用遞迴的方式定義數列 $a_3, a_4, a_5, \ldots \ldots$ 。
首先，假設我們將一個凸 $n$ 邊形的 $n$ 個頂點依順時鐘方向分別命名為 $v_1, v_2, \ldots,v_n$，多邊形的 $n$ 個邊因此是 $\overline{v_1 v_2} , \overline{v_2 v_3}, \ldots,\overline{v_{n-1} v_n}, \overline{v_n v_1}$。考慮其中的一邊 $\overline{v_n v_1}$；在我們依某種方式將多邊形三角化之後，$\overline{v_n v_1}$ 必定會是某個三角形的一邊，也就是說，$v_1$ 與 $v_n$ 必定會是某個三角形的三個頂點中的兩個，而這個三角形的第三個頂點有可能是 $v_2,v_3, \ldots, v_{n-1}$ 這 $(n-2)$ 個點中的任何一點；如果我們能夠知道當第三個頂點是這 $(n-2)$ 個點中的每一點時各有幾種方法可以將多邊形三角化，$a_n$ 應該就等於這 $(n-2)$ 個數的和。

假設以 $\overline{v_nv_1}$ 為一邊的三角形的第三個頂點為 $v_k$。先考慮 $3 \leq k \leq(n-2)$ 的情形，如下圖所示：

三角形 $v_n v_1 v_k$ 將多邊形的內部分隔成兩邊，一邊是一個以 $v_1, v_2, \ldots, v_k$ 為頂點的凸 $k$ 邊形，另一邊則是一個以 $v_k, v_{k+1}, \ldots, v_n$為頂點的凸 $(n-k+1)$ 邊形，將這兩個多邊形三角化的方法分別有 $a_k$ 與 $a_{n-k+1}$ 種，因此當第三個頂點為 $v_k$ 時，將 $n$ 邊形三角化的方法總共有 $a_k a_{n-k+1}$ 種。

接著考慮 $k$ 等於 2 的情形：

由上圖不難看出，當 $k$ 為 2，將 $n$ 邊形三角化的方法數就等於將由 $v_2, v_3, \ldots, v_n$ 這 $(n-1)$ 個點形成的凸 $(n-1)$ 邊形三角化的方法數，因此有 $a_{n-1}$ 種；如果我們定義 $a_2=1$, 那麼 $a_{n-1}$ 可以寫為 $a_2 \cdot a_{n-1}$。同樣地，當 $k=(n-1)$ 時，將 $n$ 邊形三角化的方法數就等於將由 $v_1, v_2, \ldots, v_{n-1}$ 這 $(n-1)$ 個點形成的凸 $(n-1)$ 邊形三角化的方法數，同樣也有 $a_{n-1}\left(=a_{n-1} \cdot a_2\right)$ 種；因此將凸 $n$ 邊形三角化的方法總共有
$$
\begin{aligned}
a_n & =\sum_{k=3}^{n-2} a_k a_{n-k+1}+a_2 a_{n-1}+a_{n-1} a_2 \\
& =\sum_{k=2}^{n-1} a_k a_{n-k+1}
\end{aligned}
$$
種；再配合初始條件 $a_2=1$，我們有了數列 $a_2,a_3, a_4, \ldots$ 完整的遞迴定義：
$$
a_n= \begin{cases}1 & n=2 \\ \sum_{k=2}^{n-1} a_k a_{n-k+1} & n>2\end{cases}
$$
讀者不難發現這個數列與 Catalan numbers 有密切的關係；事實上，由
$$
a_{n+2}=\sum_{k=2}^{n+1} a_k a_{n-k+3}=\sum_{k=1}^n a_{k+1} a_{n-k+2}
$$
我們很容易可以用數學歸納法証明對所有非負整數 $n \cdot a_{n+2}=C_n$，因為這兩個數列的第一項相等($a_2=C_0=1$)，而且如果對所有小於 $n$ 的非負整數 $k$ 而言 $a_{k+2}=C_k$ 都成立的話，那麼
$$
a_{n+2}=\sum_{k=1}^n a_{k+1} a_{n-k+2}=\sum_{k=1}^n C_{k-1} C_{n-k}=C_n
$$
因此，對任意一個大於 2 的正整數 $n$ 而言，將一個凸 $n$ 邊形三角化的方法總共有
$$
a_n=C_{n-2}=\frac{1}{n-1}\binom{2 n-4}{n-2}
$$
種。

hbghlyj

堆疊問題 下圖所示為一長條型的裝排球用的袋子（假設袋子很長，不管裝幾粒球都不會滿出來）：

已知在某段時間內，有 n 粒球曾經「進出」此袋，也就是說，每一粒球都曾經在某個時間被放入袋中，並於之後的某個時間被取出。以 n = 2 為例，放入及取出的順序總共有「放入、放入、取出、取出」及「放入、取出、放入、取出」等兩種可能。
請問：當 n 為任意正整數時，這 n 個放入的動作及 n 個取出的動作之間總共有幾種可能的順序？
這個問題很明顯又和我們前面探討的小明的上班問題類似，因為這 n 粒球的任何一種可能的進出順序都包含了 n 個放入及 n 個取出的動作（小明須向東及向北各走 n 格），而且過程中已取出的球數隨時都不會超過已放入的球數（小明已走過的向北的格子數隨時都不能超過向東的格子數）。因此，對任意正整數 n 而言，n 粒球進出袋子總共有 $C_n$ 種可能的順序。
讀者如果對 「資料結構」（Data Structures）稍有涉獵，不難看出此題中的排球袋其實就是「堆疊」（Stacks）的概念。

hbghlyj

关于Catalan三角数的一些高次组合恒等式

贺莘东

Abstract. Catalan三角数在组合学和数论中是一类十分重要的数.为探究Catalan三角数的内部结构以及Catalan三角数的高次组合展开式, 利用代数组合中已有的一些组合等式和数学归纳法, 并结合Catalan三角数之间的关系, 即A_{n, k}=C_{2n+1, n+1-k}、B_{n, k}=C_{2n, n-k}, 其中$$ C_{n, k}:=\binom{m-1}{k}-\binom{n-1}{k-1} $$ 得出了几个关于C_{n, k}的递推公式以及Harmonic数H_n与C_{n, k}的高次组合展开式, 也得出了A_{n, k}、B_{n, k}的高次交错和的结果.这些结果为现有的组合恒等式做了补充, 也为探究更高次的Catalan三角数做了基奠.

1976年, Shapiro首先定义了一个由有限序列构成的路径, 并给出了两条路径相交和距离以及路径长度的定义, 最后他用B_{n, k}表示长度为n, 距离为k的非交路径对的数目^[1].通常情况下Catalan三角数B_n, _k的组合表达式为$$ B_{n, k}:=\frac{k}{n}\binom{2 n}{n-k}=\binom{2 n-1}{n-k}-\binom{2 n-1}{n-k-1} $$

Shapiro在文中也明确说明将其取名为Catalan三角数的原因是由于B_{n, 1}是组合学中非常著名的Catalan数^[2,3], 其定义为$$ A_{n, k}:=\frac{2 k-1}{2 n+1}\binom{2 n+1}{n+1-k}=\binom{2 n}{n+1-k}-\binom{2 n}{n-k} . $$

Miana和Romero在文献[4]中提出了另一类Catalan三角数A_{n, k}, 其定义为$$ A_{n, k}:=\frac{2 k-1}{2 n+1}\binom{2 n+1}{n+1-k}=\binom{2 n}{n+1-k}-\binom{2 n}{n-k} . $$

他们认为虽然Catalan三角数有许多类, 但归根结底均可从Ballot数得来.而在2017年, Miana等在[5]中再次定义了一个组合数$$ C_{n, k}:=\frac{n-2 k}{n}\binom{n}{k}=\binom{n-1}{k}-\binom{n-1}{k-1} $$

他们认为这也是一类Catalan三角数, 并且它与前面两类Catalan三角数有一定的关系:$$ B_{n, k}=C_{2 n, n-k}, A_{n, k}=C_{2 n+1, n-k+1} $$

自从这三类Catalan三角数被提出到现在, 已经有了丰富的结果.2008年, Gutiérrez等在文献[6]中利用Chu-Vandermonde公式推导出了两个Catalan三角数乘积之和的结果.Miana和Romero在文献[7]中利用W-Z理论得到了关于B_{n, k}的二次和的结果.2009年, Chen和Chu在文献[8]中利用对称函数和组合间的一些反演公式彻底解决了文献[6]中的问题2.2010年, Zhang和Pang在文献[9]中利用一些已有的组合等式得出了一些交错和的结果.同年, Guo和Zeng在文献[10]中利用牛顿插值公式所得出的结论回答了文献[7]中所提出的问题1是肯定的, 问题2是否定的.还是在2010年, Miana和Romero在文献[4]中研究了另一类Catalan三角数A_{n, k}, 并给出了一些二次和的结果.2017年, Miana等在文献[5]中定义Catalan三角数C_{n, k}时, 利用三类Catalan三角数之间的关系, 得到了一些关于B_{n, k}以及A_{n, k}的结果, 并首次给出Catalan三角数与Harmonic数之间的组合等式.

1 预备知识

首先给出几个必要的定义和引理.

定义1^[7]Harmonic数H_n的定义为:$$ H_n=\sum_{k=1}^n \frac{1}{k}, n \in ℕ_+, H_0=0 $$引理 1^[7] 若 $m, n \in ℕ_+$, 则 $\sum_{k=0}^n(-1)^k C_{m, k}^2=2(-1)^n\binom{m-1}{n}^2-\sum_{k=0}^n(-1)^k\binom{m}{k}^2$.
引理 2^[7] 若 $m, n \in ℕ_+$, 则 $\sum_{k=0}^n(-1)^k C_{m, k}^3=\frac{m-3 n}{m}(-1)^n\binom{m-1}{n}^3-\frac{m-3}{m} \sum_{k=0}^{n-1}(-1\binom{m-1}{k}^3$. 注 1 本文规定 $0^0=1$, 且若 $n<k$, 或 $k<0$, 则 $\binom{n}{k}=0$.

2 主要结果

文献[5]已经研究了一部分Catalan三角数的高次组合恒等式, 本节主要利用已有的组合等式去探究其他的Catalan三角数的高次和.

定理1 若k∈ℕ, 则有C_{2k+4, k+1}=C_{2k+3, k}+C_{2k+2, k}.

证 根据 $\left(C_{n, k}\right)_{n>1, k>0}$ 的定义, 有 $C_{2 k+3, k}+C_{2 k+2, k}=\frac{(2 k+1) !}{k !(k+3) !} Q(m, k)$, 其中

Q (m, k) =3 (2k+2) +2 (k+3) =8k+12.则$$ C_{2 k+3, k}+C_{2 k+2, k}=\frac{2}{2 k+4} \times \frac{(2 k+1) !(2 k+2)(2 k+3)(2 k+4)}{(k+1) !(k+3) !}=\frac{2}{2 k+4}\binom{2 k+4}{k+1}=C_{2 k+4, k+1} \text {. } $$

从定理1可以看出$\left(C_{n, k}\right)_{n>1, k>0}$的下标只有一个变量, 并且是递进的关系.所以根据定理1便可以得到如下定理.

定理2若n∈ℕ₊, 则有$$ \sum_{k=0}^{n-1} C_{2 k+3, k}=\frac{1}{n+1}\binom{2 n+2}{n}-1 . $$

证 根据定理 1 可知 $C_{2,0}+\sum_{k=0}^{n-1} C_{2 k+3, k}=C_{2,0}+C_{3,0}+\cdots+C_{2 n+1, n-1}=C_{2 n+2, n}$, 则

证 根据A_{n, k}=C_{2n+1, n+1-k}和引理1, 可以得到\begin{aligned} & \sum_{k=1}^{n+1}(-1)^k A_{n, k}^2=(-1)^{n+1} \sum_{k=0}^n(-1)^k C_{2 n+1, k}^2=-2\binom{2 n}{n}^2+(-1)^n \sum_{k=0}^n(-1)^k\binom{2 n+1}{k}^2= \\ & -2\binom{2 n}{n}^2+\sum_{k=0}^n(-1)^{n+k}\binom{2 n}{k}^2+2 \sum_{k=0}^n(-1)^{n+k}\binom{2 n}{k}\binom{2 n}{k-1}+\sum_{k=0}^n(-1)^{n+k}\binom{2 n}{k-1}^2= \\ & -2\binom{2 n}{n}^2+\sum_{k=0}^n(-1)^{n+k}\binom{2 n}{k}^2+2 \sum_{k=0}^n(-1)^{n+k}\binom{2 n}{k}\binom{2 n}{k-1}+\sum_{k=0}^n(-1)^{n+k+1}\binom{2 n}{k}^2+\binom{2 n}{n}^2 \\ & =-\binom{2 n}{n}^2+2(-1)^n \sum_{k=1}^n(-1)^k\binom{2 n}{k}\binom{2 n}{k-1}=-(n+1)^2\left(C_n\right)^2+2(-1)^n \sum_{k=1}^n(-1)^k\binom{2 n}{k}\binom{2 n}{k-1} . \end{aligned}

定理4 若n∈ℕ₊, 则

\begin{aligned} & \sum_{k=0}^n(-1)^k B_{n, k}^3=\frac{(2 n-1)^3}{2} C_{2 n-1, n}^3+\frac{(2 n-3)(n+1)^3}{4 n}\left(C_n\right)^3 \\ & -\frac{(2 n-3)(3 n+3)}{4 n} C_{3 n, n} \cdot C_n+(-1)^n \frac{(2 n-3)(6 n-3)(n-1)}{4} D+(-1)^n \frac{2 n-3}{16 n} F, \end{aligned} 其中 $D=\sum_{k=0}^{n-1} \frac{(-1)^k}{(n-k)^3} C_{2 n, k}^2 \cdot C_{2 n-2, k-1}, F=\sum_{k=0}^{n-1} \frac{(-1)^k k^3}{(n-k)^3} C_{2 n, k}^3$.

证 由引理2可得$$ \sum_{k=0}^n(-1)^k B_{n, k}^3=(-1)^n \sum_{k=0}^n(-1)^k C_{2 n, k}^3=-\frac{1}{2}\binom{2 n-1}{n}^3-(-1)^n \frac{2 n-3}{2 n} \sum_{k=0}^{n-1}(-1)^k\binom{2 n-1}{k}^3 . $$

将等式右边的和式做如下处理:\begin{aligned} & \sum_{k=0}^{n-1}(-1)^k\binom{2 n-1}{ k}^3 \\ = & \left.\sum_{k=0}^{n-1}(-1)^k\binom{2 n}{ k}^3-\sum_{k=0}^{n-1}(-1)^k\binom{2 n-1}{ k-1}^3-3 \sum_{k=0}^{n-1}(-1)^k\binom{2 n}{ k}^2\binom{2 n-1}{ k-1}-\binom{2 n}{ k}\binom{2 n-1}{ k-1}^2\right] \\ = & \frac{1}{2} \sum_{k=0}^{2 n}(-1)^k\binom{2 n}{ k}^3-\frac{1}{2}(-1)^n\binom{2 n}{ n}^3-\frac{1}{8 n^3} \sum_{k=0}^{n-1}(-1)^k k^3\binom{2 n}{ k}^3-3 \sum_{k=0}^{n-1}(-1)^k\binom{2 n}{ k}\binom{2 n-1}{ k-1}\binom{2 n-1}{ k}\end{aligned}

经过计算可得$$ \sum_{k=0}^{n-1}(-1)^k\binom{2 n}{k}\binom{2 n-1}{k-1}\binom{2 n-1}{k}=\frac{2 n-1}{2 n} \sum_{k=0}^{n-1}(-1)^k\binom{2 n}{k}^2\binom{2 n-2}{k-1} $$

再由著名的Dixon恒等式, 即$\sum_{k=0}^{2 n}(-1)^k\binom{2 n}{n}^3=(-1)^n\binom{2 n}{n}\binom{3 n}{n}$, 可得

\begin{aligned} & \sum_{k=0}^n(-1)^k B_{n, k}^3=-\frac{1}{2}\binom{2 n-1}{n}^3+\frac{2 n-3}{4 n}\binom{2 n}{n}^3-\frac{2 n-3}{4 n}\binom{2 n}{n}\binom{3 n}{n} \\ & +\frac{(-1)^n(2 n-3)(6 n-3)}{4 n^2} \sum_{k=0}^{n-1}(-1)^k\binom{2 n}{k}^2\binom{2 n-2}{k-1}+\frac{(-1)^n(2 n-3)}{16 n^4} \sum_{k=0}^{n-1}(-1)^k k^3\binom{2 n}{k}^3 \\ & =\frac{(2 n-1)^3}{2} C_{2 n-1, n}^3+\frac{(2 n-3)(n+1)^3}{4 n}\left(C_n\right)^3-\frac{(2 n-3)(3 n+3)}{4 n} C_{3 n, n} \cdot C_n \\ & +(-1)^n \frac{(2 n-3)(6 n-3)(n-1)}{4} \sum_{k=0}^{n-1} \frac{(-1)^k}{(n-k)^3} C_{2 n, k}^2 \cdot C_{2 n-2, k-1}+(-1)^n \frac{2 n-3}{16 n} \sum_{k=0}^{n-1} \frac{(-1)^k k^3}{(n-k)^3} C_{2 n, k}^3 \\ & \end{aligned}

对于 $\binom{m}{n}$ 和 $\binom{m}{n}^2$ 均有展开式, 具体表达式可参见文献[5], 下面将这两个结果进行推广, 从而得出 $\binom{m}{n}^p$ 的展开式.

定理5若m, n, p∈ ℕ₊, 则$$ \binom{m}{n}^p=\sum_{k=n}^m \frac{k^p-(k-n)^p}{n^p}\binom{k-1}{n-1}^p . $$

证 利用数学归纳法来证明这个定理.当m=n时, 等式显然成立.假设这个等式对于m恒成立, 现验证对于m+1的情形.\begin{aligned} & \sum_{k=n}^{m+1} \frac{k^p-(k-n)^p}{n^p}\binom{k-1}{n-1}^p=\binom{m}{n}^p+\frac{(m+1)^p-(m+1-n)^p}{n^p}\binom{m}{n-1}^p \\ = & {\left[\left(\frac{m-n+1}{m+1}\right)^p+\frac{(m+1)^p-(m+1-n)^p}{n^p}\left(\frac{n}{m+1}\right)^p\right]\binom{m+1}{n}^p=\binom{m+1}{n}^p . } \end{aligned}

故对于m+1的情况等式仍然成立.

注2 在定理5中取p=2即可得到文献[5]中定理2.3.

定理6 若m, n, p∈ ℕ₊, 则有如下展开式

$$ \sum_{k=1}^n C_{m, k}\left(H_k\right)^p=\binom{m-1}{n}\left(H_n\right)^p-\frac{1}{m} \sum_{k=1}^n H_k^{p-1} \sum_{i=0}^{p-1} \sum_{j=0}^i\binom{i}{j}\binom{m}{k}\left(\frac{-1}{k H_k}\right)^{i-j} . $$

证 当n=1时, 显然成立.假设上述等式对于n恒成立, 现验证对于n+1的情况.

$$\sum_{k=1}^{n+1} C_{m, k}\left(H_k\right)^p=\binom{m-1}{ n}\left(H_n\right)^p+\frac{m-2 n-2}{m}\binom{m}{ n+1}\left(H_{n+1}\right)^p-\frac{1}{m} \sum_{k=1}^n\left(H_k\right)^{p-1} \sum_{i=0}^{p-1} \sum_{j=0}^i\binom{i}{ j}\binom{m}{ k}\left(\frac{-1}{k \cdot H_k}\right)^{i-j}$$

由于

\begin{aligned} & \binom{m-1}{n}\left(H_n\right)^p+\frac{m-2 n-2}{m}\binom{m}{n+1}\left(H_{n+1}\right)^p \\ & =-\frac{1}{m}\binom{m}{n+1} \sum_{i=0}^{p-1} H_n^i\left(H_{n+1}\right)^{p-1-i}+\frac{m-n-1}{m}\binom{m}{n+1}\left(H_{n+1}\right)^p \\ & =-\frac{1}{m}\binom{m}{n+1} \sum_{i=0}^{p-1}\left(H_{n+1}-\frac{1}{n+1}\right)^i\left(H_{n+1}\right)^{p-1-i}+\binom{m-1}{n+1}\left(H_{n+1}\right)^p \\ & =\binom{m-1}{n+1}\left(H_{n+1}\right)^p-\frac{\left(H_{n+1}\right)^{p-1}}{m} \sum_{i=0}^{p-1} \sum_{j=0}^i\binom{i}{j}\binom{m}{n+1}\left(\frac{-1}{(n+1) H_{n+1}}\right)^{i-j}, \\ & \end{aligned}则有$$\sum_{k=1}^{n+1} C_{m, k}\left(H_n\right)^p=\binom{m-1}{n+1}\left(H_{n+1}\right)^p-\frac{1}{m} \sum_{k=1}^{n+1}\left(H_n\right)^{p-1} \sum_{i=0}^{p-1} \sum_{j=0}^i\binom{i}{j}\binom{m}{k}\left(\frac{-1}{k \cdot H_k}\right)^{i-j} \text {. }$$

故对于n+1的情况等式仍然成立.

注3 利用前面介绍的关系式A_{n, k}=C_{2n+1, n+1-k}和B_{n, k}=C_{2n, n-k}以及定理6便可得到$\sum_{k=1}^n\left(H_{n-k+1}\right)^p, \sum_{k=0}^{n-1} B_{m, k}\left(H_{n-k}\right)^p$的展开式.

推论1 若n∈ℕ₊, 则有$$ \sum_{k=1}^n C_{n, k}\left(H_k\right)^2=-\frac{2^{n+1} H_n}{n}+\frac{2^{n+1}}{n} \sum_{k=1}^n \frac{1}{2^k k}+\frac{1}{n} \sum_{k=1}^n\binom nk \frac{1}{k} $$

证 利用组合恒等式$$ \sum_{k=0}^n\binom{n}{k} H_k=2^n H_n-2^n \sum_{k=1}^n \frac{1}{2^k k} $$以及定理6即可得出结论.

定理7 若m, n∈ℕ₊, 则有如下组合恒等式$$ \sum_{k=1}^n C_{m, k}^2 H_k=\frac{m-2 n}{m}\binom{m-1}{n}^2 H_n-\frac{1}{m^3} \sum_{k=1}^n(m-2 k+2) k\binom{m}{k}^2+\frac{2}{m} \sum_{k=1}^n\binom{m-1}{k-1}^2 H_k . $$

证 当n=1时, 显然成立.假设上述等式对于n恒成立, 现验证对于n+1的情况.

\[ \sum_{k=1}^{n+1} C_{m, k}^2 H_k=\frac{m-2 n}{m}\binom{m-1}{n}^2 H_n-\frac{1}{m^3} \sum_{k=1}^n(m-2 k+2) k\binom{m}{k}^2+\frac{2}{m} \sum_{k=1}^n\binom{m-1}{k-1}^2 H_k+\left(\frac{m-2 n-2}{m}\binom{m}{n+1}\right)^2 H_{n+1} . \]

利用组合等式

$$ \left(\frac{m-2 n-2}{m}\binom{m}{n+1}\right)^2=\frac{m-2 n-2}{m}\binom{m-1}{n+1}^2-\frac{m-2 n}{m}\binom{m-1}{n}^2+\frac{2}{m}\binom{m-1}{n}^2 $$可得 \begin{aligned} \sum_{k=1}^{n+1} C_{m, k}^2 H_k & =\frac{m-2 n}{m}\binom{m-1}{ n}^2\left(H_n-H_{n+1}\right)-\frac{1}{m^3} \sum_{k=1}^n(m-2 k+2) k\binom{m}{ k}^2 \\ & +\frac{m-2 n-2}{m}\binom{m-1}{ n+1}^2 H_{n+1}+\frac{2}{m} \sum_{k=1}^{n+1}\binom{m-1}{ k-1}^2 H_k \\ = & \frac{m-2 n-2}{m}\binom{m-1}{ n+1}^2 H_{n+1}-\frac{1}{m^3} \sum_{k=1}^{n+1}(m-2 k+2) k\binom{m}{ k}^2+\frac{2}{m} \sum_{k=1}^{n+1}\binom{m-1}{ k-1}^2 H_k\end{aligned}

故对于n+1的情况等式仍然成立.

本文研究了Catalan三角数的组合等式, 得出了关于A_{n, k}、B_{n, k}的高次交错和的结果.在文献[5]的基础上进一步研究了Catalan三角数与Harmonic数的关系, 并将其推广到高次的情形, 从而得出了$\sum_{k=1}^n C_{m, k}\left(H_k\right)^p, \sum_{k=1}^n C_{m, k}^2 H_k$的展开式, 这为研究Catalan数与其他数的关系奠定了一定的基础.

References

[1]L W Shapiro.A Catalantriangle[J].Discrete Math., 1976, 14 (1) :83–90.

[2]E Barcucci, M C Verri.Some more properties of Catalan numbers[J].Discrete Math., 1992, 102 (3) :229–237.

[3] P Hilton, J Pedersen.Catalan Numbers, Their Generalization, and Their Uses[J].Math.Intell., 1991, 13 (2) :64–75.

[4] P J Miana, N Romero.Moments of combinatorial and Catalan numbers[J].J.of Number Theory, 2010, 130 (8) :1876–1887.

[5] P J.Miana, H Ohtsuka, N Romero.Sums of powers of Catalan triangle numbers[J], Discrete Math., 2017, 340 (10) :2388–2397.

[6] J M Gutiérrez, M A Hernández, P.J.Miana, et al.New identities in the Catalan triangle[J].J.Math.Anal.Appl., 2008, 341 (1) :52–61.

[7]P J Miana, N Romero.Computer proofs of new identities in the Catalan triangle[J].Adv.Appl.Statistics, 2010, 14 (1) :639–647.

[8] X J Chen, W C Chu.Moments on Catalan numbers[J].J.Math.Anal.Appl., 2009, 349 (2) :311–316.

[9]Z Z Zhang, B J Pang.Several Identities in the Catalan Triangle[J].Indian J.Pure Appl.Math., 2010, 41 (2) :363–378.

[10] J W Guo, J Zeng.Factors of binomial sums from the Catalan triangle[J].J.of Number Theory, 2010, 130 (1) :172–186.