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

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

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

Theorem (André ,1887) 5 ◎Generating function 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

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

Dyck paths 2-Fuss paths

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

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

m-Fuss paths Dyck paths 2-Fuss paths

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

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

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

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

Yes, we find it！ 15

Main results

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

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

n=2 有14個Skew 2-Fuss paths

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

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

proof ： step2： step3：用Lagrange Inversion formula 22

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

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

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

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

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

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

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

proof ： step2： step3：用Lagrange Inversion formula 30

m 1 2 3 4 5 6 1, 1, 3, 10, 36, 137, …… 1, 2, 14, 118, 1114, 11306, …… 1, 4, 64, 1296, 29888, 745856, …… 1, 8, 288, 13568, 734720, 43202560, …… 1, 16, 1280, 137216, 17006592, 2293825536,…… 1, 32, 5632, 1351680, 376569856, 114340921344,…… 31

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

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

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

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

proof ： step2： step3：用Lagrange Inversion formula 36

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

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

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

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

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

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

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

THANK YOU！