Motzkin numbers and Motzkin paths

Motzkin numbers and paths: colored, weighted and (u,l,d) Motzkin paths, humps and peaks, the Motzkin triangle, links with central trinomial coefficients, alternating Motzkin sums, Aigner's inequality, and Motzkin-related sequences such as A005773; weighted Motzkin paths used to compute Hankel determinants go to Hankel determinants and continued fractions.

• Colored Motzkin paths of rank r
• Cubic lattice walks and colored Motzkin paths
• Generalized Motzkin numbers modulo primes
• Log-behavior of Motzkin prefix numbers
• Motzkin numbers
• Aigner's ratio inequality for Motzkin numbers
• Alternating sums of Motzkin numbers
• Humps and peaks in Motzkin paths
• Motzkin triangle

TheoremGenerating function of binomial Motzkin paths#✓fully proved

Let \(t \ge 1\). A binomial \([t]\)-Motzkin step is one of \(\binom{t}{k}\) differently colored steps that change the height by \(1 - k\), for some \(k \in \{0, 1, \dots, t\}\). For \(n \ge 0\) let \(M_n\) be the number of sequences of \(n\) such steps for which, starting from height \(0\), the height after the first \(m\) steps is nonnegative for every \(0 \le m \le n\) and the height after all \(n\) steps is \(0\). Then, as formal power series over \(\mathbb{Q}\),

\[\sum_{n \ge 0} M_n z^n = C_t(z)^t, \qquad C_t(z) = \sum_{n \ge 0} \frac{1}{(t-1)n + 1} \binom{tn}{n} z^n.\]

theorem binomial_tMotzkin_generatingFunction
    (t : ℕ) (ht : 1 ≤ t) :
    let Step := Σ k : Fin (t + 1), Fin (Nat.choose t k)
    let heightChange : Step → ℤ := fun s => 1 - (s.1 : ℤ)
    let pathCount : ℕ → ℕ := fun n =>
      Fintype.card {p : Fin n → Step //
        (∀ m : Fin (n + 1),
          0 ≤ ∑ i : Fin n, if i.1 < m.1 then heightChange (p i) else 0) ∧
        ∑ i : Fin n, heightChange (p i) = 0}
    let catalanGF : PowerSeries ℚ := PowerSeries.mk fun n =>
      (Nat.choose (t * n) n : ℚ) / (((t - 1) * n + 1 : ℕ) : ℚ)
    PowerSeries.mk (fun n => (pathCount n : ℚ)) = catalanGF ^ t

Sources

• Naiomi T. Cameron and Jillian E. McLeod, "Returns and Hills on Generalized Dyck Paths," Journal of Integer Sequences 19 (2016), Article 16.6.1, Theorem (binomial [t]-Motzkin generating function), lines 987–989, https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.tex

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.