卡特兰路径和q,t-enumeration 学一半的笔记

本文主要是介绍卡特兰路径和q,t-enumeration 学一半的笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• 卡特兰
  • The1st q-analogue of $C_n$
  • The 2nd q-analogue of $C_n$ /定义$C_n(q)$
• The q-Vandermonde convolution/q-范特蒙德卷积
  • 这么定义the basic 超几何级数
  • Cauchy's q-binomial theorem
  • 推论11.2.11 The q-binomial theorem
  • 推论 11.2.12
  • 推论11.2.13
  • The q-Vandermonde convolution

前面写了这篇q-analog的博客，

这里趁热打铁 2020-08-27 18:19

下面的内容来自Handbook of Enumerative Combinatorics by Miklos Bona

的第11章 Catalan Paths and q,t-enumeration

写不完写不完看不懂看不懂 2020-09-05 20:46

卡特兰

The1st q-analogue of \(C_n\)

\[\sum_{\pi \in L_{n, n}^{+}} q^{\operatorname{maj}(\sigma(\pi))}=\frac{1}{[n+1]}\left[\begin{array}{c} 2 n \\ n \end{array}\right] \]

这个上篇博客写过

拿下面的图举例子，\(n=3\)，000111，001011，001101，010011，010101

maj分别是0，3，4，2，6

\[\begin{aligned} q^0+q^3+q^4+q^2+q^6 &=\frac{1}{1+q+q^2+q^3}\cdot\frac{(1-q^6)(1-q^5)(1-q^4)}{(1-q^3)(1-q^2)(1-q^1)} \\ &=\frac{1}{1+q+q^2+q^3}\cdot(1+q^2)(1+q^3)(1+q+q^2+q^3+q^4) \\ &=\frac{1}{1+q+q^2+q^3}\cdot(1+q+2q^2+3q^3+3q^4+3q^5+3q^6+2q^7+q^8+q^9) \\ &=1+q^2+q^3+q^4+q^6 \end{aligned} \]

The 2nd q-analogue of \(C_n\) /定义\(C_n(q)\)

我理解没错的话，Carlitz-Riordan area 是说路径和\(y=x\)对角线相交区域中完整的正方形个数

这么定义\(C_n(q)=\sum_{\pi \in L_{n, n}^{+}} q^{\operatorname{area}(\pi)}\)的话，

有递归方程

\[C_{n}(q)=\sum_{k=1}^{n} q^{k-1} C_{k-1}(q) C_{n-k}(q), \quad n \geq 1 \]

这么定义的\(C_n(q)\)还能和co-inversion联系起来

The q-Vandermonde convolution/q-范特蒙德卷积

这么定义the basic 超几何级数

\[p+1 \phi_{p}\left(\begin{array}{ccc} a_{1}, & a_{2}, & \ldots, & a_{p+1} \\ & b_{1}, & \ldots, & b_{p} \end{array} ; q ; z\right)=\sum_{k=0}^{\infty} \frac{\left(a_{1}\right)_{k} \cdots\left(a_{p+1}\right)_{k}}{(q)_{k}\left(b_{1}\right)_{k} \cdots\left(b_{p}\right)_{k}} z^{k} \]

其中\((a)_k\)表示升阶乘，即\((a)_k=a(a+1)...(a+k-1)\)

Cauchy's q-binomial theorem

\[{ }_{1} \phi_{0}\left(\begin{array}{ll} a & \\ - & \end{array} ; q ; z\right)=\sum_{k=0}^{\infty} \frac{(a)_{k}}{(q)_{k}} z^{k}=\frac{(a z)_{\infty}}{(z)_{\infty}}, \quad|z|<1,|q|<1 \]

where,

\[(a ; q)_{\infty}=(a)_{\infty}=\prod_{i=0}^{\infty}\left(1-a q^{i}\right) \]

推论11.2.11 The q-binomial theorem

\[\sum_{k=0}^{n} q^{\left(\begin{array}{c} k \\ 2 \end{array}\right)}\left[\begin{array}{l} n \\ k \end{array}\right] z^{k}=(-z ; q)_{n} \]

\[\sum_{k=0}^{\infty}\left[\begin{array}{c} n+k \\ k \end{array}\right] z^{k}=\frac{1}{(z ; q)_{n+1}} \]

推论 11.2.12

\[\sum_{k=0}^{h} q^{(n-k)(h-k)}\left[\begin{array}{l} n \\ k \end{array}\right]\left[\begin{array}{c} m \\ h-k \end{array}\right]=\left[\begin{array}{c} m+n \\ h \end{array}\right] \text { holds. } \]

推论11.2.13

\[\sum_{k=0}^{h} q^{(m+1) k}\left[\begin{array}{c} n-1+k \\ k \end{array}\right]\left[\begin{array}{c} m+h-k \\ h-k \end{array}\right]=\left[\begin{array}{c} m+n+h \\ h \end{array}\right] \]

The q-Vandermonde convolution

。。。这个为什么是拿超几何级数来写的。。。。

   

剩下的空着

这篇关于卡特兰路径和q,t-enumeration 学一半的笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！