C/C++教程

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

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

目录
  • 模式避免的定义
  • 避免Pattern q 的n-排列计数$S_n(q)$
    • q长度是2
    • q长度是3
    • 对一些模式q,做$S_n(q)$的阶估计
    • Backelin, West, and Xin给出的较为一般的Theorem
    • q长度是4
  • 证明Stanley-Wilf conjecture
    • The Stanley-Wilf conjecture
    • The Füredi-Hajnal conjecture

模式避免的定义

image-20200809085809345

避免Pattern q 的n-排列计数\(S_n(q)\)

先扔结论,有时间把证明粘过来

q长度是2

\[S_n(12)=S_n(21)=1 \]

q长度是3

All patterns of length three are avoided by the same number of n-permutations.

\[S_n(123)=S_n(132)=S_n(213)=S_n(231)=S_n(312)=S_n(321)\\ S_{n}(132)=C_{n}=\frac{\left(\begin{array}{c} 2 n \\ n \end{array}\right)}{n+1} \]

对一些模式q,做\(S_n(q)\)的阶估计

image-20200809091549144

image-20200809091558968

Backelin, West, and Xin给出的较为一般的Theorem

image-20200809092432364

举例,
\(r=2,k=2,q=34\) it says, \(S_n(1234)=S_n(2134)\)
\(r=2,k=2,q=43\) it says, \(S_n(1243)=S_n(2143)\)
\(r=3,k=1,q=4\) it says, \(S_n(1234)=S_n(3214)\)

q长度是4

本来\(q\)有24种,可以证明最后归结为这三种代表,1234,1342,1324

\[\begin{aligned} &\text { for } S_{n}(1342) \text { we have } 1,2,6,23,103,512,2740,15485\\ &\text { for } S_{n}(1234) \text { we have } 1,2,6,23,103,513,2761,15767\\ &\text { for } S_{n}(1324) \text { we have } 1,2,6,23,103,513,2762,15793 \end{aligned} \]

aovid 1342 A022558

avoid 1234 A005802

avoid 1324 A061552

\[\begin{aligned} S_{n}(1342) &=(-1)^{n-1} \cdot \frac{\left(7 n^{2}-3 n-2\right)}{2} \\ &+3 \sum_{i=2}^{n}(-1)^{n-i} \cdot 2^{i+1} \cdot \frac{(2 i-4) !}{i !(i-2) !} \cdot\left(\begin{array}{c} n-i+2 \\ 2 \end{array}\right) \end{aligned} \]

\[S_{n}(1234)=2 \cdot \sum_{k=0}^{n}\left(\begin{array}{c} 2 k \\ k \end{array}\right)\left(\begin{array}{l} n \\ k \end{array}\right)^{2} \frac{3 k^{2}+2 k+1-n-2 n k}{(k+1)^{2}(k+2)(n-k+1)} \]

\[S_{n}(1234)=\frac{1}{(n+1)^{2}(n+2)} \sum_{k=0}^{n}\left(\begin{array}{c} 2 k \\ k \end{array}\right)\left(\begin{array}{c} n+1 \\ k+1 \end{array}\right)\left(\begin{array}{c} n+2 \\ k+1 \end{array}\right) \]

证明Stanley-Wilf conjecture

The Stanley-Wilf conjecture

image-20200809095149059

image-20200809095158075

书里给出的思路是先丢个 The Füredi-Hajnal conjecture出来,说这个 The Füredi-Hajnal conjecture可以推导Stanley-Wilf conjecture.

这样我们先来研究The Füredi-Hajnal conjecture

The Füredi-Hajnal conjecture

image-20200809100154408

\[f(n, P) \leq c_{p} n \]

先空着




资料来自网络

书用的是Combinatorics of permutations by Miklos Bona

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