A004148 -id:A004148 - cp's OEIS frontend

A023422 Generalized Catalan Numbers x^2A(x)^2 -(1-x+x^2+x^3+x^4+x^5)A(x) + 1 =0.

1, 1, 1, 1, 1, 1, 2, 4, 8, 16, 32, 64, 129, 261, 530, 1080, 2208, 4528, 9313, 19207, 39714, 82314, 170996, 355976, 742545, 1551817, 3248823, 6812947, 14309557, 30099645, 63402315

Offset: 0

Olivier Gérard

Seiichi Manyama, Table of n, a(n) for n = 0..2926
A. Goupil, M.-E. Pellerin and J. de Wouters d'oplinter, Snake Polyominoes, arXiv preprint arXiv:1307.8432 [math.CO], 2013-2014. (Gives a g.f.)

Cf. A000108, A001006, A004148, A004149, A023421, A023423.

Fifth row of A064645.

a[0]=1; a[n_]:= a[n]=a[n-1] + Sum[a[k]*a[n-2-k], {k,4,n-2}]; Table[a[n], {n,0,30}] (* modified by G. C. Greubel, Jan 01 2018 *)
B[q_] = (q^2 + q^3 + q^4 + q^5 - Sqrt[((q(q^5 - 1))/(q - 1) - 1)^2 - 4q^6] - q + 1)/(2q^2); CoefficientList[B[q] + O[q]^31, q] (* Jean-François Alcover, Jan 29 2019 *)

{a(n) = if(n==0,1, a(n-1) + sum(k=4,n-2, a(k)*a(n-k-2)))};
for(n=0,30, print1(a(n), ", ")) \\ G. C. Greubel, Jan 01 2018

G.f. A(x) satisfies: A(x) = (1 + x^2 * A(x)^2) / (1 - x + x^2 + x^3 + x^4 + x^5). - Ilya Gutkovskiy, Jul 20 2021

D-finite with recurrence (n+2)*a(n) +(-2*n-1)*a(n-1) +(-n+1)*a(n-2) +(n-4)*a(n-4) +(2*n-11)*a(n-5) +(n-7)*a(n-6) +2*(2*n-17)*a(n-7) +3*(n-10)*a(n-8) +(2*n-23)*a(n-9) +(n-13)*a(n-10)=0. - R. J. Mathar, Feb 03 2025

A023423 Generalized Catalan Numbers x^2A(x)^2 -(1-x+x^2+x^3+x^4+x^5+x^6)A(x) + 1 =0.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16, 32, 64, 128, 257, 517, 1042, 2104, 4256, 8624, 17504, 35585, 72455, 147746, 301706, 616948, 1263240, 2589840, 5316033, 10924681, 22475831, 46290195

Offset: 0

Olivier Gérard

Seiichi Manyama, Table of n, a(n) for n = 0..3028

Cf. A000108, A001006, A004148, A004149, A023421, A023422.

Sixth row of A064645.

A023423 := proc(n)
    option remember;
    if n <= 6 then
        1;
    else
        procname(n-1)+add(procname(k)*procname(n-2-k),k=5..n-2) ;
    end if;
end proc: # R. J. Mathar, Oct 10 2014

a[0]=1; a[n_]:= a[n]=a[n-1] + Sum[a[k]*a[n-2-k], {k,5,n-2}]; Table[a[n], {n,0,30}] (* modified by G. C. Greubel, Jan 01 2018 *)

{a(n) = if(n==0,1, a(n-1) + sum(k=5,n-2, a(k)*a(n-k-2)))};
for(n=0,30, print1(a(n), ", ")) \\ G. C. Greubel, Jan 01 2018

G.f. A(x) satisfies: A(x) = (1 + x^2 * A(x)^2) / (1 - x + x^2 + x^3 + x^4 + x^5 + x^6). - Ilya Gutkovskiy, Jul 20 2021

