A090181 -id:A090181 - cp's OEIS frontend

A152681 [x^(n+1)]Reversion[x(1-x)/(1-3x)].

1, -2, 2, 2, -10, 6, 42, -102, -82, 782, -814, -3854, 12454, 5014, -98694, 142218, 472158, -1932258, -19038, 14816994, -27370410, -64159962, 334154442, -121279878, -2418497010, 5523511086, 8914677362, -61259567662, 44249714438

Offset: 0

Paul Barry, Dec 10 2008

Hankel transform is (-2)^C(n+1,2).

			G.f. = 1 - 2*x + 2*x^2 + 2*x^3 - 10*x^4 + 6*x^5 + 42*x^6 + ... - _Michael Somos_, Sep 18 2018

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A125695.

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!((1 +3*x -Sqrt(1+2*x+9*x^2))/(2*x))); // G. C. Greubel, Sep 14 2018

A152681_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := -2*a[w-1]+add(a[j]*a[w-j-1],j=1..w-1) od;convert(a,list)end: A152681_list(28); # Peter Luschny, May 19 2011

CoefficientList[Series[(1+3*x-Sqrt[1+2*x+9*x^2])/(2*x), {x,0,50}], x] (* G. C. Greubel, Sep 14 2018 *)

x='x+O('x^30); Vec((1 +3*x -sqrt(1+2*x+9*x^2))/(2*x)) \\ G. C. Greubel, Sep 14 2018

A152681 = lambda n : (-3)^n*hypergeometric([-n, n+1], [2], 1/3)
[round(A152681(n).n(100)) for n in (0..20)] # Peter Luschny, Sep 17 2014

G.f.: (1 + 3*x - sqrt(1 + 2*x + 9*x^2))/(2*x).
a(n) = Sum_{k=0..n} C(n+k,2k)*A000108(k)*(-3)^(n-k).
a(n) = 0^n - 2*Sum_{k=0..floor((n-1)/2)} C(n-1,2k)*A000108(k)(-1)^(n-k-1)*2^k.
a(n) = Sum_{k=0..n} A090181(n,k)*(-2)^k. - Philippe Deléham, Feb 02 2009
D-finite with recurrence (n+1)*a(n) + (2*n-1)*a(n-1) + 9*(n-2)*a(n-2) = 0. - R. J. Mathar, Oct 25 2012
a(n) = (-3)^n*hypergeometric([-n, n+1], [2], 1/3). - Peter Luschny, Sep 17 2014

A156017 Schroeder paths with two rise colors and two level colors.

Original entry on oeis.org

1, 4, 24, 176, 1440, 12608, 115584, 1095424, 10646016, 105522176, 1062623232, 10840977408, 111811534848, 1163909087232, 12212421230592, 129027376349184, 1371482141884416, 14656212306231296, 157369985643577344, 1696975718802522112, 18369603773021552640

Offset: 0

Paul Barry, Feb 01 2009

Hankel transform is 8^C(n+1,2). - Philippe Deléham, Feb 04 2009

a(n-1) is also the number of ways a list of n items can be grouped into nested sublists (e.g., [a b c] to [a b c], [[a] b c], [[a, b] c], [[a [b]] c], and so on). - Ryan Tosh, Nov 10 2021

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
Z. Chen and H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 [math.CO], 2016. See eq (1.13) a=4, b=2.
Loïc Foissy, Generalized associative algebras, hal-03187479 [math.RA], 2021.

Cf. A059435, A090181.

Partial sums of A336283.

A156017_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 2*(a[w-1]+add(a[j]*a[w-j-1], j=0..w-1)) od;
convert(a, list) end: A156017_list(20); # Peter Luschny, Feb 29 2016

