目录
多项式递归Polynomial Recursions
P-recursive和c-recursive定义
例子：卡特兰数序列是P-recursive（或者说D-finite）
两个说明\(S_n(q)\)和\(S_{n,r}(q)\)nice的推断
本篇用到的一些定义和记号
rational algebraic D-finite
The P-recursiveness of \(S_{n,r}(132)\)
定义
front entries
back entries
black entries
grey entries
图示
为什么我们给排列的元素染色？性质
定义a 132-subsequence spans over the entry \(n\)
定义two permutations in the same strong class
定义
fundamental subsequence of \(p\)
两个class相似
same type
书中基础篇很大的篇幅讨论了\(S_n(q)\)的一些渐进性质
续篇里试图说明\(S_n(q)\) how nice
多项式递归Polynomial Recursions
P-recursive和c-recursive定义
更多的内容看我的这篇播客园博客
例子：卡特兰数序列是P-recursive（或者说D-finite）
证明1
\[\sum_{n \geq 0} \frac{1}{n+1}\left(\begin{array}{c}
2 n \\
n
\end{array}\right) x^{n}=\frac{2}{1 \pm \sqrt{1-4 x}}
\]可以看到是algebraic,自然也是D-finite
证明2
\[(n+1)C_n-(4n-2)C_n-1=0
\]
两个说明\(S_n(q)\)和\(S_{n,r}(q)\)nice的推断
本篇用到的一些定义和记号
\(P\) be the infinite partially ordered set of all finite permutations ordered by pattern containment. 偏序关系是说\(p\le q\) 如果\(q\) contains \(p\) as a pattern
\(C\) a class consisting of finite permutations
\(C\) is a closed class of permutations <=> if \(q\in C\)且\(p\le q\) then \(p \in C\)
rational algebraic D-finite
更多的内容看我的这篇播客园博客
The P-recursiveness of \(S_{n,r}(132)\)
书中后面很大的篇幅都是在证明这个定理或者做准备工作
定义
front entries
Entries of an n-permutation p on the left of the entry n
back entries
those on the right of n
black entries
front entries中比【back entries最大】要小的元素构成 black entries
grey entries
back entries中比【front entries最小】要大的元素构成grey entries
图示
为什么我们给排列的元素染色？性质
any black entry is smaller than any front entry which is not black， while any gray entry is larger than any back entry which is not gray.
前元素中，任何黑元素都要比非黑元素小；后元素中，任何灰元素都要比非灰元素大
any black and any gray entry is part of at least one 132-subsequence
定义a 132-subsequence spans over the entry \(n\)
it starts with a front entry and ends with a back entry, then it must start with a black one and end with a gray one.
定义two permutations in the same strong class
amazing啊
定义
fundamental subsequence of \(p\)
两个class相似
The classes C and C’ are called similar if their permutations have fundamental subsequences of the same type.
same type
same type 是说
In the symmetric group \(S_n\), two permutations \(g\) and \(h\) are called conjugates of each other if there exists an element so that \(ƒgƒ^{-1}=h\) holds.
先写到这
资料来自网络
书用的是Combinatorics of permutations by Miklos Bona
