On Skew Fuss Paths Li-Chih Chen 陳立志 指導教授：游森棚教授 Aug 11, 2013

Presentation on theme: "On Skew Fuss Paths Li-Chih Chen 陳立志 指導教授：游森棚教授 Aug 11, 2013"— Presentation transcript:

1 On Skew Fuss Paths Li-Chih Chen 陳立志 指導教授：游森棚教授 Aug 11, 2013
Department of Applied Mathematics National University of Kaohsiung, ROC Aug 11, 2013

2 Outline • Introduction Dyck paths Fuss paths
Skew Dyck paths Skew Fuss paths • Main results • Idea of proof • Discussions and future work

3 Dyck paths Definition 長度為 n 的 Dyck paths：＝ ◎起點 (0,0)，終點 (2n,0)
◎使用向上步" " U (1,1)與向下步" " D (1,-1) ，且不落在 x 軸之下。 ◎長度 n 是指其向上步 U 的個數。 n=3 有5個Dyck paths

4 Theorem (André ,1887) 5 ◎Generating function 5

5 2-Fuss paths Definition(Fuss,1795,Bertrand,1887)
長度為 n 的 2-Fuss paths：＝ ◎起點 (0,0)，終點落於 x 軸。 ◎使用向上步 U(2,2)與向下步 D(1,-1)，且不落在 x 軸之下。 ◎長度 n 是指其向上步 U 的個數。 n=2 U D 有3個2-Fuss paths

6 Theorem (Fuss,1795,Bertrand,1887)
3 ◎Generating function 3

7 Dyck paths 2-Fuss paths

8 m-Fuss paths Definition (Fuss,1795,Bertrand,1887)
長度為 n 的 m-Fuss paths：＝ ◎起點 (0,0)，終點落於 x 軸。 ◎使用向上步 U(m,m)與向下步 D(1,-1) ，且不落在 x 軸之下。 ◎長度 n 是指其向上步 U 的個數。 n=2 m格 m格 U D 有4個 3-Fuss paths

9 Theorem (Fuss,1795,Bertrand,1887)
◎ ◎Generating function

10 m-Fuss paths Dyck paths 2-Fuss paths

11 Skew Dyck paths Definition (Deutsch et al,2010)
長度為 n 的 Skew Dyck paths：＝ ◎起點 (0,0)，終點落於 x 軸。 ◎使用向上步 U(1,1)、右下步 D(1,-1)與左下步 L (-1,-1) ，且不落在 x 軸之下。 ◎長度 n 是指其向上步 U 的個數。 n=2 U D L 有3個Skew Dyck paths

12 Theorem (Deutsch et al,2010)
◎ ◎Generating function 3 3

13 m-Fuss paths Dyck paths 2-Fuss paths Skew Dyck paths

14 Our question… m-Fuss paths Dyck paths 2-Fuss paths Skew Dyck paths ？ ？

15 Yes, we find it！ 15

16 Main results

17 m-Fuss paths Dyck paths 2-Fuss paths Skew 2-Fuss paths Skew m-Fuss paths Skew Dyck paths

18 Skew 2-Fuss paths Definition 5.1 (Chen,2013)
長度為 n 的 Skew 2-Fuss paths：＝ ◎起點 (0,0) ，終點落於 x 軸。 ◎使用向上步 U(2,2)、右下步 D(1,-1)與左下步 L (-1,-1) ，且不落在 x 軸之下。 ◎長度 n 是指其向上步 U 的個數。 有2個Skew 2-Fuss paths n=1 U D L

19 n=2 有14個Skew 2-Fuss paths

20 Theorem 5.2 (Chen,2013) Theorem 5.3 (Chen,2013) 14 14
Generating function 14 Theorem 5.3 (Chen,2013) 14

21 proof ： step1：利用結構拆解法 USD’SD”S USD’SL’ U(S-1)L’L” U(S-1)L’D’S 21

22 proof ： step2： step3：用Lagrange Inversion formula 22

23 Skew m-Fuss paths Definition 5.4 (Chen,2013)
長度為 n 的 Skew m-Fuss paths：＝ ◎起點 (0,0)，終點落於 x 軸。 ◎使用向上步 U(m,m)、右下步 D(1,-1)與左下步 L (-1,-1)，且不落在 x 軸之下。 ◎長度 n 是指其向上步 U 的個數。 m格 U L D

