A164965 -id:A164965 - cp's OEIS frontend

A106228 G.f. satisfies A(x) = 1 + xA(x)/(1 - xA(x)^2).

1, 1, 2, 6, 21, 80, 322, 1347, 5798, 25512, 114236, 518848, 2384538, 11068567, 51817118, 244370806, 1159883685, 5536508864, 26560581688, 127993221140, 619280193640, 3007251366000, 14651743202152, 71601107803904, 350873710447210, 1723795243004223

Offset: 0

Paul D. Hanna, May 19 2005

nonn

Number of paths from (0,0) to (3n-3,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and have no tripledescents (ddd). Example: a(3)=6 because we have udud, Uddud, udUdd, UddUdd, uudd and Ududd (the remaining four paths contain the string ddd: uUddd, UdUddd, Uuddd and UUdddd; see A027307). - Emeric Deutsch, Jun 08 2005
a(n) = number of node-labeled ordered trees (A000108) on n vertices, each node labeled with a positive integer <= its outdegree. A node is a non-root non-leaf vertex. Example. a(3)=6 counts the 5 ordered trees on 4 vertices with all labels 1 and the tree
.|.
/ \
with its (one and only) node labeled 2. - David Callan, Jul 14 2006
a(n) = number of Schroeder (n-1)-paths with no triple descents. Example: a(4)=21 counts all 22 Schroeder 3-paths (A006318) except UUUDDD. - David Callan, Jul 14 2006
(1 + 2x + 6x^2 + ...)*(1 + x + 2x^2 + 6x^3) = (1 + 3x + 10x^2 + 37x^3 + ...), where A109081 = (1, 1, 3, 10, 37, ...). - Gary W. Adamson, Nov 15 2011
a(n) = number of Motzkin paths of length 2n-1 with no downsteps in odd position. Example: a(3)=6 counts FFFFF, FFUDF, FUFDF, UDFFF, UDUDF, UFFDF with U an upstep (1,1), F a flatstep (1,0), and D a downstep (1,-1). - David Callan, May 20 2015
Number of permutations of length n that avoid 4123, 4132, and 4213. - Jay Pantone, Oct 01 2015
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j) and e(i) <= e(k). [Martinez and Savage, 2.21] - Eric M. Schmidt, Jul 17 2017
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>3, 1>4, 4>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the fourth element is larger than the second element. - Sergey Kitaev, Dec 10 2020
a(n) is the number of peakless Motzkin paths of length 2n that do not start with an up edge and where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on 2n vertices where the leftmost vertex is not matched and only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021

			A = 1 + x*A + x^2*A^3 + x^3*A^5 + x^4*A^7 + x^5*A^9 + ...
a(4) = 21 since the top row terms of Q^3 = (10, 7, 3, 1). - _Gary W. Adamson_, Nov 15 2011
G.f. = 1 + x + 2*x^2 + 6*x^3 + 21*x^4 + 80*x^5 + 322*x^6 + 1347*x^7 + ...

Jay Pantone, Table of n, a(n) for n = 0..500
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, and Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
N. R. Beaton, M. Bouvel, V. Guerrini, and S. Rinaldi, Slicings of Parallelogram Polyominoes: Catalan, Schröder, Baxter, and Other Sequences, Electr. J. Combin. 26 (2019), P3.13. Also at arXiv:1511.04854 [math.CO], 2015-2019.
Beáta Bényi, Toufik Mansour, and José L. Ramírez, Pattern Avoidance in Weak Ascent Sequences, arXiv:2309.06518 [math.CO], 2023.
Wlodzimierz Bryc, Raouf Fakhfakh, and Wojciech Mlotkowski, Cauchy-Stieltjes families with polynomial variance functions and generalized orthogonality, arXiv:1708.05343 [math.PR], 2017-2019. Also in Probability and Mathematical Statistics (2019), Vol. 39, No. 2, 237-258.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
David Callan and Toufik Mansour, Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 62-97.
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, Bijections on pattern avoiding inversion sequences and related objects, arXiv:2404.04091 [math.CO], 2024. See pp. 2, 22.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

