【读书笔记】排列研究-模式避免-续篇Pattern Avoidance

2021/6/6 10:30:34

本文主要是介绍【读书笔记】排列研究-模式避免-续篇Pattern Avoidance,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 多项式递归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定义

image-20200811110412572

更多的内容看我的这篇播客园博客

例子:卡特兰数序列是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的推断

image-20200811112157639

本篇用到的一些定义和记号

\(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)\)

image-20200813125420669

书中后面很大的篇幅都是在证明这个定理或者做准备工作

定义

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

图示

image-20200813130305205

为什么我们给排列的元素染色?性质

  1. 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.

    前元素中,任何黑元素都要比非黑元素小;后元素中,任何灰元素都要比非灰元素大

  2. 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

image-20200813131023598

amazing啊

定义

fundamental subsequence of \(p\)

image-20200813131256582

两个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



这篇关于【读书笔记】排列研究-模式避免-续篇Pattern Avoidance的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程