CoefficientList[Series[(1-2*x-Sqrt[1-12*x+4*x^2])/(4*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)
a[n_] := 2^n Hypergeometric2F1[- n, n + 1, 2, -1];
Table[a[n], {n, 0, 20}] (* Peter Luschny, Nov 25 2020 *)

G.f.: (1-2x-sqrt(1-12x+4x^2))/(4x);
G.f.: 1/(1-2x-2x/(1-2x-2x/(1-2x-2x/(1-... (continued fraction);
a(n) = 2^n*Sum_{k=0..n} C(n+k,2k)*A000108(k) = 2^n*A006318(n).
D-finite with recurrence (n+1)*a(n) +6*(1-2*n)*a(n-1) +4*(n-2)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011
a(n) = Sum_{k=0..n} A090181(n,k)*2^(n+k). - Philippe Deléham, Nov 27 2011
a(n) ~ sqrt(4+3*sqrt(2))*(6+4*sqrt(2))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012
G.f.: 1/Q(0) where Q(k) = 1 + k*(1-2*x) - 2*x - 2*x*(k+1)*(k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013
a(n) = 2*A059435(n) for n >= 1. - Sergey Kirgizov, Feb 13 2017
a(n) = 2^n*hypergeom([-n, n + 1], [2], -1). - Peter Luschny, Nov 25 2020

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A247500 Triangle read by rows: T(n, k) = n!*binomial(n + 1, k)/(k + 1)!, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 6, 12, 6, 1, 24, 60, 40, 10, 1, 120, 360, 300, 100, 15, 1, 720, 2520, 2520, 1050, 210, 21, 1, 5040, 20160, 23520, 11760, 2940, 392, 28, 1, 40320, 181440, 241920, 141120, 42336, 7056, 672, 36, 1, 362880, 1814400, 2721600, 1814400, 635040, 127008, 15120, 1080, 45, 1

Offset: 0

Peter Luschny, Oct 17 2014

An alternative definition would have been: (n-k)!*N(n,k) where N(n,k) are the little Narayana numbers A090181(n,k). This adds a first column (1,0,0,...) to the triangle and amounts to (Gamma(n)*Gamma(n+1))/(Gamma(k)*Gamma(k+1)*Gamma(n-k+2)). - Peter Luschny, Jun 18 2015
From Peter Bala, Sep 03 2023: (Start)
Let E(y) = Sum_{n >= 0} y^n/(n+1)!. Then this triangle is the generalized Riordan array (E(y), y) with respect to the sequence n!*(n+1)! as defined in Wang and Wang.
Let B(y) = Sum_{n >= 0} y^n/(n!*(n+1)!) = 1/sqrt(y)*BesselI(1,2*sqrt(y)). A generating function for the triangle is E(y)*B(x*y) = 1 + (1 + x)*y/(1!*2!) + (2 + 3*x + x^2)*y^2/(2!*3!) + (6 + 12*x + 6*x^2 + x^3)*y^3/(3!*4!) + .... Cf. A105278 with a generating function exp(y)*B(x*y).
The n-th power of this array has a generating function E(y)^n*B(x*y). In particular, the matrix inverse has a generating function B(x*y)/E(y). (End)

			Triangle begins:
                      1;
                   1,    1;
                2,    3,    1;
             6,   12,    6,    1;
         24,   60,   40,   10,    1;
     120,  360,  300,  100,   15,    1;
  720, 2520, 2520, 1050,  210,   21,    1;

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
W. Wang and T. Wang, Generalized Riordan arrays, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.

Cf. A247499 (row sums), A008297.
Cf. A000142, A000217, A001710.
Cf. A204515 (central terms), A105278, A004736.
Cf. A090181, A001263.

a247500 n k = a247500_tabl !! n !! k
a247500_row n = a247500_tabl !! n
a247500_tabl = zipWith (zipWith div) a105278_tabl a004736_tabl
-- Reinhard Zumkeller, Oct 19 2014

/* triangle */ [[Factorial(n)/Factorial(k) * Binomial(n+2, k+1) /(n+2): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 18 2014

T := (n,k) -> ((k+1)*(n+1)*GAMMA(n+1)^2)/(GAMMA(k+2)^2*GAMMA(n-k+2));
A247500 := (n, k) -> (n!/(k+1)!)*binomial(n + 1, k):

Table[((k + 1) (n + 1) Gamma[n + 1]^2)/(Gamma[k + 2]^2*
Gamma[n - k + 2]), {n, 0, 9}, {k, 0, n}] // Flatten (* Michael De Vlieger, Jun 19 2015 *)

T(n, k) = ((k+1)*(n+1)*Gamma(n+1)^2)/(Gamma(k+2)^2 *Gamma(n-k+2)). (original name)
T(n, k) = (n!/k!)*C(n+2, k+1)/(n+2).
T(n, 0) = A000142(n).
T(n, n-1) = A000217(n).
T(n+1, 1) = A001710(n+2).
Sum_{k=0..n} T(n, k) = A247499(n).
L(n+1, k+1) = T(n-1, k)*P(n) for n>=1 and 0<=k<=n; here L(n,k) denote the unsigned Lah numbers and P(n) the pronic numbers. - Peter Luschny, Oct 18 2014
T(n,k) = A105278(n+1,k+1) / (n+1-k), k=0..n. - Reinhard Zumkeller, Oct 19 2014
From Peter Bala, May 24 2023: (Start)
Triangle equals A164652 * A008277 (assuming the same offset for the three triangles).
This is equivalent to the Stirling number identity Sum_{i = 0..n} (n+1)!/(i+1)!* binomial(n,i)*Stirling1(i+1,k) = (-1)^(n+k+1)*Stirling1(n+1,k) for n, k >= 0. (End)

Name updated by Peter Luschny, Jan 09 2022

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

Original entry on oeis.org

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, 65, 100, 65, 16, 1, 0, 1, 22, 126, 280, 280, 126, 22, 1, 0, 1, 29, 224, 686, 980, 686, 224, 29, 1, 0, 1, 37, 372, 1512, 2940, 2940, 1512, 372, 37, 1

Offset: 0

Peter Luschny, Apr 26 2022

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.
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).
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.
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).
The polynomials can also be represented as the difference between generalized Narayana polynomials, see the formula section.

			Triangle starts:
[0] 1;
[1] 0, 1;
[2] 0, 1,  1;
[3] 0, 1,  2,   1;
[4] 0, 1,  4,   4,   1;
[5] 0, 1,  7,  12,   7,   1;
[6] 0, 1, 11,  30,  30,  11,   1;
[7] 0, 1, 16,  65, 100,  65,  16,   1;
[8] 0, 1, 22, 126, 280, 280, 126,  22,  1;
[9] 0, 1, 29, 224, 686, 980, 686, 224, 29, 1;

Xi Chen, Arthur Li Bo Yang, James Jing Yu Zhao, Recurrences for Callan's Generalization of Narayana Polynomials, J. Syst. Sci. Complex (2021).
Peter Luschny, Illustration of the polynomials.
Robert A. Sulanke, The Narayana distribution, J. Statist. Plann. Inference, 2002, 101: 311-326, formula 2.

Cf. A090181 and A001263 (Narayana), A353279 (case 3), A000108 (Catalan), A145596, A172392 (central terms), A000124 (subdiagonal, column 2), A115143.
Essentially twice the Catalan numbers: A284016 (also A068875, A002420).
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).

T := (n, k) -> if n = k then 1 elif k = 0 then 0 else
binomial(n, k)^2*(k*(2*k^2 + (n + 1)*(n - 2*k))) / (n^2*(n - 1)*(n - k + 1)) fi:
seq(seq(T(n, k), k = 0..n), n = 0..10);
# Alternative:
gf := 1 - x + (1 + y)*(1 - x*(y - 1) - sqrt((x*y + x - 1)^2 - 4*x^2*y))/2:
serx := expand(series(gf, x, 16)): coeffy := n -> coeff(serx, x, n):
seq(seq(coeff(coeffy(n), y, k), k = 0..n), n = 0..10);
# Using polynomial recurrence:
P := proc(n, x) option remember; if n < 3 then [1, x, x + x^2] [n + 1] else
((2*n - 3)*(x + 1)*P(n - 1, x) - (n - 3)*(x - 1)^2*P(n - 2, x)) / n fi end:
Trow := n -> seq(coeff(P(n, x), x, k), k = 0..n): seq(Trow(n), n = 0..10);
# Represented by generalized Narayana polynomials:
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);

H[0, ] := 1; H[1, x] := x;
H[n_, x_] := x*(x + 1)*Hypergeometric2F1[1 - n, 2 - n, 2, x];
Hrow[n_] := CoefficientList[H[n, x], x]; Table[Hrow[n], {n, 0, 9}] // TableForm

from math import comb as binomial
def T(n, k):
    if k == n: return 1
    if k == 0: return 0
    return ((binomial(n, k)**2 * (k * (2 * k**2 + (n + 1) * (n - 2 * k))))
           // (n**2 * (n - 1) * (n - k + 1)))
def Trow(n): return [T(n, k) for k in range(n + 1)]
for n in range(10): print(Trow(n))

# The recursion with cache is (much) faster:
from functools import cache
@cache
def T_row(n):
    if n < 3: return ([1], [0, 1], [0, 1, 1])[n]
    A = T_row(n - 2) + [0, 0]
    B = T_row(n - 1) + [1]
    for k in range(n - 1, 1, -1):
        B[k] = (((B[k] + B[k - 1]) * (2 * n - 3)
               - (A[k] - 2 * A[k - 1] + A[k - 2]) * (n - 3)) // n)
    return B
for n in range(10): print(T_row(n))

Explicit formula (additive form):
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).
Multiplicative formula with the same boundary conditions:
T(n, k) = binomial(n, k)^2*(k*(2*k^2 + (n + 1)*(n - 2*k)))/(n^2*(n-1)*(n- k + 1)).
Bivariate generating function:
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).
Recursion based on polynomials:
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.
Recursion based on rows (see the second Python program):
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.
Hypergeometric representation:
T(n, k) = [x^k] x*(x + 1)*hypergeom([1 - n, 2 - n], [2], x) for n >= 2.
Row sums:
Sum_{k=0..n} T(n, k) = (2/n)*binomial(2*(n - 1), n - 1) = A068875(n-1) for n >= 2.
A generalization of the Narayana polynomials is given by
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)).
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.
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.

A189176 Row sums of the Riordan matrix (1+x/sqrt(1-4x),(1-sqrt(1-4x))/2) (A189175).

Original entry on oeis.org

1, 2, 5, 15, 49, 168, 594, 2145, 7865, 29172, 109174, 411502, 1560090, 5943200, 22732740, 87253605, 335897865, 1296447900, 5015206350, 19439895090, 75487384830, 293595204240, 1143532045500, 4459774977450, 17413705988874, 68067249620328, 266326619546204

Offset: 0

Emanuele Munarini, Apr 18 2011

			a(3) = 15 since the top row of M^3 = (6, 5, 3, 1, 0, 0, 0, ...)

Cf. A090181, A189175.

T[n_,k_] := If[n==k,1,Binomial[2n-k,n-k](n^2+n k-k^2-k)/((2n-k)(2n-k-1))]; Table[Sum[T[n,k], {k,0,n}], {n,0,22}]

T(n,k):=if n=k then 1 else binomial(2*n-k,n-k)*(n^2+n*k-k^2-k)/((2*n-k)*(2*n-k-1));
makelist(sum(T(n,k),k,0,n),n,0,22);

a(n) = Sum_{k=0..n} binomial(2*n-k,n-k)*(n^2+n*k-k^2-k)/((2*n-k)*(2*n-k-1)), for n>=2.
G.f.: (1-5*x+4*x^2-(1-5*x)*sqrt(1-4x))/(2*x*(1-4*x))
a(n) = Sum_{k=1..n} (3-k)*binomial(2*n-k-1,n-1), n>0, a(0)=1. - Vladimir Kruchinin, Oct 18 2011
From Gary W. Adamson, Nov 14 2011: (Start)
a(n) is the sum of top row terms in M^n, M = an infinite square production matrix as follows, with the Fibonacci sequence as the left border:
   1, 1, 0, 0, 0, 0, ...
   1, 1, 1, 0, 0, 0, ...
   2, 1, 1, 1, 0, 0, ...
   3, 1, 1, 1, 1, 0, ...
   5, 1, 1, 1, 1, 1, ...
which means the top row of M^n is the n-th row in A189175. (End)
Conjecture: (n+1)*a(n) + 3*(1-3*n)*a(n-1) + 10*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Nov 15 2011
a(n) = Sum_{k=0..n} (k+1) * A090181(n,k). - Alois P. Heinz, Apr 04 2024

A349740 Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 4, 5, 0, 1, 7, 13, 14, 0, 1, 11, 31, 41, 42, 0, 1, 16, 66, 116, 131, 132, 0, 1, 22, 127, 302, 407, 428, 429, 0, 1, 29, 225, 715, 1205, 1401, 1429, 1430, 0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862, 0, 1, 46, 586, 3106, 8398, 13690, 16210, 16750, 16795, 16796

Offset: 0

Ron L.J. van den Burg, Nov 28 2021

Given a partition P of the set {1,2,...,n}, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings.

			For n=4 the T(4,3)=13 partitions are {{1,2,3,4}}, {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,2},{3},{4}}, {{1,3},{2},{4}}, {{1,4},{2},{3}}, {{1},{2,3},{4}}, {{1},{2,4},{3}}, {{1},{2},{3,4}}.
The set of sets {{1,3},{2,4}} is missing because it is crossing. If you add the set of 4 sets, {{1},{2},{3},{4}}, you get T(4, 4) = 14 = A000108(4), the 4th Catalan number.
Triangle begins:
  1;
  0, 1;
  0, 1,  2;
  0, 1,  4,   5;
  0, 1,  7,  13,   14;
  0, 1, 11,  31,   41,   42;
  0, 1, 16,  66,  116,  131,  132;
  0, 1, 22, 127,  302,  407,  428,  429;
  0, 1, 29, 225,  715, 1205, 1401, 1429, 1430;
  0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
David Callan, Sets, Lists and Noncrossing Partitions, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3; also on arXiv, arXiv:0711.4841 [math.CO], 2007-2008.

Columns k=0-4 give (for n>=k): A000007, A000012, A000124(n-1), A116701, A116844.
Partial sums of A090181 per row.
Main diagonal is A000108.
Row sums give A088218.
T(2*n,n) gives A065097.
T(n,n-1) gives A001453 for n >= 2.
Cf. A106396, A137940.

b:= proc(x, y, t) option remember; expand(`if`(y<0
      or y>x, 0, `if`(x=0, 1, add(b(x-1, y+j, j)*
     `if`(t=1 and j<1, z, 1), j=[-1, 1]))))
    end:
T:= proc(n, k) option remember; `if`(k<0, 0,
      T(n, k-1)+coeff(b(2*n, 0$2), z, k))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Nov 28 2021

T[n_, k_] := If[n == 0, 1, Sum[j Binomial[n, j]^2 / (n - j + 1), {j, 0, k}] / n];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Peter Luschny, Nov 29 2021 *)

T(n,k) = Sum_{j=0..k} A090181(n,j), the partial sum of the Narayana numbers.
T(n,n) = A000108(n), the n-th Catalan number.
G.f.: (1 + x - x*y - sqrt((1-x*(1+y))^2 - 4*y*x^2))/(2*x*(1-y)).
T(n,k) = (1/n)*Sum_{j=0..k} j*binomial(n,j)^2 / (n-j+1) for n >= 1. - Peter Luschny, Nov 29 2021

A353279 Triangle read by rows, a Narayana related triangle whose rows are refinements of four times the Catalan numbers (for n >= 3).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 5, 8, 5, 1, 0, 1, 8, 19, 19, 8, 1, 0, 1, 12, 41, 60, 41, 12, 1, 0, 1, 17, 81, 165, 165, 81, 17, 1, 0, 1, 23, 148, 406, 560, 406, 148, 23, 1, 0, 1, 30, 253, 910, 1666, 1666, 910, 253, 30, 1

Offset: 0

Peter Luschny, Apr 29 2022

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).

			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

