OFFSET
0,9
COMMENTS
This is the third term of a sequence of generalized Narayana triangles (respectively Narayana polynomials). See A090181 for the classical case and A352687 for a discussion of the case k = 2. Many of the relations given there can be directly transferred to the present case. Here we emphasize the recurrence for the general case (see the formula section).
LINKS
Peter Luschny, Illustration of the polynomials.
FORMULA
Define Q(n, k) recursively as [A097805(n, k) for k = 0..n] if n <= k, and otherwise Q(n, k) = [(B(j) + B(j-1))*(2*(n - k) + 1) - (A(j) - 2*A(j-1) + A(j-2))*(n - k - 1)) / (n - k + 2), for j from n by -1 down to 3], where A(n) = Q(n - 2, k) '+' [0, 0] and B(n) = Q(n - 1, k) '+' [1]. a '+' b denotes the concatenation of the lists a and b. Then T(n) = Q(n, 3) is the n-th row of this triangle and the row sum equals 4*CatalanNumber(n - 2) if n >= 3.
Q(n, 1) are the rows of the Narayana triangle A090181 and Q(n, 2) the rows of A352687. It can be shown that Q(n, k)(m) >= Q(n, k + 1)(m) for k >= 1; thus A090181(n, k) >= A352687(n, k) >= T(n, k) >= Q(n, 4)(k) >= ... is an infinite weakly descending sequence for all terms of the sequence of triangles Q(n, k).
EXAMPLE
Triangle starts:
[0] 1;
[1] 0, 1;
[2] 0, 1, 1;
[3] 0, 1, 2, 1
[4] 0, 1, 3, 3, 1
[5] 0, 1, 5, 8, 5, 1
[6] 0, 1, 8, 19, 19, 8, 1
[7] 0, 1, 12, 41, 60, 41, 12, 1
[8] 0, 1, 17, 81, 165, 165, 81, 17, 1
[9] 0, 1, 23, 148, 406, 560, 406, 148, 23, 1
MAPLE
Q := proc(n, k) option remember; local A, B, j;
if n <= k then return [seq(binomial(n-1, j-1), j = 0..n)] fi; # A097805
A := [op(Q(n - 2, k)), 0, 0]; B := [op(Q(n - 1, k)), 1];
for j from n by -1 to 3 do
B[j] := ((B[j] + B[j-1])*(2*(n - k) + 1)
- (A[j] - 2*A[j-1] + A[j-2])*(n - k - 1)) / (n - k + 2);
od: B end:
Trow := n -> Q(n, 3): for n from 0 to 9 do print(Trow(n)) od:
MATHEMATICA
Q[n_, k_] := Q[n, k] = Module[{A, B, j},
If[n <= k, Return[Table[Binomial[n-1, j-1], {j, 0, n}]]];
A = Join[Q[n-2, k], {0, 0}]; B = Join[Q[n-1, k], {1}];
For[j = n, j >= 3, j--,
B[[j]] = ((B[[j]] + B[[j-1]])*(2*(n-k)+1)-
(A[[j]]-2*A[[j-1]]+A[[j-2]])*(n-k-1))/(n-k+2)];
B];
Trow[n_] := Q[n, 3];
Table[Trow[n], {n, 0, 9}] // Flatten (* Jean-François Alcover, Jul 07 2022, translated from Maple code *)
PROG
(Python)
from functools import cache
from math import comb
def comp(n, k): # compositions A097805
return comb(n-1, k-1) if k != 0 else k**n
@cache
def Trow(n, k):
if n <= k:
return [comp(n, j) for j in range(n + 1)]
A = Trow(n - 2, k) + [0, 0]
B = Trow(n - 1, k) + [1]
for j in range(n - 1, 1, -1):
B[j] = ((B[j] + B[j - 1]) * (2 * (n - k) + 1)
- (A[j] - 2 * A[j - 1] + A[j - 2]) * (n - k - 1)) // (n - k + 2)
return B
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Apr 29 2022
STATUS
approved