A097724 Triangle read by rows: T(n,k) is the number of left factors of Motzkin paths without peaks, having length n and endpoint height k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 4, 6, 6, 4, 1, 8, 13, 13, 10, 5, 1, 17, 28, 30, 24, 15, 6, 1, 37, 62, 69, 59, 40, 21, 7, 1, 82, 140, 160, 144, 105, 62, 28, 8, 1, 185, 320, 375, 350, 271, 174, 91, 36, 9, 1, 423, 740, 885, 852, 690, 474, 273, 128, 45, 10, 1, 978, 1728, 2102, 2077

Offset: 0

Emeric Deutsch, Sep 11 2004

Column 0 is A004148 (RNA secondary structure numbers).
This triangle appears identical to A191579 (apart from offsets). - Philippe Deléham, Jan 26 2014
Conjecture: the row reverse triangle is the triangle of connection constants for expressing the polynomial u(n,x+1) as a linear combination of the polynomials u(k,x), 0 <= k <= n, where u(n,x) = U(n,x/2) with U(n,x) the n-th Chebyshev polynomial of the second kind. An example is given below.  Cf. A205810. - Peter Bala, Jun 26 2025

			Triangle starts:
  1;
  1, 1;
  1, 2, 1;
  2, 3, 3, 1;
  4, 6, 6, 4, 1;
Row n has n+1 terms.
T(3,2)=3 because we have HUU, UHU and UUH, where U=(1,1) and H=(1,0).
Row 7: let u(n,x) = U(n,x/2). Then u(7,x+1) = u(7,x) + 7*u(6,x) + 21*u(5,x) + 40*u(4,x) + 59*u(3,x) + 69*u(2,x) + 62*u(1,x) + 37. - _Peter Bala_, Jun 26 2025

Alois P. Heinz, Rows n = 0..140, flattened
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Naiomi Cameron and Everett Sullivan, Peakless Motzkin paths with marked level steps at fixed height, Discrete Mathematics 344.1 (2021): 112154.
Tian-Xiao He, A-sequences, Z-sequence, and B-sequences of Riordan matrices, Discrete Mathematics 343.3 (2020): 111718.
A. Nkwanta and A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.
A. Panayotopoulos and P. Vlamos, Cutting Degree of Meanders, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From _N. J. A. Sloane_, Dec 29 2012

Cf. A004148, A191579, A091964 (row sums), A205810.

T:=proc(n,k) if k=n then 1 else (k+1)*sum(binomial(j,n-k-j)*binomial(j+k,n+1-j)/j,j=ceil((n-k+1)/2)..n-k) fi end: seq(seq(T(n,k),k=0..n),n=0..12); T:=proc(n,k) if k=n then 1 else (k+1)*sum(binomial(j,n-k-j)*binomial(j+k,n+1-j)/j,j=ceil((n-k+1)/2)..n-k) fi end: TT:=(n,k)->T(n-1,k-1): matrix(10,10,TT); # gives the sequence as a matrix

T[n_, k_] := T[n, k] = If[k==n, 1, (k+1)*Sum[Binomial[j, n-k-j]*Binomial[j +k, n+1-j]/j, {j, Ceiling[(n-k+1)/2], n-k}]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

T(n,k) = (k+1)*Sum_{j=ceiling((n-k+1)/2)..n-k} (C(j,n-k-j)*C(j+k,n+1-j)/j) for 0 <= k < n; T(n,n)=1.
G.f.: G/(1-tzG), where G = (1 - z + z^2 - sqrt(1 - 2z - z^2 - 2z^3 + z^4))/(2z^2) is the g.f. for the sequence A004148.
T(n,k) = T(n-1,k-1) + Sum_{j>=0} T(n-1-j,k+j), T(0,0) = 1, T(n,k) = 0 if k < 0 or if k > n. - Philippe Deléham, Jan 26 2014
Sum_{j=0..n-1} cos(2*Pi*k/3 + Pi/6)*T(n,k) = cos(Pi*n/2)*sqrt(3)/2 - cos(2*Pi*n/3 + Pi/6). - Leonid Bedratyuk, Dec 06 2017

A247294 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having a total of k uhd and uHd strings.

Original entry on oeis.org

1, 1, 2, 4, 7, 1, 14, 3, 30, 7, 64, 18, 141, 43, 1, 316, 102, 5, 713, 249, 16, 1626, 608, 49, 3740, 1489, 143, 1, 8659, 3669, 400, 7, 20176, 9058, 1109, 29, 47274, 22407, 3046, 105, 111302, 55560, 8282, 357, 1, 263201, 138004, 22385, 1149, 9

Offset: 0

Emeric Deutsch, Sep 16 2014

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.
Row n contains 1 + floor(n/4) entries.
Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).
T(n,0) = A247295(n).
Sum(k*T(n,k), k=0..n) = A247296(n).

			T(6,1)=7 because we have uhdhh, huhdh, hhuhd, Huhd, uhdH, uHdh, and huHd.