Cf. A027907, A027307, A001006, A086246, A109081, A164965, A262441.

a := proc(n) option remember; if n<2 then 1 elif n=2 then 2 else ((380*n^3-840*n^2+496*n-72)*a(n-1)+(76*n^3-282*n^2+302*n-84)*a(n-2)+(57*n^3-297*n^2+402*n-72)*a(n-3))/(76*n^3-54*n^2-46*n) fi end: seq(a(i),i=0..23); # Peter Luschny, Aug 03 2012

Flatten[{1,Table[1/n*Sum[Binomial[n,k]*Binomial[n+k,n-k-1],{k,0,n-1}],{n,1,20}]}] (* Vaclav Kotesovec, Sep 16 2013 *)
a[ n_] := If[ n < 0, 0, HypergeometricPFQ[{-n, 1 - n, n + 1}, {1, 3/2}, 1/4]]; (* Michael Somos, May 27 2014 *)

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

{a(n) = local(A); if( n<0, 0, n++; A = (1 + x - sqrt(1 - 2*x - 3*x^2 + x * O(x^n))) / 2; polcoeff( serreverse( x^2 / A), n))}; /* Michael Somos, Jun 18 2005 */

{a(n) = if( n<1, n==0, polcoeff( serreverse( x /  (1 + 2*x + 2*x^2 + x^3) + x * O(x^n)), n))}; /* Michael Somos, Dec 31 2014 */

from mpmath import mp
mp.dps = 32; mp.pretty = True
def A106228(n) : return int(mp.hyper([-n, 1-n, n+1], [1, 3/2], 1/4))
[A106228(n) for n in (0..23)] # Peter Luschny, Aug 02 2012

G.f.: A(x) = (1/x)*series_reversion[x/(1 + x*G001006(x))] and thus G.f. satisfies: A(x) = 1 + x*A(x)*G001006(x*A(x)) where G001006(x) is the g.f. of Motzkin numbers A001006.
G.f.: 1 + x*exp( Sum_{n>=1} A082759(n)*x^n/n ), where A082759(n) = Sum_{k=0..n} binomial(n,k)*trinomial(n,k). - Paul D. Hanna, Nov 02 2012
a(n) = (1/n)sum(binomial(n, j+1)*b(n, j), j=0..n-1), where b(n, j) are the trinomial coefficients [b(n, j)=A027907(n, j)=coefficient of x^j in (1+x+x^2)^n]. - Emeric Deutsch, Jun 08 2005
Given g.f. A(x), then B(x) = x*A(x) satisfies 0 = f(x, B(x)) where f(x, y) = y^3 - (1+y)*x*(y-x). - Michael Somos, Jun 18 2005
a(n+1) = Sum[binomial(2n-2k,n-k)*binomial(n+k,n)/(n+1),{k,0,n}]. - David Callan, Aug 16 2006
For n>0: a(n) = 1/n*sum(binomial(n,j)*sum(binomial(j,i)*binomial(n-j,2*j-n-i-1)*2^(2*n-3*j+2*i+1),i=0..n-1), j=0..n); - Vladimir Kruchinin, Dec 26 2010
a(n) = 1/(n+1)*sum(binomial(n+1,k)*binomial(n+k+1,n-k),k,0,n); - Vladimir Kruchinin, Feb 28 2010
a(n) = upper left term in M^n, M = the production matrix:
  1, 1
  1, 1, 1
  2, 2, 1, 1
  3, 3, 2, 1, 1
  4, 4, 3, 2, 1, 1
  5, 5, 4, 3, 2, 1, 1
  ...
- Gary W. Adamson, Jul 08 2011
D-finite with recurrence: 4*n*(2*n+1)*a(n) + 2*(6-5*n-10*n^2)*a(n-1) + 12*(-9*n^2+35*n-33)*a(n-2) - 2*(n-3)*(13*n-28)*a(n-3) - 15*(n-3)*(n-4)*a(n-4) = 0. - R. J. Mathar, Nov 14 2011
From Gary W. Adamson, Nov 15 2011: (Start)
a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:
  1, 1, 0, 0, 0, ...
  2, 1, 1, 0, 0, ...
  3, 2, 1, 1, 0, ...
  4, 3, 2, 1, 1, ...
  5, 4, 3, 2, 1, ...
  ... (End)
