A004148 -id:A004148 - cp's OEIS frontend

A110236 Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).

1, 2, 4, 10, 24, 58, 143, 354, 881, 2204, 5534, 13940, 35213, 89162, 226238, 575114, 1464382, 3734150, 9534594, 24374230, 62377881, 159793932, 409717004, 1051405260, 2700168229, 6939388478, 17845927498, 45922416814, 118238842174

Offset: 1

Emeric Deutsch, Jul 17 2005

nonn

Number of UHD's in all peakless Motzkin paths of length n+2; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(2)=2 because in HHHH, HUHD, UHDH, and UHHD we have a total of 0+1+1+0 UHD's.

			a(3)=4 because in the 2 (=A004148(3)) peakless Motzkin paths of length 3, namely HHH and UHD (where U=(1,1), H=(1,0) and D=(1,-1)), we have altogether 4 H steps.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Cf. A004148, A110235, A089732, A190172, A203611, bisection of A202411.

T:=proc(n,k) if n+k mod 2 = 0 then 2*binomial((n+k)/2,k)*binomial((n+k)/2,k-1)/(n+k) else 0 fi end:seq(add(k*T(n,k),k=1..n),n=1..33);

Rest[CoefficientList[Series[((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1) /(2*x), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 13 2014 *)

x='x+O('x^66); Vec(((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1)/(2*x)) /* Joerg Arndt, Mar 27 2013 */

a(n) = Sum_{k=1..n} k*T(n, k), where T(n, k) = floor(2/(n+k))*binomial((n+k)/2, k)*binomial((n+k)/2, k-1) for n+k mod 2 = 0 and T(n, k)=0 otherwise.
G.f.: (1-z+z^2-Q)/(2*z*Q), where Q = sqrt(1 - 2z - z^2 - 2z^3 + z^4).
a(n) = Sum_{k=1..n} k*A110235(n,k).
a(n) = Sum_{k>=0} k*A190172(n+2,k).
a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k+j,n-k-j)*C(k,n-k-j). - Paul Barry, Oct 24 2006, index corrected Jul 13 2011
a(n+1) = Sum_{k=0..floor(n/2)} C(n-k+1,k+1)*C(n-k,k); a(n+1) := Sum_{k=0..n} C(k+1,n-k+1)*C(k,n-k). - Paul Barry, Aug 17 2009, indices corrected Jul 13 2011
G.f.: z*S^2/(1-z^2*S^2), where S = 1 + z*S + z^2*S*(S-1) (the g.f. of the RNA secondary structure numbers; A004148).
a(n) = -f_{n}(-n) with f_1(n)=n and f_{p}(n) = (n+p-1)*(n+p+1-1)^2 *(n+p+2-1)^2*...*(n+p+(p-1)-1)^2/(p!*(p-1)!) + f_{p-1}(n) for p > 1. - Alzhekeyev Ascar M, Jun 27 2011
Let A=floor(n/2), R=n-1, B=A-R/2+1, C=A+1, D=A-R and Z=1 if n mod 2 = 1, otherwise Z = n*(n+2)/4. Then a(n) = Z*Hypergeometric([1,C,C+1,D,D-1],[B,B,B-1/2,B-1/2],1/16). - Peter Luschny, Jan 14 2012
D-finite with recurrence (n+1)*a(n) -3*n*a(n-1) +2*(n-3)*a(n-2) +3*(-n+2)*a(n-3) +2*(n-1)*a(n-4) +3*(-n+4)*a(n-5) +(n-5)*a(n-6)=0. - R. J. Mathar, Nov 30 2012
G.f.: ((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1)/(2*x). - Mark van Hoeij, Mar 27 2013
From Vaclav Kotesovec, Feb 13 2014: (Start)
Recurrence: (n-2)*(n-1)*(n+1)*a(n) = (n-2)*n*(2*n-1)*a(n-1) + (n-1)*(n^2 - 2*n - 2)*a(n-2) + (n-2)*n*(2*n-3)*a(n-3) - (n-3)*(n-1)*n*a(n-4).
a(n) ~ (sqrt(5)+3)^(n+1) / (5^(1/4) * sqrt(Pi*n) * 2^(n+2)). (End)

A023432 Number of Dyck n-paths with ascents and descents of length equal to 1 (mod 3).

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 7, 12, 22, 42, 80, 152, 292, 568, 1112, 2185, 4313, 8557, 17050, 34089, 68370, 137542, 277475, 561185, 1137595, 2311014, 4704235, 9593662, 19598920, 40103635, 82185653, 168666493, 346613232, 713200114, 1469254621, 3030218948, 6256281188

Offset: 0

Olivier Gérard

Number of Motzkin paths of length n-1 with no peaks, no double rises and no doubledescents (i.e., no UD's, no UU's and no DD's, where U=(1,1) and D=(1,-1), n>0; can be easily formulated using RNA secondary structure terminology). E.g., a(5)=4 because we have HHHH, HUHD, UHDH and UHHD; here H=(1,0). Also number of peakless Motzkin paths of length n in which each D=(1,-1) step is followed by an H=(1,0) step (can be easily formulated using RNA secondary structure terminology). E.g., a(5)=4 because we have HHHHH, HUHDH, UHDHH and UHHDH (here U=(1,1)). - Emeric Deutsch, Jan 09 2004
The coefficient of t^n in the power series expansion of the solution u in the equation (1-t*u)(u-t*u-t-t^2*u^2+t^3*u)=0. - Shanzhen Gao, May 13 2011
Also the number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 3).  The a(5) = 4 paths for n=5 are: UDUDUDUDUD, UUUUDDDDUD, UUUUDUDDDD, UDUUUUDDDD. - Alois P. Heinz, May 09 2012
a(n)=number of strictly alternating bargraphs of semiperimeter n+2. A bargraph is said to be strictly alternating if its ascents and descents alternate and all the formed peaks and valleys have width 1. An ascent (descent) is a maximal sequence of consecutive U (D) steps. Example: a(4) = 2 because among the 35 (=A082582(6)) bargraphs of semiperimeter 6 only those corresponding to the compositions [5] and [2,1,2] are strictly alternating. - Emeric Deutsch, Aug 26 2016
For n>=1, a(n) is the number of Dyck paths of semilength n+2 in which all ascent and descent lengths are >=3. For example, a(4) = 2 counts U^6.D^6, U^3.D^3.U^3.D^3 where ^ denotes repetition and a dot denotes concatenation. The gf F(x) = 1 + x^3 + x^4 + x^5 + 2*x^6 + ...  for these paths satisfies F = 1 + x^3/(1-x) + (F-1)x^3/((1-x)(1-x*F)), which follows from a first return decomposition and summing over the lengths of the first ascent and first descent. A bijection to the title paths would be interesting. - David Callan, Dec 07 2021

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 12*x^6 + 22*x^7 +...
where the logarithm of the g.f. equals the series:
log(A(x)) = (1 + x^2)*x + (1 + 2^2*x^2 + x^4)*x^2/2 + (1 + 3^2*x^2 + 3^2*x^4 + x^6)*x^3/3 + (1 + 4^2*x^2 + 6^2*x^4 + 4^2*x^6 + x^8)*x^4/4 + (1 + 5^2*x^2 + 10^2*x^4 + 10^2*x^6 + 5^2*x^8 + x^10)*x^5/5 + ... - _Paul D. Hanna_

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
A.J. Bu and Robert Dougherty-Bliss, Enumerating restricted Dyck paths with context free grammars, #A69 INTEGERS 21 (2021).
Emeric Deutsch and S. Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv preprint arXiv:1609.00088 [math.CO], 2016.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, (submitted to INTEGERS: The Electronic Journal of Combinatorial Number Theory).
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.

Cf. A000108, A001006, A004148, A004149, A006318, A082582, A275448.

Column k=3 of A212363.

a023432 n = a023432_list !! n
a023432_list = 1 : 1 : f [1,1] where
   f xs'@(x:_:xs) = y : f (y : xs') where
     y = x + sum (zipWith (*) xs $ reverse $ tail xs)
-- Reinhard Zumkeller, Nov 13 2012

a:= proc(n) option remember;
      `if`(n=0, 1, a(n-1) +add(a(k)*a(n-3-k), k=1..n-3))
    end:
seq(a(n), n=0..50); # Alois P. Heinz, May 09 2012

Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-3-k ], {k, 0, n-4} ];
CoefficientList[Series[(1-x+x^3-Sqrt[1-2*x-2*x^3+x^2-2*x^4+x^6])/(2*x^3), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 22 2014 *)

a(n):=if n=0 then 1 else sum(binomial(n-2*q,q)*binomial(n-2*q,q+1)/(n-2*q),q,0,(n-1)/2); /* Vladimir Kruchinin, Jan 21 2019 */

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

{a(n)=polcoeff( exp(sum(m=1, n+1, x^m/m*sum(j=0, m, binomial(m, j)^2*x^(2*j))+x*O(x^n))), n)} /* Paul D. Hanna */

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, (1-x^2)^(2*m+1)*sum(j=0, n\2, binomial(m+j, j)^2*x^(2*j))*x^m/m)+x*O(x^n))); polcoeff(A, n, x)} /* Paul D. Hanna */