24 ◎ Generating function Theorem 5.5 (Chen,2013) Theorem 5.6 (Chen,2013)

25 proof ： step1：利用數學歸納法及結構拆解導出 已知 m=1 時成立(即定理4.2) 已知 m=2 時成立(即定理5.2)
假設 Skew m-Fuss paths 時成立 證明 Skew (m+1)-Fuss paths 時也成立 設 Skew (m+1)-Fuss paths 的生成函數記為 S 25

26 proof ： 依第一次下降到 y=1 及 y=0 分類，並令第 一次下降到 y=0 的單位步的起點為 P，可 分成 4 種類型：
(Ⅰ) LD (Ⅱ) LL (Ⅲ) DD (Ⅳ) DL 26

27 proof ： case1： ◎(Ⅰ)(Ⅱ) 型：第一次下降到 y=1 的上一步是 L 的路徑。
◎在(Ⅰ)(Ⅱ)型中，先考慮 y=1 之上的路徑，就是以(1,1)為起點，P 為終點的路徑。 ◎(Ⅰ)型的路徑＝原點到 P 的路徑 × （S） ◎(Ⅱ)型的路徑＝原點到 P 的路徑 × （1） ◎(Ⅰ)(Ⅱ) 型相當於以原點為起點，P為終點的路徑，乘上(S+1)。 27

28 proof ： case2： ◎(Ⅲ)(Ⅳ) 型：第一次下降到 y=1 的上一步是 D 的路徑。
◎在(Ⅲ)(Ⅳ)中，先考慮 y=1 之上的路徑，就是以(1,1)為起點，P 為終點的路徑。 ◎(Ⅲ)型的路徑＝原點到 P 的路徑 × （S） ◎(Ⅳ)型的路徑＝原點到 P 的路徑 × （1） ◎(Ⅲ)(Ⅳ) 型相當於以原點為起點，P 為終點的路徑，乘上(S+1) 28

29 proof ： 原點走到P的函數方程由數學歸納法假設為 滿足S的函數方程 = 原點走到P乘上(S+1), 即 29

30 proof ： step2： step3：用Lagrange Inversion formula 30

31 m 1 2 3 4 5 6 1, 1, 3, 10, 36, 137, …… 1, 2, 14, 118, 1114, 11306, …… 1, 4, 64, 1296, 29888, , …… 1, 8, 288, 13568, , , …… 1, 16, 1280, , , ,…… 1, 32, 5632, , , ,…… 31

32 m-Fuss paths Dyck paths 2-Fuss paths Skew 2-Fuss paths Skew m-Fuss paths Skew Dyck paths

33 按照向左步的計數(Skew 2-Fuss paths) Theorem 5.7
◎Generating function n=2 33

34 按照向左步的計數(Skew 2-Fuss paths)
Theorem 5.8 ： 34

35 proof ： step1：利用結構拆解 ，將左下步標記為 y 35

36 proof ： step2： step3：用Lagrange Inversion formula 36

37 按照向左步的計數(Skew m-Fuss paths)
Theorem 5.9 ◎Generating function 37

38 Discussions and future work
1.數論性質 （1）Dyck paths(Catalan數) （2）Fuss paths(Fuss Catalan數)

39 Discussions and future work
1. 數論性質 （3）Skew 2-Fuss paths Theorem 6.1 證明：定義 ψ： → ψ(……L) ＝……D，且ψ(……D) ＝……L ，顯然是一個 involution，ψ將所有 中的路徑二二配對，故 必為偶數。 n=2 39

40 Discussions and future work
1. 數論性質 （3）Skew 2-Fuss paths Question： Skew m-Fuss paths 的數論性質？ Conjectures： 40

41 Discussions and future work
2. 細分 Dyck Paths： 按照山峰數 Narayana numbers 按照隧道（tunnel）數 Narayana numbers 按照區塊（block）數 Ballot numbers 按照第一個山峰的高度 Ballot numbers 按照高度（height） Height distribution Question： Skew m-Fuss paths 按照以上細分是否有結果？ 41

42 Discussions and future work
3. Skew 2-Fuss paths 按" " 步的細分 (★) Question：(★) 有簡單的証明嗎？ 42

43 Discussions and future work
4. 組合結構？ ◎There are Catalan Structures ◎There are Fuss Structures Question： Skew m-Fuss paths families？？

44 THANK YOU！