cp's OEIS Frontend

A352687 Triangle read by rows, a Narayana related triangle whose rows are refinements of twice the Catalan numbers (for n >= 2).

%I A352687 #38 Aug 06 2024 11:31:30
%S A352687 1,0,1,0,1,1,0,1,2,1,0,1,4,4,1,0,1,7,12,7,1,0,1,11,30,30,11,1,0,1,16,
%T A352687 65,100,65,16,1,0,1,22,126,280,280,126,22,1,0,1,29,224,686,980,686,
%U A352687 224,29,1,0,1,37,372,1512,2940,2940,1512,372,37,1
%N A352687 Triangle read by rows, a Narayana related triangle whose rows are refinements of twice the Catalan numbers (for n >= 2).
%C A352687 This is the second triangle in a sequence of Narayana triangles. The first is A090181, whose n-th row is a refinement of Catalan(n), whereas here the n-th row of T is a refinement of 2*Catalan(n-1). We can show that T(n, k) <= A090181(n, k) for all n, k. The third triangle in this sequence is A353279, where also a recurrence for the general case is given.
%C A352687 Here we give a recurrence for the row polynomials, which correspond to the recurrence of the classical Narayana polynomials combinatorially proved by Sulanke (see link).
%C A352687 The polynomials have only real zeros and form a Sturm sequence. This follows from the recurrence along the lines given in the Chen et al. paper.
%C A352687 Some interesting sequences turn out to be the evaluation of the polynomial sequence at a fixed point (see the cross-references), for example the reversion of the Jacobsthal numbers A001045 essentially is -(-2)^n*P(n, -1/2).
%C A352687 The polynomials can also be represented as the difference between generalized Narayana polynomials, see the formula section.
%H A352687 Xi Chen, Arthur Li Bo Yang, James Jing Yu Zhao, <a href="https://doi.org/10.1007/s11424-021-0216-z">Recurrences for Callan's Generalization of Narayana Polynomials</a>, J. Syst. Sci. Complex (2021).
%H A352687 Peter Luschny, <a href="/A352687/a352687.pdf">Illustration of the polynomials</a>.
%H A352687 Robert A. Sulanke, <a href="https://citeseerx.ist.psu.edu/pdf/43f55a444127be30366676c977e9d7e412d25614">The Narayana distribution</a>, J. Statist. Plann. Inference, 2002, 101: 311-326, formula 2.
%F A352687 Explicit formula (additive form):
%F A352687 T(n, n) = 1, T(n > 0, 0) = 0 and otherwise T(n, k) = binomial(n, k)*binomial(n - 1, k - 1)/(n - k + 1) - 2*binomial(n - 1, k)*binomial(n - 1, k - 2)/(n - 1).
%F A352687 Multiplicative formula with the same boundary conditions:
%F A352687 T(n, k) = binomial(n, k)^2*(k*(2*k^2 + (n + 1)*(n - 2*k)))/(n^2*(n-1)*(n- k + 1)).
%F A352687 Bivariate generating function:
%F A352687 T(n, k) = [x^n] [y^k](1 - x + (1+y)*(1-x*(y-1) - sqrt((x*y+x-1)^2 - 4*x^2*y))/2).
%F A352687 Recursion based on polynomials:
%F A352687 T(n, k) = [x^k] (((2*n - 3)*(x + 1)*P(n - 1, x) - (n - 3)*(x - 1)^2*P(n - 2, x)) / n) with P(0, x) = 1, P(1, x) = x, and P(2, x) = x + x^2.
%F A352687 Recursion based on rows (see the second Python program):
%F A352687 T(n, k) = (((B(k) + B(k-1)) * (2*n - 3) - (A(k) - 2*A(k-1) + A(k-2))*(n-3))/n), where A(k) = T(n-2, k) and B(k) = T(n-1, k), for n >= 3.
%F A352687 Hypergeometric representation:
%F A352687 T(n, k) = [x^k] x*(x + 1)*hypergeom([1 - n, 2 - n], [2], x) for n >= 2.
%F A352687 Row sums:
%F A352687 Sum_{k=0..n} T(n, k) = (2/n)*binomial(2*(n - 1), n - 1) = A068875(n-1) for n >= 2.
%F A352687 A generalization of the Narayana polynomials is given by
%F A352687 N{n, k}(x) = Sum_{j=0..n-2*k}(((k + 1)/(n - k)) * binomial(n - k, j - 1) * binomial(n - k, j + k) * x^(j + k)).
%F A352687 N{n, 0}(x) are the classical Narayana polynomials A001263 and N{n, 1}(x) is a shifted version of A145596 based in (3, 2). Our polynomials are the difference P(n, x) = N{n, 0}(x) - N{n, 1}(x) for n >= 1.
%F A352687 Let RS(T, n) denote the row sum of the n-th row of T, then RS(T, n) - RS(A090181, n) = -4*binomial(2*n - 3, n - 3)/(n + 1) = A115143(n + 1) for n >= 3.
%e A352687 Triangle starts:
%e A352687 [0] 1;
%e A352687 [1] 0, 1;
%e A352687 [2] 0, 1,  1;
%e A352687 [3] 0, 1,  2,   1;
%e A352687 [4] 0, 1,  4,   4,   1;
%e A352687 [5] 0, 1,  7,  12,   7,   1;
%e A352687 [6] 0, 1, 11,  30,  30,  11,   1;
%e A352687 [7] 0, 1, 16,  65, 100,  65,  16,   1;
%e A352687 [8] 0, 1, 22, 126, 280, 280, 126,  22,  1;
%e A352687 [9] 0, 1, 29, 224, 686, 980, 686, 224, 29, 1;
%p A352687 T := (n, k) -> if n = k then 1 elif k = 0 then 0 else
%p A352687 binomial(n, k)^2*(k*(2*k^2 + (n + 1)*(n - 2*k))) / (n^2*(n - 1)*(n - k + 1)) fi:
%p A352687 seq(seq(T(n, k), k = 0..n), n = 0..10);
%p A352687 # Alternative:
%p A352687 gf := 1 - x + (1 + y)*(1 - x*(y - 1) - sqrt((x*y + x - 1)^2 - 4*x^2*y))/2:
%p A352687 serx := expand(series(gf, x, 16)): coeffy := n -> coeff(serx, x, n):
%p A352687 seq(seq(coeff(coeffy(n), y, k), k = 0..n), n = 0..10);
%p A352687 # Using polynomial recurrence:
%p A352687 P := proc(n, x) option remember; if n < 3 then [1, x, x + x^2] [n + 1] else
%p A352687 ((2*n - 3)*(x + 1)*P(n - 1, x) - (n - 3)*(x - 1)^2*P(n - 2, x)) / n fi end:
%p A352687 Trow := n -> seq(coeff(P(n, x), x, k), k = 0..n): seq(Trow(n), n = 0..10);
%p A352687 # Represented by generalized Narayana polynomials:
%p A352687 N := (n, k, x) -> add(((k+1)/(n-k))*binomial(n-k,j-1)*binomial(n-k,j+k)*x^(j+k), j=0..n-2*k): seq(print(ifelse(n=0, 1, expand(N(n,0,x) - N(n,1,x)))), n=0..7);
%t A352687 H[0, _] := 1; H[1, x_] := x;
%t A352687 H[n_, x_] := x*(x + 1)*Hypergeometric2F1[1 - n, 2 - n, 2, x];
%t A352687 Hrow[n_] := CoefficientList[H[n, x], x]; Table[Hrow[n], {n, 0, 9}] // TableForm
%o A352687 (Python)
%o A352687 from math import comb as binomial
%o A352687 def T(n, k):
%o A352687     if k == n: return 1
%o A352687     if k == 0: return 0
%o A352687     return ((binomial(n, k)**2 * (k * (2 * k**2 + (n + 1) * (n - 2 * k))))
%o A352687            // (n**2 * (n - 1) * (n - k + 1)))
%o A352687 def Trow(n): return [T(n, k) for k in range(n + 1)]
%o A352687 for n in range(10): print(Trow(n))
%o A352687 (Python) # The recursion with cache is (much) faster:
%o A352687 from functools import cache
%o A352687 @cache
%o A352687 def T_row(n):
%o A352687     if n < 3: return ([1], [0, 1], [0, 1, 1])[n]
%o A352687     A = T_row(n - 2) + [0, 0]
%o A352687     B = T_row(n - 1) + [1]
%o A352687     for k in range(n - 1, 1, -1):
%o A352687         B[k] = (((B[k] + B[k - 1]) * (2 * n - 3)
%o A352687                - (A[k] - 2 * A[k - 1] + A[k - 2]) * (n - 3)) // n)
%o A352687     return B
%o A352687 for n in range(10): print(T_row(n))
%Y A352687 Cf. A090181 and A001263 (Narayana), A353279 (case 3), A000108 (Catalan), A145596, A172392 (central terms), A000124 (subdiagonal, column 2), A115143.
%Y A352687 Essentially twice the Catalan numbers: A284016 (also A068875, A002420).
%Y A352687 Values of the polynomial sequence: A068875 (row sums): P(1), A154955: P(-1), A238113: P(2)/2, A125695 (also A152681): P(-2), A054872: P(3)/2, P(3)/6 probable A234939, A336729: P(-3)/6, A082298: P(4)/5, A238113: 2^n*P(1/2), A154825 and A091593: 2^n*P(-1/2).
%K A352687 nonn,tabl
%O A352687 0,9
%A A352687 _Peter Luschny_, Apr 26 2022