Riordan arrays and number triangles

Riordan arrays and their A- and Z-sequences, inverses, triple factorizations, pseudo-involutions and total positivity, the Pascal and Pell matrices as Riordan arrays, Barry's triangles, triangular recurrence arrays extended to negative rows, and diagonal or row sums of triangles.

• A- and Z-sequences of Riordan arrays
• Barry's Stirling-like triangle
• Bell matrices
• Binomial interpolated triangles
• Degenerate harmonic numbers and Riordan arrays
• Diagonal sequences of square zig-zag shapes
• Exponential Riordan arrays of Pascal type
• Morgan–Voyce polynomials
• Ordinary Riordan Pascal-like triangles
• Pascal matrix
• Pell matrix as a Riordan array
• Total positivity of Riordan arrays
• Triangular recurrence arrays at negative indices

DefinitionBarry–Hennessy generalized Fibonacci numbers#✓fully proved

For a real number \(r\) and a natural number \(n\), the \(r\)-parameter generalized Fibonacci number is the real number

\[F_r(n) = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} r^k.\]

def rFibonacciNumber (r : ℝ) (n : ℕ) : ℝ :=
  ∑ k ∈ Finset.range (n / 2 + 1), (Nat.choose (n - k) k : ℝ) * r ^ k

Sources

• Paul Barry and Aoife Hennessy, Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms, Journal of Integer Sequences 12 (2009), Article 09.5.3.

TheoremConstant term and row sum of a shifted array#✓fully proved

Let \(R\) be a commutative semiring, let \((A_{i,k})_{i,k \in \mathbb{N}}\) be an array with entries in \(R\), and let \(r \in R\) and \(n \in \mathbb{N}\). For \(s \in R\) let \(A^{(s)}\) be the \(s\)-shifted array with entries \(A^{(s)}_{i,j} = \sum_{k=j}^{i} \binom{k}{j} A_{i,k} s^{k-j}\) (an empty sum when \(j > i\)), and let \(p(X) = \sum_{k=0}^{n} A^{(r)}_{n,k} X^k \in R[X]\) be the \(n\)-th row polynomial of \(A^{(r)}\). Then \(p(0) = A^{(r)}_{n,0} = \sum_{k=0}^{n} A_{n,k} r^k\) and \(p(1) = \sum_{k=0}^{n} A^{(r)}_{n,k} = A^{(r+1)}_{n,0}\).

theorem shiftedRiordanArray_constantTerm_and_sumCoefficients
    {R : Type*} [CommSemiring R] (A : ℕ → ℕ → R) (r : R) (n : ℕ) :
    let shifted : R → ℕ → ℕ → R := fun s i j =>
      ∑ k ∈ Finset.Icc j i, (Nat.choose k j : R) * A i k * s ^ (k - j)
    let p : Polynomial R :=
      ∑ k ∈ Finset.range (n + 1),
        Polynomial.C (shifted r n k) * Polynomial.X ^ k
    Polynomial.eval 0 p = shifted r n 0 ∧
      shifted r n 0 = ∑ k ∈ Finset.range (n + 1), A n k * r ^ k ∧
      Polynomial.eval 1 p =
        ∑ k ∈ Finset.range (n + 1), shifted r n k ∧
      (∑ k ∈ Finset.range (n + 1), shifted r n k) =
        shifted (r + 1) n 0

Sources

• José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, "On One-Parameter Catalan Arrays," Journal of Integer Sequences 18 (2015), Article 15.5.1, Corollary (equations eqColumn0Rr and eqRowsumsRr), lines 240–245, https://cs.uwaterloo.ca/journals/JIS/VOL18/Agapito/agapito2.tex

DefinitionDiagonal sums of an array#✓fully proved

For a doubly indexed array \((a_{i,j})_{i, j \ge 0}\) with entries in an additive commutative monoid \(M\), the \(n\)-th diagonal sum is \(d_n = \sum_{i + j = n} a_{i,j} = \sum_{k=0}^{n} a_{k,n-k}\).