a(n) = 3_F_2([-n, 1-n, n+1], [1, 3/2], 1/4). - Peter Luschny, Aug 02 2012
A four-term recurrence equation is given in the Maple program. Peter Luschny, Aug 03 2012
a(n) ~ 1/228*sqrt(114)*sqrt((32129+3933*sqrt(57))^(1/3) * ((32129+3933*sqrt(57))^(2/3) + 532 + 38*(32129+3933*sqrt(57))^(1/3))) / ((32129+3933*sqrt(57))^(1/3)) * (((1261+57*sqrt(57))^(2/3) + 112 + 10*(1261+57*sqrt(57))^(1/3)) / (6*(1261+57*sqrt(57))^(1/3)))^n / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 16 2013
G.f. satisfies x*F(x)^3 - x*F(x)^2 + (x-1)*F(x) + 1 = 0. - Jay Pantone, Oct 01 2015
G.f. satisfies A(-x*A(x)^3) = 1/A(x). - Alexander Burstein, Dec 05 2019
G.f.: A(x) = sqrt(B(x)) where B(x) is the g.f. of A262441. - Seiichi Manyama, Mar 31 2024
a(n) = Sum_{k=0..n} binomial(n,k) * binomial(n/2+3*k/2+1/2,n)/(n+3*k+1). - Seiichi Manyama, Apr 04 2024

A121988 Number of vertices of the n-th multiplihedron.

Original entry on oeis.org

0, 1, 2, 6, 21, 80, 322, 1348, 5814, 25674, 115566, 528528, 2449746, 11485068, 54377288, 259663576, 1249249981, 6049846848, 29469261934, 144293491564, 709806846980, 3506278661820, 17385618278700, 86500622296800, 431718990188850, 2160826237261692

Offset: 0

Jonathan Vos Post, Jun 24 2007

G.f. = x*c(x)*c(x*c(x)) where c(x) is the generating function of the Catalan numbers C(n). Thus a(n) is the Catalan transform of the sequence C(n-1). Reference for the definition of Catalan transform is the paper by Paul Barry. - Stefan Forcey (sforcey(AT)tnstate.edu), Aug 02 2007
A129442 is an essentially identical sequence. - R. J. Mathar, Jun 13 2008
From Peter Bala, Jan 27 2020: (Start)
This sequence is the main diagonal of the lower triangular array formed by putting the sequence [0, 1, 1, 2, 5, 14, 42, ...] of Catalan numbers (with 0 prepended) in the first column (k = 0) of the array and then completing the triangle using the relation T(n,k) = T(n-1,k) + T(n,k-1) for k >= 1.
    0
    1    1
    1    2    2
    2    4    6    6
    5    9   15   21   21
   14   23   38   59   80   80
  ...
Cf. A307495.
Alternatively, the sequence can be obtained by multiplying the sequence of Catalan numbers by the array A106566. (End)

			G.f. = x + 2*x^2 + 6*x^3 + 21*x^4 + 80*x^5 + 322*x^6 + 1348*x^7 + 5814*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..500
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004. See p. 19.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5, pp. 1-24.
David Callan, A combinatorial interpretation of the Catalan transform of the Catalan numbers, arXiv:1111.0996 [math.CO], 2011.
Stefan Forcey, Convex Hull Realizations of the Multiplihedra, Theorem 3.2, p. 8, arXiv:0706.3226 [math.AT], 2007-2008.
Stefan Forcey, Aaron Lauve, and Frank Sottile, New Hopf Structures on Binary Trees, dmtcs:2740 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009).
Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
Tian-Xiao He and Louis W. Shapiro, Row sums and alternating sums of Riordan arrays, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95.

Cf. A000108, A127632, A129442, A007317, A164965, A106566, A158826, A307495.

