Catalan numbers and their generalizations

Catalan numbers and generalizations defined by formulas or recurrences: Fuss–Catalan, super Catalan, (p,q)-Patalan, Whitt and Sabar arrays, generalized Catalan–Schröder, Fine and Riordan numbers, Narayana numbers and polynomials, Touchard's identity, Raney's cycle lemma, and divisibility or growth of these numbers.

TheoremClosed form of the Eloe–Kublik gamma array#✓fully proved

Let \(\gamma_{n,k}\), for natural numbers \(n\) and \(k\), be real numbers such that \(\gamma_{n,0} = 1\) for every \(n\), \(\gamma_{2n-1,n} = 0\) for every \(n \ge 1\), and

\[\gamma_{n,k} = (1 + \frac{2k}{n+2})\,\gamma_{n-1,k} + \frac{2k-n-1}{n+2}\,\gamma_{n-1,k-1}\]

whenever \(n \ge 2\) and \(1 \le k \le \lfloor n/2 \rfloor\). Then \(\gamma_{n,k} = (-\frac{1}{4})^k \binom{n}{2k} C_k\) for all natural numbers \(n\) and \(k\) with \(k \le \lfloor n/2 \rfloor\), where \(C_k\) is the \(k\)-th Catalan number.

theorem gamma_closed_form : ∀ (γ : ℕ → ℕ → ℝ),
    (∀ n : ℕ, γ n 0 = 1) →
    (∀ n : ℕ, 1 ≤ n → γ (2 * n - 1) n = 0) →
    (∀ n k : ℕ, 2 ≤ n → 1 ≤ k → k ≤ n / 2 →
      γ n k = (1 + 2 * (k : ℝ) / ((n : ℝ) + 2)) * γ (n - 1) k +
        (2 * (k : ℝ) - (n : ℝ) - 1) / ((n : ℝ) + 2) * γ (n - 1) (k - 1)) →
    ∀ n k : ℕ, k ≤ n / 2 →
      γ n k = (-1 / 4 : ℝ) ^ k * (Nat.choose n (2 * k) : ℝ) * (catalan k : ℝ)
Sources
  • Paul Eloe and Catherine Kublik, "When Numerical Analysis Crosses Paths with Catalan and Generalized Motzkin Numbers," Journal of Integer Sequences 21 (2018), Article 18.8.4, Theorem closedform_thm, lines 390-396, https://cs.uwaterloo.ca/journals/JIS/VOL21/Kublik/kublik2.tex; the recursion and initial conditions are equation gamma_linear_recursion, lines 87-91.

DefinitionPalindromic Narayana numbers#✓fully proved

For natural numbers \(n\) and \(k\), the palindromic Narayana number is the rational number \(\tilde{N}(n, k) = \binom{n}{k} \binom{n+1}{k} / (k+1)\).

The value is taken in \(\mathbb{Q}\) so that the displayed quotient is represented literally.

def palindromicNarayanaNumber (n k : ℕ) : ℚ :=
  (n.choose k : ℚ) * ((n + 1).choose k : ℚ) / (k + 1 : ℚ)
Sources

TheoremTouchard's Catalan identity#✓fully proved

For every natural number \(n\), writing \(C_k = \binom{2k}{k}/(k+1)\) for the \(k\)-th Catalan number,

\[C_{n+1} = \sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n}{2i} 2^{n-2i} C_i.\]
theorem touchard_catalan_identity (n : Nat) :
    catalan (n + 1) =
      (Finset.range (n / 2 + 1)).sum
        (fun i => catalan i * 2 ^ (n - 2 * i) * Nat.choose n (2 * i))
Sources
  • https://cs.uwaterloo.ca/journals/JIS/VOL20/Dershowitz/dersh3.tex, lines 274-277. A second JIS source prints the finite upper bound as floor(n/2).

TheoremVon Szily's identity for super Catalan numbers#✓fully proved

For all natural numbers \(m\) and \(n\),

\[ \left\lfloor \frac{(2m)!\,(2n)!}{m!\,n!\,(m+n)!} \right\rfloor = \sum_{k=\max(-m,-n)}^{\min(m,n)} (-1)^k \binom{2m}{m+k} \binom{2n}{n+k}, \]

where the sum runs over the integers \(k\) with \(\max(-m, -n) \le k \le \min(m, n)\).

The quotient inside the floor is the super Catalan number \(S(m, n)\). The source sums over all \(k \in \mathbb{Z}\); only the terms in this range are nonzero.

theorem von_szily_super_catalan_identity (m n : ℕ) :
    (((2 * m).factorial * (2 * n).factorial /
        (m.factorial * n.factorial * (m + n).factorial) : ℕ) : ℤ) =
      ∑ k ∈ Finset.Icc (max (-(m : ℤ)) (-(n : ℤ))) (min (m : ℤ) (n : ℤ)),
        (-1 : ℤ) ^ k.natAbs *
          (Nat.choose (2 * m) (Int.toNat ((m : ℤ) + k)) : ℤ) *
          (Nat.choose (2 * n) (Int.toNat ((n : ℤ) + k)) : ℤ)
Sources
  • Kendra Killpatrick, Super FiboCatalan Numbers and Their Lucas Analogues, Journal of Integer Sequences 28 (2025), Article 25.5.8, von Szily identity quoted in the Open problems section, lines 671–674, https://cs.uwaterloo.ca/journals/JIS/VOL28/Killpatrick/killp6.tex, citing I. Gessel, Super ballot numbers, J. Symbolic Comput. 14 (1992), p. 11.
4 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.