Peter Luschny, Illustration of the polynomials.

Cf. A090181 (and A001263), A352687, A097805, A000108.

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:

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 *)

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
for n in range(10): print(Trow(n, 3)) # k=1 -> A090181, k=2 -> A352687

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).

A379103 Expansion of (1-3x-sqrt(9x^2-14*x+1))/4.

Original entry on oeis.org

0, 1, 5, 35, 295, 2765, 27705, 290535, 3148995, 34995065, 396602605, 4566227435, 53259218495, 627982592965, 7473163652705, 89640387354735, 1082664905352795, 13155505626756465, 160709002086562005, 1972595405313408435, 24315686632846439895, 300886761671728853565, 3736205372071338170505, 46540791299676591116535

Offset: 0

Nathaniel Johnston, Dec 15 2024

Problem A6 on the 2024 William Lowell Putnam Mathematical Competition was to compute the Hankel transform of this sequence, which is A110147.

Given constants X and Y, let A(x) = (1 - x*(X - Y) - sqrt(1 - 2*x*(X + Y) + x^2*(X - Y)^2))/(2*Y) = x*(1) + x^2*(X) + x^3*X*(X + Y) + x^4*X*(X^2 + 3*X*Y + Y^2) + ... where the coefficients of A(x) is the Narayana triangle A090181. A(x) satisfies 0 = x - A(x)*(1 - x*(X-Y)) + A(x)^2*Y. The Hankel transform of the coefficients 1, X, X*(X + Y), ... is the sequence 1, (X*Y), (X*Y)^2, ... while the Hankel transform of X, X*(X + Y), X*(X^2 + 3*X*Y + Y^2), ... is the sequence X, X^3*Y, X^6*Y^3, X^10*Y^6, .... In the case of this sequence, X = 5 and Y = 2. - Michael Somos, Apr 26 2025

			G.f. = x + 5*x^2 + 35*x^3 + 295*x^4 + 2765*x^5 + 27705*x^6 + ... - _Michael Somos_, Apr 26 2025