If \(a\) is a lower-triangular array with \(a_{i,j}\) in row \(i\) and column \(j\), these are its sums along rising diagonals. For a Riordan array \((g, f)\), whose column \(j\) has generating function \(g(x) f(x)^j\), the sequence \((d_n)\) has generating function \(g(x) / (1 - x f(x))\).

public def diagonalSums {M : Type*} [AddCommMonoid M] (a : ℕ → ℕ → M) (n : ℕ) : M :=
  ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal n, a ij.1 ij.2

TheoremPeart–Woodson triple factorization of Riordan arrays#✓fully proved

Let \(b\) be an integer, let \(\varepsilon\), \(\delta\) and \(\lambda\) be real numbers, and let \(g\) and \(f\) be formal power series over \(\mathbb{R}\) with \(g(0) = 1\) and \(f(0) = 0\). Write \(r_{n,k}\) for the coefficient of \(x^n\) in \(g f^k\), and suppose that for all natural numbers \(n\) and \(k\)

\[r_{n+1,0} = (b + \varepsilon)\, r_{n,0} + (\lambda + \delta)\, r_{n,1},\]

\[r_{n+1,k+1} = r_{n,k} + b\, r_{n,k+1} + \lambda\, r_{n,k+2},\]

that is, the Riordan array \((g, f)\) has dot diagram \([b + \varepsilon, \lambda + \delta; 1, b, \lambda]\). With the Riordan product \((p_1, p_2) \ast (q_1, q_2) = (p_1 \cdot q_1(p_2),\, q_2(p_2))\), let \(P_b = \bigl(1/(1 - bx),\, x/(1 - bx)\bigr)\) and \(C_\lambda = \bigl(c(\lambda x^2),\, x\, c(\lambda x^2)\bigr)\), where \(c(x) = \sum_{m \ge 0} C_m x^m\) is the generating function of the Catalan numbers \(C_m\), and let \(F_{\varepsilon,\delta} = \bigl(1/(1 - \varepsilon x - \delta x^2),\, x\bigr)\). Then \((g, f) = (P_b \ast C_\lambda) \ast F_{\varepsilon,\delta}\).

MetaMathlibExt.triple_factorization_of_dot_diagram · 23 lines

theorem triple_factorization_of_dot_diagram
    (b : ℤ) (ε δ lam : ℝ) (g f : PowerSeries ℝ)
    (hg : PowerSeries.constantCoeff g = 1)
    (hf : PowerSeries.constantCoeff f = 0) :
    let coeff := fun (p : PowerSeries ℝ) (n : ℕ) => PowerSeries.coeff n p
    let entry := fun (n k : ℕ) => coeff (g * f ^ k) n
    let hasDot :=
      (∀ n : ℕ, entry (n + 1) 0 = ((b : ℝ) + ε) * entry n 0 + (lam + δ) * entry n 1) ∧
      (∀ n k : ℕ, entry (n + 1) (k + 1) =
        entry n k + (b : ℝ) * entry n (k + 1) + lam * entry n (k + 2))
    let compose := fun (p q : PowerSeries ℝ) => PowerSeries.subst q p
    let mul := fun (p q : PowerSeries ℝ × PowerSeries ℝ) =>
      (p.1 * compose q.1 p.2, compose q.2 p.2)
    let X : PowerSeries ℝ := PowerSeries.X
    let cat : PowerSeries ℝ := PowerSeries.mk fun n => (catalan n : ℝ)
    let catLam := compose cat (PowerSeries.C lam * X ^ 2)
    let Pb : PowerSeries ℝ × PowerSeries ℝ :=
      ((1 - PowerSeries.C (b : ℝ) * X)⁻¹,
       X * (1 - PowerSeries.C (b : ℝ) * X)⁻¹)
    let CLam : PowerSeries ℝ × PowerSeries ℝ := (catLam, X * catLam)
    let Fεδ : PowerSeries ℝ × PowerSeries ℝ :=
      ((1 - PowerSeries.C ε * X - PowerSeries.C δ * X ^ 2)⁻¹, X)
    hasDot → (g, f) = mul (mul Pb CLam) Fεδ