Triangle starts:
1;
1;
2;
4;
7,1;
14,3;
30,7;

Alois P. Heinz, Rows n = 0..300, flattened
M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Cf. A004148, A247290, A247292, A247295, A247296.

eq := G = 1+z*G+z^2*G+z^3*(G-z-z^2+t*z+t*z^2)*G: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 25)): for n from 0 to 22 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 22 do seq(coeff(P[n], t, k), k = 0 .. floor((1/4)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y, t) option remember; `if`(y<0 or y>n, 0, `if`(n=0, 1,
      expand(b(n-1, y-1, 0)*`if`(t=2, x, 1)+b(n-1, y, `if`(t=1, 2, 0))
      +`if`(n>1, b(n-2, y, `if`(t=1, 2, 0))+b(n-2, y+1, 1), 0))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..20);  # Alois P. Heinz, Sep 16 2014

b[n_, y_, t_] := b[n, y, t] = If[y<0 || y>n, 0, If[n == 0, 1, Expand[b[n-1, y-1, 0]*If[t == 2, x, 1] + b[n-1, y, If[t == 1, 2, 0]] + If[n>1, b[n-2, y, If[t == 1, 2, 0]] + b[n-2, y+1, 1], 0]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

G.f. G = G(t,z) satisfies G = 1 + z*G + z^2*G + z^3*G*(G - z - z^2 + t*z + t*z^2).

A075125 Number of parallelogram polyominoes of site-perimeter n (also called staircase polyominoes, although that term is overused).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 2, 5, 10, 21, 46, 102, 230, 526, 1216, 2838, 6678, 15825, 37734, 90469, 217962, 527418, 1281250, 3123603, 7639784, 18740795, 46096732, 113666820, 280928470, 695796891, 1726744166, 4293121609, 10692145390, 26671959375, 66634602702

Offset: 1

Andrew Rechnitzer (a.rechnitzer(AT)ms.unimelb.edu.au), Sep 09 2002

nonn

a(n) is the number of Dyck n-paths with no UDU's and no DUD's (A004148) whose first ascent is of length 3. For example, a(5)=2 counts UUUDDUUDDD, UUUDDDUUDD. - David Callan, May 08 2007
From Emeric Deutsch, Nov 07 2009: (Start)
a(n) = Sum_{k>=0} k*A166299(n-2,k).
Number of UUDD's starting at level 0 in all Dyck paths of semilength n-2 that have no ascents and no descents of length 1. Example: a(6)=2 because in UUDDUUDD and UUUUDDDD we have 2 + 0 = 2 UUDD's starting at level 0. (The Dyck paths having no ascents and no descents of length 1 are enumerated by the secondary structure numbers A004148).
(End)

M. P. Delest, D. Gouyou-Beauchamps and B. Vauquelin, Enumeration of parallelogram polyominoes with given bond and site parameter, Graphs and Combinatorics, 3(1987),325-339. [From Emeric Deutsch, Nov 07 2009]

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.

Cf. A004148, A006958, A075126, A166299.

G := 4*z^4/(1+z-z^2+sqrt((1+z+z^2)*(1-3*z+z^2)))^2: Gser := series(G, z = 0, 32): seq(coeff(Gser, z, n), n = 1 .. 30); # Emeric Deutsch, Nov 07 2009

Rest[CoefficientList[Series[4 x^4/(1 + x - x^2 + Sqrt[(1 + x + x^2) (1 - 3 x + x^2)])^2, {x, 0, 40}], x]] (* Vaclav Kotesovec, Mar 21 2014 *)

a(n):=2*sum((binomial(k-2,2*k-n+2)*binomial(k+1,n-k-3))/(k+1),k,floor((n-2)/2),n-3); /* Vladimir Kruchinin, Oct 12 2020 */

G.f.: p^2/2*(1-p^2-2*p^3+p^4-(1+p-p^2)*sqrt((1+p+p^2)*(1-3*p+p^2)));
a(n) ~ sqrt(2) * ((3+sqrt(5))/2)^n / (sqrt(377 + 843/sqrt(5)) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 21 2014. Equivalently, a(n) ~ 5^(1/4) * phi^(2*n - 7) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021
Conjecture: -(2*n-11)*(n-2)*(2*n-9)*a(n) +4*(2*n-11)*(n-3)*(n-5)*a(n-1) +(4*n^3-60*n^2+317*n-582)*a(n-2) +2*(2*n-7)*(2*n^2-26*n+81)*a(n-3) -(n-10)*(2*n-7)*(2*n-9)*a(n-4)=0. - R. J. Mathar, May 30 2016
a(n) = 2 * Sum_{k=floor((n-2)/2)..n-3} C(k-2,2*k-n+2)*C(k+1,n-k-3)/(k+1). - Vladimir Kruchinin, Oct 12 2020

Offset changed to 1 by Emeric Deutsch, Nov 07 2009
More terms from Vincenzo Librandi, Mar 22 2014
Name modified by Alois P. Heinz, Sep 21 2016

A088518 Symmetric secondary structures of RNA molecules with n nucleotides.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 5, 9, 12, 21, 29, 50, 71, 121, 175, 296, 434, 730, 1082, 1812, 2709, 4521, 6807, 11328, 17157, 28485, 43359, 71844, 109830, 181674, 278769, 460443, 708840, 1169283, 1805291, 2974574, 4604363, 7578937, 11758552, 19337489, 30064037

Offset: 0

Emeric Deutsch, Nov 18 2003

nonn

Diagonal sums of triangle in A088855. - Philippe Deléham, Jan 04 2009
Number of prime symmetric Dyck (n+2)-paths with no ascent of length 1. E.g., the a(3) = 2 5-paths are UUUUUDDDDD and UUUDDUUDDD. - David Scambler, Aug 27 2012
a(n) is the number of 3412-avoiding involutions on [n] with no transpositions of the form (i,i+1) that are invariant under the reverse complement map. For example, a(5)=4 counts the involutions 12345, 14325, 52341, 54321. - Juan B. Gil, May 23 2020

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.

Cf. A000045, A004148.

b:= proc(n) option remember;
      `if`(n=0, 1, b(n-1)+ add(b(k)*b(n-2-k), k=1..n-2))
    end:
a:= proc(n) option remember; `if`(n<2, 1,
      a(n-1) +a(n-2) +`if`(irem(n, 2, 'r')=0, -b(r-1), 0))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 27 2012

CoefficientList[Series[(1 - 3*x^2 + x^4 - Sqrt[1 - 2*x^2 - x^4 - 2*x^6 + x^8])/(2*x^2*(-1 + x + x^2)), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)
b[n_] := b[n] = If[n==0, 1, b[n-1] + Sum[b[k]*b[n-2-k], {k, 1, n-2}]]; a[n_] := a[n] = If[n<2, 1, a[n-1] + a[n-2] + If[{q, r} = QuotientRemainder[n, 2 ]; r==0, -b[q-1], 0]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)

G.f.: H(z) satisfies z^2*(1-z-z^2)*H^2 + (1-z-z^2)*(1+z-z^2)*H - (1+z-z^2) = 0. H = (1/(1-z-z^2))*C(-z^2/(1-3z^2+z^4)), where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function. a(0)=a(1)=1; a(2n) = a(2n-1) + a(2n-2) - A004148(n-1) for n > 0; a(2n+1) = a(2n) + a(2n-1) for n > 0.
a(n) = F(n) - Sum_{i=1..floor(n/2)-1} A004148(i)*F(n-1-2i), where F(i)=A000045(i) are the Fibonacci numbers. - Emeric Deutsch, Nov 19 2003
a(n) is asymptotic to c*phi^n/sqrt(n) where phi=(1+sqrt(5))/2 and c=0.86.... - Benoit Cloitre, Nov 19 2003
In closed form, c = sqrt(1+3/sqrt(5)) / sqrt(Pi) = 0.863346635039540133... - Vaclav Kotesovec, Mar 21 2014
D-finite with recurrence (n+2)*a(n) -a(n-1) +(-2*n-1)*a(n-2) -2*a(n-3) +(-n+3)*a(n-4) -2a(n-5) +(-2*n+13)*a(n-6) -a(n-7) +(n-8)*a(n-8)=0. - R. J. Mathar, Jul 26 2022

A089732 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n having k (1,1) steps (can be easily translated into RNA secondary structure terminology). Except for row 0, row n has ceiling(n/2) entries.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 6, 1, 1, 10, 6, 1, 15, 20, 1, 1, 21, 50, 10, 1, 28, 105, 50, 1, 1, 36, 196, 175, 15, 1, 45, 336, 490, 105, 1, 1, 55, 540, 1176, 490, 21, 1, 66, 825, 2520, 1764, 196, 1, 1, 78, 1210, 4950, 5292, 1176, 28, 1, 91, 1716, 9075, 13860, 5292, 336, 1, 1, 105

Offset: 0

Emeric Deutsch, Jan 07 2004

			T(4,1)=3 because we have UHDH, HUHD and UHHD, where U=(1,1), D=(1,-1), H=(1,0).
1; 1; 1; 1,1; 1,3; 1,6,1; 1,10,6; 1,15,20,1; 1,21,50,10; 1,28,105,50,1.
From _Tom Copeland_, May 14 2012: (Start)
Or as irregular table whose diagonals are rows of A001263:
[1] 1;
[2] 1;
[3] 1,  1;
[4] 1,  3,;
[5] 1,  6,   1;
[6] 1, 10,   6;
[7] 1, 15,  20,  1;
[8] 1, 21,  50, 10;
[9] 1, 28, 105, 50, 1; (End)

A. Panayotopoulos and P. Vlamos, Cutting Degree of Meanders, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From _N. J. A. Sloane_, Dec 29 2012
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
Yuriy Shablya and Dmitry Kruchinin, Algorithms for ranking and unranking the combinatorial set of RNA secondary structures, arXiv:2301.11890 [cs.DS], 2023.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]
M. S. Waterman, Home Page (contains copies of his papers)

Row sums give A004148.

{T(n,k)=local(A); if(n<1, k==0, n--; A=1+O(x); for(i=1,(n+1)\2, A = 1/(1/(1+x*x*y*A)-x)); polcoeff(polcoeff(A,n),k))} /* Michael Somos, Sep 08 2005 */

T(0, 0) = 1;
T(n, k) = binomial(n-k, k)*binomial(n-k, k+1)/(n-k) for 2k <= n-1.
G.f. = g = (1 - z + tz^2 - sqrt(1 - 2z + z^2 - 2tz^2 - 2tz^3 + t^2*z^4))/(2tz^2), solution of g = 1 + zg + tz^2*g(g-1). G.f. = 1+r(tz, z), where r(t, z) is the Narayana function defined by r = z(1+r)(1+tr). Column g.f.'s are 1/(1-z) for column 0 and z^(k+1)*N_k(z)/(1-z)^(2k+1) for columns k=1, 2, ..., where N_k(z) = (1/k)*Sum_{j=1..k} binomial(k, j)*binomial(k, j-1)*z^(j-1) are the Narayana polynomials.
G.f. g(z, t) = Sum_{n, k} T(n, k)z^n*t^k = 1/(1 - z + z^2*t(1-g(z, t))). - Michael Somos, Sep 08 2005
Given g.f. g(z, t) then G=z*g(z, t) series reversion in z is -G(-z, t). - Michael Somos, Sep 08 2005
Given g.f. g(z, t) then G=z*g(z, t) satisfies G = z + z*G/(1-t*z*G). - Michael Somos, Sep 08 2005

A112806 Expansion of solution of functional equation.

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 312, 1277, 5369, 23049, 100612, 445214, 1992606, 9004260, 41025315, 188259072, 869305315, 4036286518, 18832973733, 88259024068, 415252542641, 1960718710035, 9288106921038, 44129146527731

Offset: 0

Michael Somos, Sep 20 2005

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000
Gi-Sang Cheon, S.-T. Jin, L. W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Available online 30 March 2015.

Cf. A004148, A216490.

a(n):=sum((binomial(n+2*i+1,i)*sum(binomial(k,n-k-2*i)*(-1)^(n-k)*binomial(n+k+2*i,k),k,0,n-2*i))/(n+2*i+1),i,0,n/2); /* Vladimir Kruchinin, Mar 07 2016 */

{a(n)=local(A); if(n<0, 0, A=x+O(x^4); for(k=1,n, A=x+subst(x^2/(1-x^3),x,x*A)); polcoeff(A,3*n+1))}

{a(n)=local(A=1+x+x*O(x^n));for(i=1,n,A=1+x*A^2/(1-x^2*A^3));polcoeff(A,n)} \\ Paul D. Hanna, Jun 06 2012

Given g.f. A(x), then series reversion of B(x)=x*A(x^3) is -B(-x).
Given g.f. A(x), then y=x*A(x^3) satisfies y=x+(xy)^2/(1-(xy)^3).
G.f. satisfies: A(x) = 1 + x*A(x)^2/(1 - x^2*A(x)^3). - Paul D. Hanna, Jun 06 2012
G.f. satisfies: A(x) = 1/A(-x*A(x)^3); note that the Catalan function C(x) = 1 + x*C(x)^2 (A000108) also satisfies this condition. - Paul D. Hanna, Jun 06 2012
a(n) = Sum_{i=0..n/2}((binomial(n+2*i+1,i)*Sum_{k=0..n-2*i}(binomial(k,n-k-2*i)*(-1)^(n-k)*binomial(n+k+2*i,k)))/(n+2*i+1)). - Vladimir Kruchinin, Mar 07 2016
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1,k) * binomial(2*n-k+1,n-2*k)/(2*n-k+1). - Seiichi Manyama, Aug 28 2023

A166288 Triangle read by rows: T(n,k) is the number of Dyck paths with no UUU's and no DDD's, of semilength n and having k UDUD's (0<=k <= n-1; U=(1,1), D=(1,-1)).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 4, 5, 6, 1, 1, 6, 12, 9, 8, 1, 1, 9, 23, 24, 14, 10, 1, 1, 17, 38, 56, 40, 20, 12, 1, 1, 26, 84, 100, 110, 60, 27, 14, 1, 1, 46, 145, 250, 210, 190, 84, 35, 16, 1, 1, 81, 280, 480, 580, 385, 301, 112, 44, 18, 1, 1, 135, 551, 995, 1225, 1155, 644, 448, 144, 54, 20, 1, 1

Offset: 1

Emeric Deutsch, Oct 12 2009

Sum of entries in row n = A004148(n+1) (the secondary structure numbers).
T(n,0) = A166289(n).
Sum(k*T(n,k), k=0..n-1) = A166290(n).

			T(5,2) = 6 because we have (UDUDUD)UUDD, UDU(UDUDUD)D, UUDD(UDUDUD), U(UDUD)D(UDUD), U(UDUDUD)DUD, and (UDUD)U(UDUD)D (the UDUD's are shown between parentheses).
Triangle starts:
  1;
  1,  1;
  2,  1,  1;
  2,  4,  1,  1;
  4,  5,  6,  1,  1;
  6, 12,  9,  8,  1, 1;
  9, 23, 24, 14, 10, 1, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A004148, A166289, A166290.

T(2n,n) gives A333156.

F := RootOf(z^3*G^2-(1+z-t*z)*(1-t*z-z^2)*G+(1+z-t*z)^2, G): Fser := series(F, z = 0, 15): for n to 12 do P[n] := sort(coeff(Fser, z, n)) end do: for n to 12 do seq(coeff(P[n], t, j), j = 0 .. n-1) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x or t=8, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 7, 4, 7, 2, 2, 8][t])
      +`if`(t=4, z, 1)  *b(x-1, y-1, [5, 3, 6, 3, 6, 8, 3][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=1..15);  # Alois P. Heinz, Jun 04 2014

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x || t == 8, 0, If[x == 0, 1, Expand[b[x-1, y+1, {2, 7, 4, 7, 2, 2, 8}[[t]] ] + If[t == 4, z, 1]*b[x-1, y-1, {5, 3, 6, 3, 6, 8, 3}[[t]] ]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 1, 15}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

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

A167539 a(n) = Sum_{k=0..[n/2]} C(n-k,k)^2 * n/(n-k), n>=1.

Original entry on oeis.org

1, 3, 7, 15, 36, 87, 211, 519, 1285, 3198, 7998, 20079, 50571, 127725, 323367, 820407, 2085306, 5309169, 13537045, 34561890, 88347091, 226079208, 579110262, 1484766015, 3809948461, 9783998877, 25143452881, 64658016249, 166375274790

Offset: 1

Paul D. Hanna, Nov 23 2009

nonn

			L.g.f.: L(x) = x + 3*x^2/2 + 7*x^3/3 + 15*x^4/4 + 36*x^5/5 + 87*x^6/6 +...
exp(L(x)) = 1 + x + 2*x^2 + 6*x^3 + 16*x^4 + 45*x^5 + 142*x^6 + 459*x^7 +...+ A004148(n+1)*x^n/n +...

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

Cf. A004148, variants: A166895, A166897, A166899.

Table[Sum[(Binomial[n - k, k]^2)*(n/(n - k)), {k, 0, n/2}], {n, 1, 100}] (* G. C. Greubel, Jun 15 2016 *)

{a(n) = sum(k=0,n\2, binomial(n-k,k)^2 * n/(n-k))}
for(n=1,30,print1(a(n),", "))

{a(n) = n * polcoeff( log( (1 - x - x^2 - sqrt((1+x+x^2)*(1-3*x+x^2) +x^6*O(x^n) )) / (2*x^3) ), n)}
for(n=1,30,print1(a(n),", "))

{a(n) = sum(k=0,n-1,sum(j=0,k, binomial(n-k+j,n-k)*n/(n-k+j) * binomial(n-k,k-j)*binomial(k-j,j)))}
for(n=1,30,print1(a(n),", "))

L.g.f.: Log((1 - x - x^2 - sqrt((1+x+x^2)*(1-3*x+x^2)))/(2*x^3)) = Sum_{n>=1} a(n)*x^n/n. - Paul D. Hanna, Jul 19 2015
L.g.f.: -Log((1 - x - x^2 + sqrt((1+x+x^2)*(1-3*x+x^2)))/2) = Sum_{n>=1} a(n)*x^n/n. (Minor simplification of the l.g.f. given above.) - Petros Hadjicostas, Oct 25 2017
a(n) = Sum_{k=0..n-1} Sum_{j=0..k} C(n-k+j,n-k)*n/(n-k+j) * C(n-k,k-j)*C(k-j,j).
a(n) ~ 5^(1/4) * phi^(2*n + 1) / (2*sqrt(Pi*n)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Nov 27 2017

cp's OEIS Frontend

A023422 Generalized Catalan Numbers x^2*A(x)^2 -(1-x+x^2+x^3+x^4+x^5)*A(x) + 1 =0.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A023423 Generalized Catalan Numbers x^2*A(x)^2 -(1-x+x^2+x^3+x^4+x^5+x^6)*A(x) + 1 =0.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A097724 Triangle read by rows: T(n,k) is the number of left factors of Motzkin paths without peaks, having length n and endpoint height k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A247294 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having a total of k uhd and uHd strings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A075125 Number of parallelogram polyominoes of site-perimeter n (also called staircase polyominoes, although that term is overused).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A088518 Symmetric secondary structures of RNA molecules with n nucleotides.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A089732 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n having k (1,1) steps (can be easily translated into RNA secondary structure terminology). Except for row 0, row n has ceiling(n/2) entries.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A023422 Generalized Catalan Numbers x^2A(x)^2 -(1-x+x^2+x^3+x^4+x^5)A(x) + 1 =0.

A023423 Generalized Catalan Numbers x^2A(x)^2 -(1-x+x^2+x^3+x^4+x^5+x^6)A(x) + 1 =0.