Nathaniel Johnston, Determinant involving (1 - 3x - sqrt(1 - 14x + 9x^2))/4, YouTube video, 2024.
Nathaniel Johnston, Putnam 2024 A6 solution, 2024.

Cf. A025231, A047891, A082298, A110147.

a = 3;b = 2;c(1) = 1;last_val = 16;for j = 2:last_val
c(j) = a*c(j-1) + b*sum(c(1:j-1).*fliplr(c(1:j-1)));
end

a[ n_] := SeriesCoefficient[ (1 - 3*x - Sqrt[1 - 14*x + 9*x^2])/4, {x, 0, n}]; (* Michael Somos, Apr 26 2025 *)
a[ n_] := With[{X = 5, Y = 2}, SeriesCoefficient[ Nest[x/(1 - (X-Y)*x - Y*#)&, O[x], n], {x, 0, n}]]; (* Michael Somos, Apr 28 2025 *)
a[ n_] := With[{X = 5, Y = 2}, SeriesCoefficient[ Nest[x/(1 - X*x/(1 - Y*#))&, O[x], Ceiling[n/2]], {x, 0, n}]]; (* Michael Somos, Apr 28 2025 *)

my(x='x+O('x^33)); concat([0],Vec((1-3*x-sqrt(9*x^2-14*x+1))/4)) \\ Joerg Arndt, Dec 15 2024

a(n) = my(A = O(x)); for(k=1, n, A = x + 3*x*A + 2*A^2); polcoeff(A, n); /* Michael Somos, Apr 26 2025 */

a(n) = my(A = O(x), X = 5, Y = 2); for(k = 1, n, A = x/(1 - (X-Y)*x - Y*A)); polcoeff(A, n); /* Michael Somos, Apr 28 2025 */

a(n) = my(A = O(x), X = 5, Y = 2); for(k = 1, (n+1)\2, A = x/(1 - X*x/(1 - Y*A))); polcoeff(A, n); /* Michael Somos, Apr 28 2025 */

a(0) = 0, a(1) = 1, a(n) = 3*a(n-1) + 2*Sum_{k=0..n} a(k)*a(n-k) for n >= 2.
G.f.: (1-3*x-sqrt(9*x^2-14*x+1))/4.
G.f.: x/(1-5*x/(1-2*x/(1-5*x/(1-2*x/(1-5*x/(...)))))). - Thomas Scheuerle, Feb 28 2025
a(n) = (1/4)*(-1)^(n+1) * Sum_{k=0..n} binomial(1/2,k) * binomial(1/2,n-k) * (7+2*sqrt(10))^k * (7-2*sqrt(10))^(n-k) for n >= 2. - Ehren Metcalfe, Feb 26 2025
a(n) ~ 5^(1/4) * (7 + 2*sqrt(10))^(n - 1/2) / (2^(7/4) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 27 2025
The g.f. A(x) satisfies 0 = x - (1 - 3*x)*A(x) + 2*A(x)^2 and A(x) = x + 3*x*A(x) + 2*A(x)^2. - Michael Somos, Apr 26 2025

A101919 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k up steps starting at even heights.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 12, 8, 1, 1, 33, 42, 13, 1, 1, 88, 183, 102, 19, 1, 1, 232, 717, 624, 205, 26, 1, 1, 609, 2622, 3275, 1650, 366, 34, 1, 1, 1596, 9134, 15473, 11020, 3716, 602, 43, 1, 1, 4180, 30691, 67684, 64553, 30520, 7483, 932, 53, 1, 1, 10945, 100284, 279106

Offset: 0

Emeric Deutsch, Dec 20 2004

A Schroeder path of length 2n is a lattice path starting from (0,0), ending at (2n,0), consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis (Schroeder paths are counted by the large Schroeder numbers, A006318). Also number of Schroeder paths of length 2n and having k humps. A hump is an up step U followed by 0 or more level steps H followed by a down step D. The T(3,2)=8 Schroeder paths of length 6 and having 2 humps are: H(UD)(UD), (UD)H(UD), (UD)(UD)H, (UD)(UHD), (UD)(UUDD), (UHD)(UD), (UUDD)(UD) and U(UD)(UD)D, the humps being shown between parentheses. Row sums are the large Schroeder numbers (A006318). Column 1 yields the odd-indexed Fibonacci numbers minus 1 (A027941). T(n,n-1)=A034856(n)=binomial(n + 1, 2) + n - 1.

Product A085478*A090181 (Morgan-Voyce times Narayana). [From Paul Barry, Jan 29 2009]

			T(3,2)=8 because we have HU'DU'D, U'DHU'D, U'DU'DH, U'DU'HD, U'DU'UDD, U'HDU'D, U'UDDU'D and U'UU'DDD, the up steps starting at an even height being shown with a prime sign.
Triangle begins:
1;
1,1;
1,4,1;
1,12,8,1;
1,33,42,13,1;

Cf. A006318, A027941, A034856, A101920.

G:=1/2/(-z+z^2)*(-1+z+t*z-z^2+sqrt(1-6*z-2*t*z+11*z^2+2*t*z^2-6*z^3+t^2*z^2-2*t*z^3+z^4)): Gser:=simplify(series(G,z=0,13)): P[0]:=1: for n from 1 to 11 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 11 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields the sequence in triangular form

G.f.=G=G(t, z) satisfies z(1-z)G^2-(1-z-tz+z^2)G+1-z=0.

G.f.: 1/(1-x-xy/(1-x-x/(1-x-xy/(1-x-xy/(1-x-x/(1-x-xy/(1-.... (continued fraction). [From Paul Barry, Jan 29 2009]

A358723 Number of n-node rooted trees of edge-height equal to their number of leaves.

Original entry on oeis.org

0, 1, 0, 2, 1, 6, 7, 26, 43, 135, 276, 755, 1769, 4648, 11406, 29762, 75284, 195566, 503165, 1310705, 3402317, 8892807, 23231037, 60906456, 159786040, 420144405, 1105673058, 2914252306, 7688019511, 20304253421, 53667498236, 141976081288, 375858854594, 995728192169

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Edge-height (A109082) is the number of edges in the longest path from root to leaf.

			The a(1) = 0 through a(7) = 7 trees:
  .  (o)  .  ((oo))  ((o)(o))  (((ooo)))  (((o))(oo))
             (o(o))            ((o(oo)))  (((o)(oo)))
                               ((oo(o)))  ((o)((oo)))
                               (o((oo)))  ((o)(o(o)))
                               (o(o(o)))  ((o(o)(o)))
                               (oo((o)))  (o((o)(o)))
                                          (o(o)((o)))

Andrew Howroyd, Table of n, a(n) for n = 1..200

For internals instead of leaves: A011782, ranked by A209638.
For internals instead of edge-height: A185650 aerated, ranked by A358578.
For node-height: A358589 (square trees), ranked by A358577, ordered A358590.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
A358575 counts rooted trees by nodes and internals, ordered A090181.
Cf. A065097, A109082, A109129, A342507, A358552, A358587, A358591, A358728.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Count[#,{},{-2}]==Depth[#]-2&]],{n,1,10}]

\\ Needs R(n,f) defined in A358589.
seq(n) = {Vec(R(n, (h,p)->polcoef(p,h-1,y)), -n)} \\ Andrew Howroyd, Jan 01 2023

Terms a(19) and beyond from Andrew Howroyd, Jan 01 2023

cp's OEIS Frontend

A152681 [x^(n+1)]Reversion[x*(1-x)/(1-3*x)].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A156017 Schroeder paths with two rise colors and two level colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A247500 Triangle read by rows: T(n, k) = n!*binomial(n + 1, k)/(k + 1)!, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A189176 Row sums of the Riordan matrix (1+x/sqrt(1-4*x),(1-sqrt(1-4*x))/2) (A189175).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Maxima

Formula

A349740 Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A353279 Triangle read by rows, a Narayana related triangle whose rows are refinements of four times the Catalan numbers (for n >= 3).

A152681 [x^(n+1)]Reversion[x(1-x)/(1-3x)].

A189176 Row sums of the Riordan matrix (1+x/sqrt(1-4x),(1-sqrt(1-4x))/2) (A189175).

A379103 Expansion of (1-3x-sqrt(9x^2-14*x+1))/4.