Sources

• Cameron and Nkwanta, Riordan multiplication at lines 113–117 and the dot-diagram recursions at lines 124–138.
• Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences 8 (2005), Article 05.3.7, Triple Factorization theorem due to Peart and Woodson, line 339, reused in the proof at line 373, https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.tex.

TheoremTwin Powers Theorem for pseudo-involutions#✓fully proved

Let \(l\) be a natural number, let \(n = 2l + 1\), and let \(g\) be a formal power series over \(\mathbb{R}\) with \(g(0) \ne 0\). Put \(f(x) = x\, g(x^n)\) and \(h(x) = x\, g(x)^n\). Call a power series \(p\) pseudo-involutory if \(p(0) = 0\), the coefficient of \(x\) in \(p\) is nonzero, and the compositional inverse \(\bar p\) of \(p\) satisfies \(\bar p(x) = -p(-x)\); call \(B\) a B-function of \(p\) if \(p(x) - x = x\, p(x)\, B(x\, p(x))\). Let

\[P(x) = \sum_{j=0}^{l} \frac{2l+1}{2j+1} \binom{l+j}{2j} x^j.\]

Suppose that \(B_f\) is a B-function of \(f\), that \(B_h\) is a B-function of \(h\), and that \(f\) or \(h\) is pseudo-involutory. Then \(f\) and \(h\) are both pseudo-involutory, and

\[x^n B_h(x^n)^2 = x B_f(x)^2 \, P\bigl(x B_f(x)^2\bigr)^2.\]

MetaMathlibExt.twin_powers · 28 lines

theorem twin_powers
    (l : ℕ)
    (g : PowerSeries ℝ)
    (Bf : PowerSeries ℝ)
    (Bh : PowerSeries ℝ)
    (hg : PowerSeries.constantCoeff g ≠ 0) :
    let Xr : PowerSeries ℝ := PowerSeries.X
    let n := 2 * l + 1
    let f := Xr * g.subst (Xr ^ n)
    let h := Xr * g ^ n
    let IsPseudoInvolutory := fun p : PowerSeries ℝ =>
      PowerSeries.constantCoeff p = 0 ∧
        ∃ hp : IsUnit (PowerSeries.coeff 1 p),
          p.substInvOfIsUnit hp = -(p.subst (-Xr))
    let IsBFunction := fun p B : PowerSeries ℝ =>
      p - Xr = (Xr * B).subst (Xr * p)
    let P : PowerSeries ℝ :=
      Finset.sum (Finset.range (l + 1)) (fun j : ℕ =>
        (PowerSeries.C
            ((((2 * l + 1 : ℕ) : ℝ) / ((2 * j + 1 : ℕ) : ℝ)) *
              (Nat.choose (l + j) (2 * j) : ℝ)) : PowerSeries ℝ) *
          Xr ^ j)
    (IsPseudoInvolutory f ∨ IsPseudoInvolutory h) →
      IsBFunction f Bf →
      IsBFunction h Bh →
      IsPseudoInvolutory f ∧ IsPseudoInvolutory h ∧
        (Xr * Bh ^ 2).subst (Xr ^ n) =
          (Xr * P ^ 2).subst (Xr * Bf ^ 2)

Sources

• Alexander Burstein and Louis W. Shapiro, "Pseudo-Involutions in the Riordan Group," Journal of Integer Sequences 25 (2022), Article 22.3.6, The Twin Powers Theorem, lines 1129–1146, https://cs.uwaterloo.ca/journals/JIS/VOL25/Burstein/burstein14.tex

5 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.