G.f.: (1-z+z^3-sqrt(1-2z-2z^3+z^2-2z^4+z^6))/(2z^3). - Emeric Deutsch, Jan 09 2004
G.f.: 1/(1-x-x^4/(1-x-x^3-x^4/(1-x-x^3-x^4/(1-x-x^3-x^4/(1-... (continued fraction). - Paul Barry, May 22 2009
G.f.: 1/(1-x/(1-x^3/(1-x/(1-x^3/(1-x/(1-x^3/(1-... (continued fraction). - Paul Barry, Nov 30 2009
From Paul D. Hanna, Nov 01 2011: (Start)
G.f. (for offset -1) satisfies: A(x) = (1 + x*A(x))*(1 + x^3*A(x)).
G.f.: A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * x^(2*k) ).
G.f.: A(x) = exp( Sum_{n>=1} x^n/n * (1-x^2)^(2*n+1) * Sum_{k>=0} C(n+k,k)^2 * x^(2*k) ). (End)
a(n) ~ sqrt(3-5*r+2*r^2-3*r^3-2*r^4) / (2*sqrt(2*Pi)*n^(3/2)*r^(n+3)), where r = 0.465571231876768... is the root of the equation 1+r^2+r^6 = 2*r*(1+r^2+r^3). - Vaclav Kotesovec, Mar 22 2014
a(n) = Sum_{k=0..(n-1)/2} C(n-2*k,k)*C(n-2*k,k+1)/(n-2*k), n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019
D-finite with recurrence (n+3)*a(n) +(-2*n-3)*a(n-1) +n*a(n-2) +(-2*n+3)*a(n-3) +2*(-n+3)*a(n-4) +(n-6)*a(n-6)=0. - R. J. Mathar, Jul 23 2023

New name, using a comment of Alois P. Heinz, from Peter Luschny, Jan 21 2019

A215576 G.f. satisfies A(x) = (1 + x^2)(1 + xA(x)^2).

Original entry on oeis.org

1, 1, 3, 8, 24, 80, 278, 997, 3670, 13782, 52588, 203314, 794726, 3135540, 12470444, 49942305, 201233170, 815205699, 3318291966, 13565162636, 55669063762, 229257178198, 947142023262, 3924380904498, 16303716754884, 67899954924360, 283425070356740, 1185551594834910

Offset: 0

Paul D. Hanna, Aug 16 2012

nonn

More generally, for fixed parameters p, q, r, and s, if F(x) satisfies:
F(x) = exp( Sum_{n>=1} x^(n*r)*F(x)^(n*p)/n * [Sum_{k=0..n} C(n,k)^2 * x^(k*s)*F(x)^(k*q)] ),
then F(x) = (1 + x^r*F(x)^(p+1))*(1 + x^(r+s)*F(x)^(p+q+1)).

			G.f.: A(x) = 1 + x + 3*x^2 + 8*x^3 + 24*x^4 + 80*x^5 + 278*x^6 + 997*x^7 +...
Related expansions:
A(x)^2 = 1 + 2*x + 7*x^2 + 22*x^3 + 73*x^4 + 256*x^5 + 924*x^6 + 3414*x^7 +...
where A(x) = 1+x^2 + x*(1+x^2)*A(x)^2.
The logarithm of the g.f. A = A(x) equals the series:
log(A(x)) = (1 + x/A^2)*A*x + (1 + 2^2*x/A^2 + x^2/A^4)*A^2*x^2/2 +
 (1 + 3^2*x/A^2 + 3^2*x^2/A^4 + x^3/A^6)*A^3*x^3/3 +
 (1 + 4^2*x/A^2 + 6^2*x^2/A^4 + 4^2*x^3/A^6 + x^4/A^8)*A^4*x^4/4 +
 (1 + 5^2*x/A^2 + 10^2*x^2/A^4 + 10^2*x^3/A^6 + 5^2*x^4/A^8 + x^5/A^10)*A^5*x^5/5 +
 (1 + 6^2*x/A^2 + 15^2*x^2/A^4 + 20^2*x^3/A^6 + 15^2*x^4/A^8 + 6^2*x^5/A^10 + x^6/A^12)*A^6*x^6/6 +...
more explicitly,
log(A(x)) = x + 5*x^2/2 + 16*x^3/3 + 57*x^4/4 + 231*x^5/5 + 938*x^6/6 + 3830*x^7/7 + 15833*x^8/8 +...

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

Cf. A199876, A199877, A198951, A198953, A198957, A192415, A198888, A200717, A004148, A036765.

Cf. A186241, A199874, A200074, A200075, A200718, A200719.

nmax=20;aa=ConstantArray[0,nmax]; aa[[1]]=1;Do[AGF=1+Sum[aa[[n]]*x^n,{n,1,j-1}]+koef*x^j; sol=Solve[Coefficient[(1+x^2)*(1+x*AGF^2)-AGF,x,j]==0,koef][[1]];aa[[j]]=koef/.sol[[1]],{j,2,nmax}];Flatten[{1,aa}] (* Vaclav Kotesovec, Aug 19 2013 *)
CoefficientList[Series[(1 - Sqrt[1 - 4*x*(1 + x^2)^2]) / (2*x*(1 + x^2)), {x, 0, 30}], x] (* Vaclav Kotesovec, Oct 11 2018 *)
Table[Sum[Binomial[2*n - 4*i + 1, i] * Binomial[2*n - 4*i + 1, n - 2*i]/(2*n - 4*i + 1), {i, 0, Floor[n/2]}], {n, 0, 30}] (* Vaclav Kotesovec, Oct 11 2018, after Vladimir Kruchinin *)

{a(n)=polcoeff((1 - sqrt(1 - 4*x*(1+x^2 +x*O(x^n))^2)) / (2*x*(1+x^2 +x*O(x^n))),n)}
for(n=0,31,print1(a(n),", "))

{a(n)=local(A=1+x); for(i=1, n, A=(1+x*A^2)*(1+x^2)+x*O(x^n)); polcoeff(A, n)}

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2*x^j/A^(2*j))*(x*A+x*O(x^n))^m/m))); polcoeff(A, n, x)}

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, (1-x/A^2)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j/A^(2*j))*x^m*A^m/m))); polcoeff(A, n, x)}

G.f. satisfies:
(1) A(x) = (1 - sqrt(1 - 4*x*(1+x^2)^2)) / (2*x*(1+x^2)).
(2) A(x) = exp( Sum_{n>=1} (x^n/n) * A(x)^n * (Sum_{k=0..n} C(n,k)^2 * x^k / A(x)^(2*k)) ).
(3) A(x) = exp( Sum_{n>=1} (1-x/A(x)^2)^(2*n+1) * (Sum_{k>=0} C(n+k,k)^2*x^k/A(x)^(2*k)) * x^n*A(x)^n/n ).
(4) A(x) = x / Series_Reversion( x*G(x) ) where G(x) is the g.f. of A200717.
(5) A(x) = G(x/A(x)) where G(x) = A(x*G(x)) is the g.f. of A200717.
Recurrence: (n+1)*a(n) = 2*(2*n-1)*a(n-1) - (n+1)*a(n-2) + 6*(2*n-5)*a(n-3) + 6*(2*n-9)*a(n-5) + 2*(2*n-13)*a(n-7). - Vaclav Kotesovec, Aug 19 2013
a(n) ~ c*d^n/n^(3/2), where d = 4.41997678... is the root of the equation -4-8*d^2-4*d^4+d^5=0 and c = sqrt(d*(8 + 16*d^2 + 8*d^4 + 3*d^5 + d^7) / (Pi*(1 + d^2)^3))/4 = 0.648259186485429075561822659694489853... - Vaclav Kotesovec, Aug 19 2013, updated Oct 11 2018
a(n) = Sum_{i=0..floor(n/2)} C(2*n-4*i+1,i)*C(2*n-4*i+1,n-2*i)/(2*n-4*i+1). - Vladimir Kruchinin, Oct 11 2018

A064645 Table where the entry (n,k) (n >= 0, k >= 0) gives number of Motzkin paths of the length n with the minimum peak width of k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 9, 2, 1, 1, 1, 21, 4, 1, 1, 1, 1, 51, 8, 2, 1, 1, 1, 1, 127, 17, 4, 1, 1, 1, 1, 1, 323, 37, 8, 2, 1, 1, 1, 1, 1, 835, 82, 16, 4, 1, 1, 1, 1, 1, 1, 2188, 185, 33, 8, 2, 1, 1, 1, 1, 1, 1, 5798, 423, 69, 16, 4, 1, 1, 1, 1, 1, 1, 1, 15511, 978, 146, 32, 8, 2, 1, 1, 1, 1, 1, 1, 1, 41835, 2283, 312, 65, 16, 4, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Antti Karttunen, Oct 03 2001

			E.g., we have the following nine Motzkin paths of length 4, of which the last 4 have each peak at least of width 1 and the last 2 with each peak at least 2 dashes wide, so M(4,0) = 9, M(4,1) = 4 and M(4,2) = 2.
   /\                                 _       _     __
  /  \   /\/\   __/\   _/\_   /\__   / \_   _/ \   /  \   ____
The array starts:
      1    1   1   1   1   1   1   1   1   1   1
      1    1   1   1   1   1   1   1   1   1   1
      2    1   1   1   1   1   1   1   1   1   1
      4    2   1   1   1   1   1   1   1   1   1
      9    4   2   1   1   1   1   1   1   1   1
     21    8   4   2   1   1   1   1   1   1   1
     51   17   8   4   2   1   1   1   1   1   1
    127   37  16   8   4   2   1   1   1   1   1
    323   82  33  16   8   4   2   1   1   1   1
    835  185  69  32  16   8   4   2   1   1   1
   2188  423 146  65  32  16   8   4   2   1   1
   5798  978 312 133  64  32  16   8   4   2   1
  15511 2283 673 274 129  64  32  16   8   4   2

Seiichi Manyama, Table of n, a(n) for n = 0..9869 (rows n=0..139 of triangle, flattened)

Column k=0: Motzkin numbers (A001006), column k=1: A004148, column k=2: A004149, column k=3: A023421, column k=4: A023422, column k=5: A023423. Uses the table A001263(n, k).

# trinv() given in A054425
[seq(A064645(j),j=0..104)]; A064645 := (n) -> Mpw((((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), (n-((trinv(n)*(trinv(n)-1))/2)));
C := (n,k) -> `if`((n <= 0),0,binomial(n,k));
Mpw := proc(n,m) local i,k; 1+add(add(A001263(i,k)*C(n-(m*k),2*i),k=1..i),i=0..floor(n/2)); end;

trinv[n_] := Floor[(1 + Sqrt[8 n + 1])/2];
CC[n_, k_] := If[n <= 0, 0, Binomial[n, k]];
a[n_] := Mpw[(((trinv[n] - 1)*(((1/2) trinv[n]) + 1)) - n), (n - ((trinv[n] (trinv[n] - 1))/2))];
Mpw[n_, m_] := 1 + Sum[Sum[If[k == 0, 0, Binomial[i - 1, k - 1] Binomial[i, k - 1]/k] CC[n - m*k, 2i], {k, 1, i}], {i, 0, n/2}];
Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Mar 06 2016, adapted from Maple *)

A131198 Triangle T(n,k), 0 <= k <= n, read by rows, given by [1,0,1,0,1,0,1,0,...] DELTA [0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 6, 6, 1, 0, 1, 10, 20, 10, 1, 0, 1, 15, 50, 50, 15, 1, 0, 1, 21, 105, 175, 105, 21, 1, 0, 1, 28, 196, 490, 490, 196, 28, 1, 0, 1, 36, 336, 1176, 1764, 1176, 336, 36, 1, 0, 1, 45, 540, 2520, 5292, 5292, 2520, 540, 45, 1, 0

Offset: 0

Philippe Deléham, Oct 20 2007

Mirror image of triangle A090181, another version of triangle of Narayana (A001263).

Equals A133336*A130595 as infinite lower triangular matrices. - Philippe Deléham, Oct 23 2007

			Triangle begins:
  1;
  1,  0;
  1,  1,   0;
  1,  3,   1,   0;
  1,  6,   6,   1,   0;
  1, 10,  20,  10,   1,   0;
  1, 15,  50,  50,  15,   1,  0;
  1, 21, 105, 175, 105,  21,  1, 0;
  1, 28, 196, 490, 490, 196, 28, 1, 0; ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009), Article 09.7.6.
Paul Barry, On a Generalization of the Narayana Triangle, J. Int. Seq. 14 (2011), Article 11.4.5.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry and A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
FindStat - Combinatorial Statistic Finder, The number of peaks of a Dyck path., The number of double rises of a Dyck path., The number of valleys of a Dyck path., The number of left oriented leafs except the first one of a binary tree., The number of left tunnels of a Dyck path.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

Cf. A000217, A002415, A006542, A006857.

[[n le 0 select 1 else (n-k)*Binomial(n,k)^2/(n*(k+1)): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Feb 06 2018

T := (n,k) -> `if`(n=0, 0^n, binomial(n,k)^2*(n-k)/(n*(k+1)));
seq(print(seq(T(n,k), k=0..n)), n=0..5); # Peter Luschny, Jun 08 2014
R := n -> simplify(hypergeom([1 - n, -n], [2], x)):
Trow := n -> seq(coeff(R(n, x), x, k), k = 0..n):
seq(print(Trow(n)), n = 0..9); # Peter Luschny, Apr 26 2022

Table[If[n == 0, 1, (n-k)*Binomial[n,k]^2/(n*(k+1))], {n,0,10}, {k,0,n}] //Flatten (* G. C. Greubel, Feb 06 2018 *)

for(n=0,10, for(k=0,n, print1(if(n==0,1, (n-k)*binomial(n,k)^2/(n* (k+1))), ", "))) \\ G. C. Greubel, Feb 06 2018

Sum_{k=0..n} T(n,k)*x^k = A000012(n), A000108(n), A001003(n), A007564(n), A059231(n), A078009(n), A078018(n), A081178(n), A082147(n), A082181(n), A082148(n), A082173(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 respectively.
Sum_{k=0..n} T(n,k)*x^(n-k) = A000007(n), A000108(n), A006318(n), A047891(n+1), A082298(n), A082301(n), A082302(n), A082305(n), A082366(n), A082367(n), for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Oct 23 2007
Sum_{k=0..floor(n/2)} T(n-k,k) = A004148(n). - Philippe Deléham, Nov 06 2007
T(2*n,n) = A125558(n). - Philippe Deléham, Nov 16 2011
T(n, k) = [x^k] hypergeom([1 - n, -n], [2], x). - Peter Luschny, Apr 26 2022

A212363 Number A(n,k) of Dyck n-paths all of whose ascents and descents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 14, 1, 1, 1, 1, 1, 4, 42, 1, 1, 1, 1, 1, 2, 8, 132, 1, 1, 1, 1, 1, 1, 4, 17, 429, 1, 1, 1, 1, 1, 1, 2, 7, 37, 1430, 1, 1, 1, 1, 1, 1, 1, 4, 12, 82, 4862, 1, 1, 1, 1, 1, 1, 1, 2, 7, 22, 185, 16796, 1

Offset: 0

Alois P. Heinz, May 10 2012

			A(3,0) = 1: UDUDUD.
A(3,1) = 5: UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD.
A(4,2) = 4: UDUDUDUD, UDUUUDDD, UUUDDDUD, UUUDUDDD.
A(5,2) = 8: UDUDUDUDUD, UDUDUUUDDD, UDUUUDDDUD, UDUUUDUDDD, UUUDDDUDUD, UUUDUDDDUD, UUUDUDUDDD, UUUUUDDDDD.
A(5,3) = 4: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDUDDDD.
Square array A(n,k) begins:
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   2,  1,  1,  1,  1,  1,  1, ...
  1,   5,  2,  1,  1,  1,  1,  1, ...
  1,  14,  4,  2,  1,  1,  1,  1, ...
  1,  42,  8,  4,  2,  1,  1,  1, ...
  1, 132, 17,  7,  4,  2,  1,  1, ...
  1, 429, 37, 12,  7,  4,  2,  1, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-10 give: A000012, A000108, A004148, A023432, A023427, A212364, A212365, A212366, A212367, A212368, A212369.

A:= proc(n, k) option remember;
      `if`(k=0, 1, `if`(n=0, 1, A(n-1, k)
                   +add(A(j, k)*A(n-k-j, k), j=1..n-k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);
# second Maple program:
A:= (n, k)-> `if`(k=0, 1, coeff(series(RootOf(
              A||k=1+A||k*(x-x^k*(1-A||k)), A||k), x, n+1), x, n)):
seq(seq(A(n, d-n), n=0..d), d=0..15);

A[n_, k_] := A[n, k] = If[k == 0, 1, If[n == 0, 1, A[n-1, k] + Sum[A[j, k]*A[n-k-j, k], {j, 1, n-k}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Jan 15 2014, translated from first Maple program *)

G.f. of column k>0 satisfies: A_k(x) = 1+A_k(x)*(x-x^k*(1-A_k(x))), g.f. of column k=0: A_0(x) = 1/(1-x).
A(n,k) = A(n-1,k) + Sum_{j=1..n-k} A(j,k)*A(n-k-j,k) for n,k>0; A(n,0) = A(0,k) = 1.
G.f. of column k > 0: (1 - x + x^k - sqrt((1 - x + x^k)^2 - 4*x^k)) / (2*x^k). - Vaclav Kotesovec, Sep 02 2014

A025242 Generalized Catalan numbers A(x)^2 -(1+x)^2A(x) +x(2+x+x^2) =0.

Original entry on oeis.org

2, 1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089

Offset: 1

Clark Kimberling, Olivier Gérard

Number of Dyck paths of semilength n-1 with no UUDD (n>1). Example: a(4)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - Emeric Deutsch, Jan 27 2003
a(n) is the number of Dyck (n-2)-paths with no DDUU (n>2). Example: a(6)=13 counts all 14 Dyck 4-paths except UUDDUUDD which contains a DDUU. There is a simple bijective proof: given a Dyck path that avoids DDUU, for every occurrence of UUDD except the first, the ascent containing this UU must be immediately preceded by a UD (else a DDUU would be present). Transfer the latter UD to the middle of the DD in the UUDD. Then insert a new UD in the middle of the first DD if any; if not, the path is a sawtooth UDUD...UD, in which case insert a UD at the end. This is a bijection from DDUU-avoiding Dyck n-paths to UUDD-avoiding Dyck (n+1)-paths. - David Callan, Sep 25 2006
For n>1, a(n) is the number of cyclic permutations of [n-1] that avoid the vincular pattern 13-4-2, i.e., the pattern 1342 where the 1 and 3 must be adjacent. By the trivial Wilf equivalence, the same applies for 24-3-1, 31-2-4, and 42-1-3. - Rupert Li, Jul 27 2021

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 10.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 18.
Vít Jelínek, Toufik Mansour and Mark Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.1, without the leading 2.
Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Séminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.
Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
Toufik Mansour and Mark Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A001006, A006318, A004148, A007477, A082582, A086581.

a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-1-k ], {k, 2, n-1} ];

a(n)=polcoeff((1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4+x*O(x^n)))/2,n)

a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-3)*a(3) for n >= 4.
G.f.: (1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4))/2. - Michael Somos, Jun 08 2000
Conjecture: n*(n+1)*a(n) +(n^2+n+2)*a(n-1) +2*(-9*n^2+15*n+17)*a(n-2) +2*(5*n+4)*(n-4)*a(n-3) +(n+1)*(n-6)*a(n-4) +(5*n+4)*(n-7)*a(n-5)=0. - R. J. Mathar, Jan 12 2013
G.f.: 2 + x - x*G(0), where G(k) = 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013

A091964 Number of left factors of peakless Motzkin paths of length n.

Original entry on oeis.org

1, 2, 4, 9, 21, 50, 121, 296, 730, 1812, 4521, 11328, 28485, 71844, 181674, 460443, 1169283, 2974574, 7578937, 19337489, 49401526, 126350742, 323495259, 829033334, 2126454271, 5458711430, 14023219126, 36049991901, 92734505565

Offset: 0

Emeric Deutsch, Mar 13 2004

nonn

Number of paths from (0,0) to the line x=n, consisting of steps u=(1,1), h=(1,0), d=(1,-1), that never go below the x-axis and a u step is never followed by a d step.
a(n) is also the number of peakless Motzkin paths of length n in which the (1,0)-steps at level 0 come in 2 colors. Example: a(4)=21 because, denoting u=(1,1), h=(1,0), and d=(1,-1), we have 2^4 = 16 paths of shape hhhh, 2 paths of shape huhd, 2 paths of shape uhdh, and 1 path of shape uhhd. - Emeric Deutsch, May 03 2011
Equals diagonal sums of triangle A124428. - Paul D. Hanna, Oct 31 2006

			a(2)=4 because we have hh, hu, uh and uu.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, Symmetric circular matchings and RNA folding. Discr. Math., 312:100-112, 2012. See Prop. 5, C_2^{1}(z).
Asamoah Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.
Helmut Prodinger, Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs, arXiv:2501.13645 [math.CO], 2025. See p. 8.

Cf. A004148, A104559, A124428.

[(&+[Binomial(Floor((n+k)/2),k)*Binomial(Floor((n+k+1)/2),k): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Feb 26 2019

CoefficientList[Series[2/(1-3*x+x^2+Sqrt[1-2*x-x^2-2*x^3+x^4]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)

a(n)=sum(k=0,n,binomial(n-k\2,(k+1)\2)*binomial(n-(k+1)\2,k\2)) \\ Paul D. Hanna, Mar 24 2005

a(n)=sum(k=0,n,binomial((n+k)\2,k)*binomial((n+k+1)\2,k)) \\ Paul D. Hanna, Oct 31 2006

[sum(binomial(floor((n+k)/2),k)*binomial(floor((n+k+1)/2),k) for k in (0..n)) for n in (0..30)] # G. C. Greubel, Feb 26 2019

G.f.: 2/(1 - 3*z + z^2 + sqrt(1 - 2*z - z^2 - 2*z^3 + z^4)).
a(n) = Sum_{k=0..n} C(n-floor(k/2), floor((k+1)/2)) * C(n-floor((k+1)/2), floor(k/2)). - Paul D. Hanna, Mar 24 2005
a(n) = Sum_{k=0..n} C(floor((n+k)/2),k)*C(floor((n+k+1)/2),k). - Paul D. Hanna, Oct 31 2006
G.f.: 1/(1-x-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-... (continued fraction). - Paul Barry, Jun 30 2009
D-finite with recurrence (n+1)*a(n) + 2*(-n-1)*a(n-1) + (-n+1)*a(n-2) + 2*(-n+3)*a(n-3) + (n-3)*a(n-4) = 0. - R. J. Mathar, Nov 24 2012
a(n) ~ (3+sqrt(5))^n / (sqrt(7*sqrt(5)-15) * sqrt(Pi*n) * 2^(n-1/2)). - Vaclav Kotesovec, Feb 12 2014
Equivalently, a(n) ~ phi^(2*n + 2) / (5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021

A093128 Number of dissections of a polygon using strictly disjoint diagonals.

Original entry on oeis.org

1, 1, 3, 6, 13, 29, 65, 148, 341, 793, 1860, 4395, 10452, 24999, 60097, 145130, 351916, 856502, 2091599, 5123437, 12585354, 30995031, 76516348, 189310421, 469335998, 1165790119, 2900870597, 7230320746, 18049387617, 45123390441, 112963369113, 283162526640, 710664478791, 1785645155847, 4491596869206

Offset: 0

David Callan, Mar 23 2004

a(n) is the number of dissections of a regular (n+2)-gon using 0 or more strictly disjoint diagonals.

			a(3)=6 because there are 5 ways to insert a single diagonal into a pentagon plus the empty dissection.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.
Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 8; arXiv:1709.08416 [math.CO], 2017.
Giovanni Resta, Illustration of a(3)-a(10)

Row sums of A093127.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( 1 + (1+x)*( 1 -2*x -x^3 - Sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4) )); // G. C. Greubel, Dec 28 2019

seq(coeff(series(1 + (1+x)*( 1 -2*x -x^3 - sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4), x, n+2), x, n), n = 0..40); # G. C. Greubel, Dec 28 2019

CoefficientList[Series[1 +(1+x)*(1-2*x-x^3 -Sqrt[(1-3*x+x^2)*(1-x)*(1-x^3)])/( 2*x^4), {x,0,40}], x] (* G. C. Greubel, Dec 28 2019 *)

{A132461(n)=sum(k=0,n\2,(binomial(n-k, k)+binomial(n-k-1, k-1))^2)}
{a(n)=polcoeff(exp(sum(m=1,n,A132461(m)*x^m/m)+x*O(x^n)),n)} \\ Paul D. Hanna, Nov 09 2013

def A093128_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1 + (1+x)*( 1 -2*x -x^3 - sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4) ).list()
A093128_list(40) # G. C. Greubel, Dec 28 2019

G.f.: 1 + (1+x)*( 1 -2*x -x^3 - sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4).
a(n) = A004148(n+2) - A004148(n) for n>=1.
Logarithmic derivative yields A132461. - Paul D. Hanna, Nov 09 2013
G.f.: exp( Sum_{n>=1} A132461(n)*x^n/n ), where A132461(n) = Sum_{k=0..[n/2]} (C(n-k,k) + C(n-k-1,k-1))^2. - Paul D. Hanna, Nov 09 2013

Terms a(26) onward added by G. C. Greubel, Dec 28 2019

A180718 G.f.: exp( Sum_{n>=0} [ Sum_{k=0..n} C(n,k)^2x^k ]^2 x^n/n ).

Original entry on oeis.org

1, 1, 3, 8, 25, 80, 271, 952, 3443, 12758, 48212, 185283, 722227, 2849955, 11366379, 45757142, 185726603, 759401542, 3125472832, 12939604503, 53856950922, 225250407802, 946253665230, 3991221520996, 16897320866269, 71782331694315

Offset: 0

Paul D. Hanna, Sep 24 2010

nonn

Compare the g.f. of this sequence to the g.f.s:
. exp( Sum_{n>=0} [Sum_{k=0..n} C(n,k)^2*x^k]*x^n/n ) = (G(x)-1)/x where G(x) = g.f. of A004148.
. exp( Sum_{n>=0} [Sum_{k=0..n} C(n,k)*x^k]^2*x^n/n ) = 1/(1-x*(1+x)^2).

			G.f.: A(x) = 1 + x + 3*x^2 + 8*x^3 + 25*x^4 + 80*x^5 + 271*x^6 +...
The logarithm (A180719) begins:
log(A(x)) = x + 5*x^2/2 + 16*x^3/3 + 61*x^4/4 + 226*x^5/5 + 884*x^6/6 + 3543*x^7/7 + 14429*x^8/8 +...
which equals the sum of the series:
log(A(x)) = (1 + x)^2*x
+ (1 + 4*x + x^2)^2*x^2/2
+ (1 + 9*x + 9*x^2 + x^3)^2*x^3/3
+ (1 + 16*x + 36*x^2 + 16*x^3 + x^4)^2*x^4/4
+ (1 + 25*x + 100*x^2 + 100*x^3 + 25*x^4 + x^5)^2*x^5/5
+ (1 + 36*x + 225*x^2 + 400*x^3 + 225*x^4 + 36*x^5 + x^6)^2*x^6/6 +...

Vaclav Kotesovec, Table of n, a(n) for n = 0..900

Cf. A180719, A004148.

{a(n)=polcoeff(exp(sum(m=1,n,sum(k=0,m,binomial(m,k)^2*x^k)^2*x^m/m)+x*O(x^n)),n)}

cp's OEIS Frontend

A110236 Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A023432 Number of Dyck n-paths with ascents and descents of length equal to 1 (mod 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

Formula

Extensions

A215576 G.f. satisfies A(x) = (1 + x^2)*(1 + x*A(x)^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

A064645 Table where the entry (n,k) (n >= 0, k >= 0) gives number of Motzkin paths of the length n with the minimum peak width of k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A131198 Triangle T(n,k), 0 <= k <= n, read by rows, given by [1,0,1,0,1,0,1,0,...] DELTA [0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A212363 Number A(n,k) of Dyck n-paths all of whose ascents and descents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A215576 G.f. satisfies A(x) = (1 + x^2)(1 + xA(x)^2).

A025242 Generalized Catalan numbers A(x)^2 -(1+x)^2A(x) +x(2+x+x^2) =0.

A180718 G.f.: exp( Sum_{n>=0} [ Sum_{k=0..n} C(n,k)^2x^k ]^2 x^n/n ).