a:= proc(n) option remember; `if`(n<3, n, (14*(n-1)*(2*n-3)*a(n-1)
      -4*(4*n-9)*(4*n-7)*a(n-2))/ (3*n*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 20 2012

a[0] = 0; a[n_] := a[n] = (2 n - 2)!/((n - 1)! n!) + Sum[ a[i]*a[n - i], {i, n - 1}]; Table[ a@n, {n, 0, 24}] (* Robert G. Wilson v, Jun 28 2007 *)
a[ n_] := If[ n < 1, 0, SeriesCoefficient[ InverseSeries[ Series[ x - 2 x^2 + 2 x^3 - x^4, {x, 0, n}]], {x, 0, n}]]; (* Michael Somos, Jun 01 2014 *)
a[0] = 0; a[n_] := Binomial[2n-2, n-1]*Hypergeometric2F1[1/2, 1-n, 2-2n, 4] /n; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 31 2016 *)

{a(n) = if( n<1, 0, polcoeff( serreverse( x - 2*x^2 + 2*x^3 - x^4 + x * O(x^n)), n))}; /* Michael Somos, Jun 01 2014 */

a(0) = 0; a(n) = C(n-1) + Sum_{i=1..n-1} a(i)*a(n-i), where C(n) = A000108(n).
G.f.: (1-sqrt(2*sqrt(1-4x)-1))/2. a(n) = (1/n)*Sum_{k=1..n} binomial(2*n-k-1,n-1)*binomial(2k-2, k-1); a(0)=0. - Stefan Forcey (sforcey(AT)tnstate.edu), Aug 02 2007
a(n) = Sum_{k = 0..n} A106566(n,k)*A000108(k-1) with A000108(-1)=0. - Philippe Deléham, Aug 27 2007
From Vaclav Kotesovec, Oct 19 2012: (Start)
D-finite with recurrence 3*(n-1)*n*a(n) = 14*(n-1)*(2*n-3)*a(n-1) - 4*(4*n-9)*(4*n-7)*a(n-2).
a(n) ~ 2^(4*n-5/2)/(sqrt(Pi)*3^(n-1/2)*n^(3/2)). (End)
G.f.: A(x) satisfies A(x)=x*(1+A(x))/((1-A(x))*(1+A(x)^3)). - Vladimir Kruchinin, Jun 01 2014
G.f. is series reversion of (x - x^2) * (1 - x + x^2) = x - 2*x^2 + 2*x^3 - x^4. - Michael Somos, Jun 01 2014
From Peter Bala, Aug 22 2024: (Start)
G.f. A(x) = 1 - 1/c(x*c(x)), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
Sum_{n >= 1} a(n)*y^n = x*c(x), where y = x*(1 - x). (End)

More terms from Robert G. Wilson v, Jun 28 2007

A366034 G.f. A(x) satisfies A(x) = 1/(1 - x)^3 + x(1 - x)^3A(x)^3.

Original entry on oeis.org

1, 4, 15, 70, 405, 2676, 19075, 142562, 1100961, 8711968, 70257055, 575269278, 4769615773, 39961571228, 337805166747, 2877506096794, 24675158973081, 212835736433304, 1845348003175063, 16073746202176150, 140590118902532757, 1234285061013293716

Offset: 0

Seiichi Manyama, Oct 04 2023

nonn

Cf. A014140, A164965, A366215.

Cf. A366184.

a(n) = sum(k=0, n, binomial(n+2*k+2, n-k)*binomial(3*k, k)/(2*k+1));

a(n) = Sum_{k=0..n} binomial(n+2*k+2,n-k) * binomial(3*k,k)/(2*k+1).

A164925 Array, binomial(j-i,j), read by rising antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, -1, 0, 1, 1, -2, 0, 0, 1, 1, -3, 1, 0, 0, 1, 1, -4, 3, 0, 0, 0, 1, 1, -5, 6, -1, 0, 0, 0, 1, 1, -6, 10, -4, 0, 0, 0, 0, 1, 1, -7, 15, -10, 1, 0, 0, 0, 0, 1, 1, -8, 21, -20, 5, 0, 0, 0, 0, 0, 1, 1, -9, 28, -35, 15, -1, 0, 0, 0, 0, 0, 1, 1, -10, 36, -56, 35, -6, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Mark Dols, Aug 31 2009

Inverse of A052509, or A004070???

			Array, A(n, k), begins as:
  1,  1,  1,   1,  1,   1,  1,  1,  1, ...
  1,  0,  0,   0,  0,   0,  0,  0,  0, ...
  1, -1,  0,   0,  0,   0,  0,  0,  0, ...
  1, -2,  1,   0,  0,   0,  0,  0,  0, ...
  1, -3,  3,  -1,  0,   0,  0,  0,  0, ...
  1, -4,  6,  -4,  1,   0,  0,  0,  0, ...
  1, -5, 10, -10,  5,  -1,  0,  0,  0, ...
  1, -6, 15, -20, 15,  -6,  1,  0,  0, ...
  1, -7, 21, -35, 35, -21,  7, -1,  0, ...
Antidiagonal triangle, T(n, k), begins as:
  1;
  1,  1;
  1,  0,  1;
  1, -1,  0,  1;
  1, -2,  0,  0,  1;
  1, -3,  1,  0,  0,  1;
  1, -4,  3,  0,  0,  0,  1;
  1, -5,  6, -1,  0,  0,  0,  1;
  1, -6, 10, -4,  0,  0,  0,  0,  1;

G. C. Greubel, Antidiagonals n = 0..50, flattened

Cf. A004070, A008346, A010892, A052509, A052992.

Cf. A109466, A130595, A164899, A164915, A164965.

A164925:= func< n,k | k eq 0 or k eq n select 1 else Binomial(2*k-n,k) >;
[A164925(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Feb 10 2023

T[n_, k_]:= If[k==0 || k==n, 1, Binomial[2*k-n, k]];
Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Feb 10 2023 *)

{A(i, j) = if( i<0, 0, if(i==0 || j==0, 1, binomial(j-i, j)))}; /* Michael Somos, Jan 25 2012 */

def A164925(n,k): return 1 if (k==0 or k==n) else binomial(2*k-n, k)
flatten([[A164925(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Feb 10 2023

Sum_{k=0..n} T(n, k) = A164965(n). - Mark Dols, Sep 02 2009
From G. C. Greubel, Feb 10 2023: (Start)
A(n, k) = binomial(k-n, k), with A(0, k) = A(n, 0) = 1 (array).
T(n, k) = binomial(2*k-n, k), with T(n, 0) = T(n, n) = 1 (antidiagonal triangle).
Sum_{k=0..n} (-1)^k*T(n, k) = A008346(n).
Sum_{k=0..n} (-2)^k*T(n, k) = (-1)^n*A052992(n). (End)

Edited by Michael Somos, Jan 26 2012

Offset changed by G. C. Greubel, Feb 10 2023

cp's OEIS Frontend

A106228 G.f. satisfies A(x) = 1 + x*A(x)/(1 - x*A(x)^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A121988 Number of vertices of the n-th multiplihedron.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A366034 G.f. A(x) satisfies A(x) = 1/(1 - x)^3 + x*(1 - x)^3*A(x)^3.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A164925 Array, binomial(j-i,j), read by rising antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A115360 Period 6: repeat [1,-1,1,0,0,0].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A164976 Triangle read by rows, expansion of 1/(1-2*y*x-x+x^2-y*x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A144083 Triangle read by rows: partial sums from the right of an A010892 subsequences decrescendo triangle.

Views

Author

Keywords

A106228 G.f. satisfies A(x) = 1 + xA(x)/(1 - xA(x)^2).

A366034 G.f. A(x) satisfies A(x) = 1/(1 - x)^3 + x(1 - x)^3A(x)^3.

A164976 Triangle read by rows, expansion of 1/(1-2yx-x+x^2-y*x^2).

A366215 G.f. A(x) satisfies A(x) = 1/(1 - x)^4 + x(1 - x)^4A(x)^4.