A006318 -id:A006318 - cp's OEIS frontend

A079489 a(n) = (24^nbinomial(2n, n) - binomial(4n + 1, 2*n)) / (n + 1).

1, 3, 22, 211, 2306, 27230, 338444, 4362627, 57788170, 781825066, 10757497972, 150073096238, 2117778107732, 30176799215196, 433586825237912, 6274885068167651, 91383942213277530, 1338275570267001458, 19695358741104824036, 291137841642777382330, 4320734864185863437820

Offset: 0

N. J. A. Sloane, Jan 20 2003

a(n) is the number of ordered trees on 2n-1 edges in which every subtree of the root (including its rooting edge) has an even number of edges, except for the leftmost subtree which has an odd number of edges (including its rooting edge). - David Callan, Apr 10 2012
a(n) is the number of 2 X 2n Young tableaux with a wall between the first and second row in each even column. If there is a wall between two cells, the entries may be decreasing; see [Banderier, Wallner 2021].
  Example for a(1)=3:
   3 4  2 4  2 3
     -    -    -
   1 2, 1 3, 1 4. - Michael Wallner, Mar 09 2022

G. C. Greubel, Table of n, a(n) for n = 0..830
Cyril Banderier and Michael Wallner, Young Tableaux with Periodic Walls: Counting with the Density Method, Séminaire Lotharingien de Combinatoire, 85B (2021), Art. 47, 12 pp.
Feihu Liu and Guoce Xin, Simple Generating Functions for Certain Young Tableaux with Periodic Walls, arXiv:2401.14627 [math.CO], 2024.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table A.1).
Alon Regev, Enumerating triangulations by parallel diagonals, arXiv:1208.3915 [math.CO], 2012. - _N. J. A. Sloane_, Dec 25 2012
Alon Regev, Enumerating Triangulations by Parallel Diagonals, Journal of Integer Sequences, Vol. 15 (2012), #12.8.5.

Final diagonal of triangle in A078990.

Cf. A000108, A006318, A066357, A060941, A066357, A300386 - A300389, A333563.

a := n -> (2*4^n*binomial(2*n, n) - binomial(4*n + 1, 2*n)) / (n + 1):
seq(a(n), n = 0..20);  # Peter Luschny, Aug 26 2024

((Sqrt[2] Sqrt[1 + Sqrt[1 - 16 x]] - Sqrt[1 - 16 x] - 1)/(4 x) + O[x]^20)[[3]] (* Vladimir Reshetnikov, Sep 25 2016 *)
CoefficientList[Series[-(1 - Sqrt[1 - 4*Sqrt[x]])*(1 - Sqrt[1 + 4*Sqrt[x]])/(4*x), {x,0,50}], x] (* G. C. Greubel, Apr 13 2017 *)

a(n)=if(n<0,0,polcoeff(serreverse(x*(1-x^2)/(1+x^2)^2+O(x^(2*n+3))),2*n+1))

{a(n)=polcoeff(exp(sum(m=1,n,binomial(4*m-1,2*m)*x^m/m)+x*O(x^n)),n)} \\ Paul D. Hanna, Dec 30 2010

Series reversion of x(1-x^2)/(1+x^2)^2 expanded in odd powers of x. [Previous name.]
If x = y*(1-y^2)/(1+y^2)^2 then y = x + 3*x^3 + 22*x^5 + 211*x^7 + 2306*x^9 + ...
G.f. A(x) satisfies x*A(x^2) = (C(x) - C(-x))/(C(x) + C(-x)) where C(x) is g.f. of the Catalan numbers A000108.
a(n) = Sum_{k=0..2n} (-1)^k * A000108(2*n-k) * A000108(k). - David Callan, Aug 16 2006
a(n) = ((2^(4n+2))/Gamma(1/2)) * ((Gamma(n+1/2)/(2*Gamma(n+2))) - Gamma(2n+3/2)/Gamma(2n+3)). [David Dickson (dcmd(AT)unimelb.edu.au), Nov 10 2009]
G.f.: exp( Sum_{n>=1} C(4n-1,2n)*x^n/n ). - Paul D. Hanna, Dec 30 2010
G.f.: C(sqrt(x))*C(-sqrt(x)) where C(x) is the g.f. for the Catalan numbers A000108. - David Callan, Apr 10 2012
D-finite with recurrence n*(n+1)*(2*n+1)*a(n) -2*n*(32*n^2-32*n+11)*a(n-1) +16*(4*n-5)*(4*n-3)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Nov 29 2012
a(n) ~ (2-sqrt(2))*16^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 20 2013
a(n) = 2^(2*n+1)*Catalan(n) - Catalan(2*n+1) (see Regev). It follows that the 2-adic valuations of a(n) and Catalan(n) are equal. In particular, a(n) is odd iff n is of the form 2^m - 1. - Peter Bala, Aug 02 2016
G.f.: (sqrt(2) * sqrt(1 + sqrt(1-16*x)) - sqrt(1-16*x) - 1)/(4*x). - Vladimir Reshetnikov, Sep 25 2016
G.f. A(x) satisfies A(x^2) = C(x)^2*r(-x*C(x)^2), where C(x) is g.f. of the Catalan numbers A000108, and r(x) is g.f. of the large Schröder numbers A006318. - Alexander Burstein, Nov 21 2019
From Peter Bala, Sep 14 2021: (Start)
A(x) = exp( Sum_{n >= 1} (1/2)*binomial(4*n,2*n)*x^n/n ).
1 + x*A(x) is the o.g.f. of A066357.
The sequence defined by b(n) := [x^n] A(x)^n begins [1, 3, 53, 1056, 22181, 480003, 10588508, 236720424, ...]  and satisfies the congruence b(p) == b(1) (mod p^3) for prime p >= 3. See A333563. Cf. A060941. (End)
From Peter Bala, Oct 23 2024: (Start)
For integer r and positive integer s, define a sequence {u(n) : n >= 0} by setting u(n) = [x^(s*n)] A(x)^(r*n). We conjecture that the supercongruence u(n*p^k) == u(n*p^(k-1)) (mod p^(3*k)) holds for all primes p >= 5 and for all positive integers n and k.
Let B(x) = 1/x * series_reversion(x*A(x)). Define a sequence {v(n) : n >= 0} by setting v(n) = [x^(s*n)] B(x)^(r*n). We conjecture that the supercongruence v(n*p^k) == v(n*p^(k-1)) (mod p^(3*k)) holds for all primes p >= 5 and for all positive integers n and k. (End)

New name by Peter Luschny, Aug 26 2024

A112478 Expansion of (1 + x + sqrt(1 + 6*x + x^2))/2.

Original entry on oeis.org

1, 2, -2, 6, -22, 90, -394, 1806, -8558, 41586, -206098, 1037718, -5293446, 27297738, -142078746, 745387038, -3937603038, 20927156706, -111818026018, 600318853926, -3236724317174, 17518619320890, -95149655201962, 518431875418926, -2832923350929742, 15521467648875090

Offset: 0

Paul Barry, Sep 07 2005

This is the A-sequence for the Delannoy triangle A008288. See the W. Lang link under A006232 for Sheffer a- and z-sequences where also Riordan A- and Z-sequences are explained. O.g.f. A(y) = y/Finv(y) = 2*y/(-(1 + y) + sqrt(y^2 + 6*y + 1)) = ((1 + y) + sqrt(1 + 6*y + y^2))/2 with Finv the inverse function of F(x) = x*(1 + x)/(1 - x). The o.g.f. of the Z-sequence is 1.

			G.f. = 1 + 2*x - 2*x^2 + 6*x^3 - 22*x^4 + 90*x^5 - 394*x^6 + 1806*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200

A minor variation of A006318. See A085403 for yet another version.
Row sums of number triangle A112477.
Cf. A364393, A364407, A364408, A364409, A366266, A366267, A366268.
Cf. A366325.

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

{a(n) = polcoeff((1 + x + sqrt(1 + 6*x + x^2 + x*O(x^n)))/2, n)}; /* Michael Somos, Jul 07 2020 */

G.f.: (1 + x + sqrt(1 + 6*x + x^2))/2. - Sergei N. Gladkovskii, Jan 04 2012
G.F.: G(0) where G(k)= 1 + x + x/G(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Jan 04 2012
D-finite with recurrence: n*a(n) + 3*(2*n-3)*a(n-1) + (n-3)*a(n-2) = 0. - R. J. Mathar, Nov 24 2012
a(n) ~ (-1)^(n+1) * sqrt(3*sqrt(2) - 4) * (3 + 2*sqrt(2))^n / (2 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014
0 = a(n)*(a(n+1) + 15*a(n+2) + 4*a(n+3)) + a(n+1)*(-3*a(n+1) + 34*a(n+3) + 15*a(n+3)) + a(n+2)*(-3*a(n+2) + a(n+3)) for all integer n > 0. - Michael Somos, Jul 07 2020
From Seiichi Manyama, Oct 08 2023: (Start)
G.f. satisfies A(x) = 1 + x + x/A(x).
a(n) = (-1)^(n-1) * Sum_{k=0..n} binomial(2*k-1,k) * binomial(n+k-2,n-k)/(2*k-1). (End)

A003516 Binomial coefficients C(2n+1, n-2).

Original entry on oeis.org

1, 7, 36, 165, 715, 3003, 12376, 50388, 203490, 817190, 3268760, 13037895, 51895935, 206253075, 818809200, 3247943160, 12875774670, 51021117810, 202112640600, 800472431850, 3169870830126, 12551759587422

Offset: 2

N. J. A. Sloane

a(n) is the number of royal paths (A006318) from (0,0) to (n,n) with exactly one diagonal step off the line y=x. - David Callan, Mar 25 2004

a(n) is the total number of DDUU's in all Dyck (n+2)-paths. - David Scambler, May 03 2013

			For n=4, C(2*4+1,4-2) = C(9,2) = 9*8/2 = 36, so a(4) = 36. - _Michael B. Porter_, Sep 10 2016

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 2..1000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Heidi Goodson, An Identity for Vertically Aligned Entries in Pascal's Triangle, arXiv:1901.08653 [math.CO], 2019.
Milan Janjic, Two Enumerative Functions.
Toufik Mansour and Mark Shattuck, Counting occurrences of subword patterns in non-crossing partitions, Art Disc. Appl. Math. (2022).
Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.3. - From _N. J. A. Sloane_, Sep 16 2012
Daniel W. Stasiuk, An Enumeration Problem for Sequences of n-ary Trees Arising from Algebraic Operads, Master's Thesis, University of Saskatchewan-Saskatoon (2018).

Diagonal 6 of triangle A100257.
Third unsigned column (s=2) of A113187. - Wolfdieter Lang, Oct 18 2012
Cf. triangle A114492 - Dyck paths with k DDUU's.
Cf. A001622, A115139.
Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002054 (m = 3), A002694 (m = 4), A002696 (m = 6), A030053 - A030056, A004310 - A004318.

List([2..25], n-> Binomial(2*n+1, n-2)); # G. C. Greubel, Mar 21 2019

[Binomial(2*n+1,n-2): n in [2..25]]; // Vincenzo Librandi, Apr 13 2011

CoefficientList[ Series[ 32/(((Sqrt[1 - 4 x] + 1)^5)*Sqrt[1 - 4 x]), {x, 0, 25}], x] (* Robert G. Wilson v, Aug 08 2011 *)
Table[Binomial[2*n +1,n-2], {n,2,25}] (* G. C. Greubel, Jan 23 2017 *)

{a(n) = binomial(2*n+1, n-2)}; \\ G. C. Greubel, Mar 21 2019

[binomial(2*n+1, n-2) for n in (2..25)] # G. C. Greubel, Mar 21 2019

G.f.: 32*x^2/(sqrt(1-4*x)*(sqrt(1-4*x)+1)^5). - Marco A. Cisneros Guevara, Jul 18 2011
a(n) = Sum_{k=0..n-2} binomial(n+k+2,k). - Arkadiusz Wesolowski, Apr 02 2012
D-finite with recurrence (n+3)*(n-2)*a(n) = 2*n*(2*n+1)*a(n-1). - R. J. Mathar, Oct 13 2012
G.f.: x^2*c(x)^5/sqrt(1-4*x) = ((-1 + 2*x) + (1 - 3*x + x^2) * c(x))/(x^2*sqrt(1-4*x)), with c(x) the o.g.f. of the Catalan numbers A000108. See the W. Lang link under A115139 for powers of c. - Wolfdieter Lang, Sep 10 2016
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). - Ilya Gutkovskiy, Sep 10 2016
From Amiram Eldar, Jan 24 2022: (Start)
Sum_{n>=2} 1/a(n) = 4 - 14*Pi/(9*sqrt(3)).
Sum_{n>=2} (-1)^n/a(n) = 228*log(phi)/(5*sqrt(5)) - 134/15, where phi is the golden ratio (A001622). (End)
G.f.: 2F1([7/2,3],[6],4*x). - Karol A. Penson, Apr 24 2024
a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x^2 - 5*x + 5)/sqrt(4 - x). - Peter Bala, Oct 13 2024

A349310 G.f. A(x) satisfies: A(x) = (1 + x * A(x)^4) / (1 - x).

Original entry on oeis.org

1, 2, 10, 74, 642, 6082, 60970, 635818, 6826690, 74958914, 837833482, 9500939978, 109037364930, 1264049402754, 14780619799722, 174121322204074, 2064572904600706, 24620095821589378, 295087003429677322, 3552841638851183690, 42950428996378731010

Offset: 0

Ilya Gutkovskiy, Nov 14 2021

nonn

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

Cf. A002293, A006318, A346626, A346646, A349311, A349312, A349313, A349314.

nmax = 20; A[] = 0; Do[A[x] = (1 + x A[x]^4)/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
Table[Sum[Binomial[n + 3 k, 4 k] Binomial[4 k, k]/(3 k + 1), {k, 0, n}], {n, 0, 20}]

a(n) = Sum_{k=0..n} binomial(n+3*k,4*k) * binomial(4*k,k) / (3*k+1).
a(n) = F([(1+n)/3, (2+n)/3, (3+n)/3, -n], [2/3, 1, 4/3], -1), where F is the generalized hypergeometric function. - Stefano Spezia, Nov 14 2021
a(n) ~ sqrt(1 + 3*r) / (2^(13/6) * sqrt(3*Pi) * (1-r)^(1/6) * n^(3/2) * r^(n + 1/3)), where r = 0.0766602099042102089064087954661556186872273232742446843... is the smallest real root of the equation 3^3 * (1-r)^4 = 4^4 * r. - Vaclav Kotesovec, Nov 15 2021

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

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 13, 26, 52, 104, 212, 438, 910, 1903, 4009, 8494, 18080, 38656, 82988, 178802, 386490, 837928, 1821664, 3970282, 8673258, 18987930, 41652382, 91539466, 201525238, 444379907, 981384125, 2170416738, 4806513660

Offset: 0

Olivier Gérard

Essentially the same as A025246.
Number of lattice paths in the first quadrant from (0,0) to (n,0) using only steps H=(1,0), U=(1,1) and D=(2,-1). E.g. a(5)=7 because we have HHHHH, HHUD, HUDH, HUHD, UDHH, UHDH and UHHD. - Emeric Deutsch, Dec 25 2003
Also number of peakless Motzkin paths of length n with no double rises; in other words, Motzkin paths of length n with no UD's and no UU's, where U=(1,1) and D=(1,-1). E.g. a(5)=7 because we have HHHHH, HHUHD, HUHDH, HUHHD, UHDHH, UHHDH and UHHHD, where H=(1,0). - Emeric Deutsch, Jan 09 2004
Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos, Jul 13 2003
Hankel transform is A010892(n+1). [From Paul Barry, Sep 19 2008]
Number of FU_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. This also works for U_{k}F-equivalence classes. - Sergey Kirgizov, Apr 08 2018

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 13*x^6 + 26*x^7 + 52*x^8 + 104*x^9 + ...

Reinhard Zumkeller, 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, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Paul Barry, Elliptic Curves, Riordan arrays and Lattice Paths, arXiv:2507.16765 [math.CO], 2025. See p. 16.
Johann Cigler, Some nice Hankel determinants, arXiv preprint arXiv:1109.1449 [math.CO], 2011.
Shalosh B. Ekhad and Mingjia Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 666
Feihu Liu, Ying Wang, Yingrui Zhang, and Zihao Zhang, Hankel Determinants for Convolution of Power Series: An Extension of Cigler's Results, arXiv:2503.17187 [math.CO], 2025. See p. 9.
K. Park and G.-S. Cheon, Lattice path counting with a bounded strip restriction
Helmut Prodinger, Motzkin paths of bounded height with two forbidden contiguous subwords of length two, arXiv:2310.12497 [math.CO], 2023.

Cf. A000108, A001006, A004148, A006318, A025246.

Cf. A014137, A090344, A144700.

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

[(&+[Binomial(n-k, 2*k)*Catalan(k): k in [0..Floor(n/3)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022

a := n -> hypergeom([1/3 - n/3, 2/3 - n/3, -n/3], [2, -n], 27):
seq(simplify(a(n)), n = 0..32); # Peter Luschny, Jun 15 2022

a[0]=1; a[n_]:= a[n]= a[n-1] + Sum[a[k]*a[n-3-k], {k, 0, n-3}];
Table[a[n], {n,0,40}]

{a(n) = polcoeff( (1 - x - sqrt((1-x)^2 - 4*x^3 + x^4 * O(x^n))) / 2, n+3)}; /* Michael Somos, Jul 13 2003 */

[sum(binomial(n-k,2*k)*catalan_number(k) for k in (0..(n//3))) for n in (0..40)] # G. C. Greubel, Jun 15 2022

G.f.: (1 - x - sqrt((1-x)^2 - 4*x^3)) / (2*x^3) = A(x). y = x * A(x) satisfies 0 = x - y + x*y + (x*y)^2. - Michael Somos, Jul 13 2003
a(n+1) = a(n) + a(0)*a(n-2) + a(1)*a(n-3) + ... + a(n-2)*a(0). - Michael Somos, Jul 13 2003
a(n) = A025246(n+3). - Michael Somos, Jan 20 2004
G.f.: (1/(1-x))*c(x^3/(1-x)^2), c(x) the g.f. of A000108. - From Paul Barry, Sep 19 2008
From Paul Barry, May 22 2009: (Start)
G.f.: 1/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-... (continued fraction).
a(n) = Sum_{k=0..floor(n/3)} binomial(n-k, 2*k)*A000108(k). (End)
(n+3)*a(n) = (2*n+3)*a(n-1) - n*a(n-2) + 2*(2*n-3)*a(n-3). - R. J. Mathar, Nov 26 2012
0 = a(n)*(16*a(n+1) - 10*a(n+2) + 32*a(n+3) - 22*a(n+4)) + a(n+1)*(2*a(n+1) - 15*a(n+2) + 9*a(n+3) + 4*a(n+4)) + a(n+2)*(a(n+2) + 2*a(n+3) - 5*a(n+4)) + a(n+3)*(a(n+3) + a(n+4)) if n>=0. - Michael Somos, Jan 30 2014
a(n) ~ (8 + 12*r^2 + 5*r) * sqrt(r^2 - 4*r + 3) / (4 * sqrt(Pi) * n^(3/2) * r^n), where r = 0.432040800333095789... is the real root of the equation -1 + 2*r - r^2 + 4*r^3 = 0. - Vaclav Kotesovec, Jun 15 2022
a(n) = hypergeom([(1 - n)/3, (2 - n)/3, -n/3], [2, -n], 27). - Peter Luschny, Jun 15 2022

A349311 G.f. A(x) satisfies: A(x) = (1 + x * A(x)^5) / (1 - x).

Original entry on oeis.org

1, 2, 12, 112, 1232, 14832, 189184, 2512064, 34358784, 480745984, 6848734464, 99003237376, 1448575666176, 21411827808256, 319255531155456, 4796005997940736, 72520546008219648, 1102912584949792768, 16859182461720526848, 258886644574700699648

Offset: 0

Ilya Gutkovskiy, Nov 14 2021

nonn

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

Cf. A002294, A006318, A346626, A346647, A349310, A349312, A349313, A349314.

nmax = 19; A[] = 0; Do[A[x] = (1 + x A[x]^5)/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
Table[Sum[Binomial[n + 4 k, 5 k] Binomial[5 k, k]/(4 k + 1), {k, 0, n}], {n, 0, 19}]

a(n) = Sum_{k=0..n} binomial(n+4*k,5*k) * binomial(5*k,k) / (4*k+1).
a(n) = F([(1+n)/4, (2+n)/4, (3+n)/4, (4+n)/4, -n], [1/2, 3/4, 1, 5/4], -1), where F is the generalized hypergeometric function. - Stefano Spezia, Nov 14 2021
a(n) ~ sqrt(1 + 4*r) / (2 * 5^(3/4) * sqrt(2*Pi) * (1-r)^(1/4) * n^(3/2) * r^(n + 1/4)), where r = 0.0600920016324256496641829206872407657377702010870270617... is the real root of the equation 4^4 * (1-r)^5 = 5^5 * r. - Vaclav Kotesovec, Nov 15 2021

A010683 Let S(x,y) = number of lattice paths from (0,0) to (x,y) that use the step set { (0,1), (1,0), (2,0), (3,0), ...} and never pass below y = x. Sequence gives S(n-1,n) = number of 'Schröder' trees with n+1 leaves and root of degree 2.

Original entry on oeis.org

1, 2, 7, 28, 121, 550, 2591, 12536, 61921, 310954, 1582791, 8147796, 42344121, 221866446, 1170747519, 6216189936, 33186295681, 178034219986, 959260792775, 5188835909516, 28167068630713, 153395382655222

Offset: 0

Robert Sulanke (sulanke(AT)diamond.idbsu.edu), N. J. A. Sloane

a(n) is the number of compound propositions "on the negative side" that can be made from n simple propositions.
Convolution of A001003 (the little Schröder numbers) with itself. - Emeric Deutsch, Dec 27 2003
Number of dissections of a convex polygon with n+3 sides that have a triangle over a fixed side (the base) of the polygon. - Emeric Deutsch, Dec 27 2003
a(n-1) = number of royal paths from (0,0) to (n,n), A006318, with exactly one diagonal step on the line y=x. - David Callan, Mar 14 2004
Number of short bushes (i.e., ordered trees with no vertices of outdegree 1) with n+2 leaves and having root of degree 2. Example: a(2)=7 because, in addition to the five binary trees with 6 edges (they do have 4 leaves) we have (i) two edges rb, rc hanging from the root r with three edges hanging from vertex b and (ii) two edges rb, rc hanging from the root r with three edges hanging from vertex c. - Emeric Deutsch, Mar 16 2004
The a(n) equal the Fi2 sums, see A180662, of Schröder triangle A033877. - Johannes W. Meijer, Mar 26 2012
Row sums of A144944 and of A186826. - Reinhard Zumkeller, May 11 2013

T. D. Noe, Table of n, a(n) for n=0..200
A. Bacher, Directed and multi-directed animals on the square lattice with next nearest neighbor edges, arXiv preprint arXiv:1301.1365 [math.CO], 2013-2015. See R(t).
D. Birmajer, J. B. Gil, and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
Kevin Brown, Hipparchus on Compound Statements, 1994-2010.
Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, Pattern-avoiding Cayley permutations via combinatorial species, arXiv:2407.19583 [math.CO], 2024.
Shishuo Fu, Zhicong Lin, and Yaling Wang, Refined Wilf-equivalences by Comtet statistics, arXiv:2009.04269 [math.CO], 2020.
Laurent Habsieger, Maxim Kazarian and Sergei Lando, On the second number of Plutarch, Am. Math. Monthly, Vol. 105, No. 5 (May, 1998), p. 446.
H. Kwong, On recurrences of Fahr and Ringel: An Alternate Approach, Fib. Quart., 48 (2010), 363-365; see p. 364.
J. W. Meijer, Famous numbers on a chessboard, Acta Nova, Volume 4, No.4, December 2010. pp. 589-598.
E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
D. G. Rogers and L. W. Shapiro, Deques, trees and lattice paths, in Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference. Lecture Notes in Mathematics, Vol. 884 (Springer, Berlin, 1981), pp. 293-303. Math. Rev., 83g, 05038; Zentralblatt, 469(1982), 05005. See Figs. 7a and 8b.
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
Index entries for sequences related to trees

Cf. A001003, A006318, A033877, A144944, A180662, A186826.
Second right-hand column of triangle A011117.
A177010 has a closely-related g.f..

a010683 = sum . a144944_row  -- Reinhard Zumkeller, May 11 2013

[n le 2 select n else (6*(2*(n-1)^2-1)*Self(n-1) - (n-3)*(2*n-1)*Self(n-2))/((n+1)*(2*n-3)): n in [1..30]]; // G. C. Greubel, Mar 11 2023

a := proc(n) local k: if n=0 then 1 else (2/n)*add(binomial(n, k)* binomial(n+k+1, k-1), k=1..n) fi: end:
seq(a(n), n=0..21); # Johannes W. Meijer, Mar 26 2012, revised Mar 31 2015

f[ x_, y_ ]:= f[ x, y ]= Module[ {return}, If[x==0, return =1, If[y==x-1, return =0, return= f[x,y-1] + Sum[f[k, y], {k,0,x-1} ]]]; return];
(* Do[Print[Table[f[ k, j ], {k, 0, j}]], {j, 10, 0, -1}] *)
Table[f[x, x+1], {x,0,21}]
(* Second program: *)
a[n_] := 2*Hypergeometric2F1[1-n, n+3, 2, -1]; a[0]=1;
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Dec 09 2014, after Wolfdieter Lang *)

x='x+O('x^100); Vec(((1-x)^2-(1+x)*sqrt(1-6*x+x^2))/(8*x^2)) \\ Altug Alkan, Dec 19 2015

a = lambda n: (n+1)*hypergeometric([1-n, -n], [3], 2)
[simplify(a(n)) for n in range(22)] # Peter Luschny, Nov 19 2014

G.f.: ((1-t)^2-(1+t)*sqrt(1-6*t+t^2))/(8*t^2) = A(t)^2, with o.g.f. A(t) of A001003.
From Wolfdieter Lang, Sep 12 2005: (Start)
a(n) = (2/n)*Sum_{k=1..n} binomial(n, k)*binomial(n+k+1, k-1).
a(n) = 2*hypergeometric2F1([1-n, n+3], [2], -1), n>=1. a(0)=1. (End)
a(n) = ((2*n+1)*LegendreP(n+1,3) - (2*n+3)*LegendreP(n,3)) / (4*n*(n+2)) for n>0. - Mark van Hoeij, Jul 02 2010
From Gary W. Adamson, Jul 08 2011: (Start)
Let M = the production matrix:
  1, 2, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, ...
  1, 2, 1, 2, 0, 0, ...
  1, 2, 1, 2, 1, 0, ...
  1, 2, 1, 2, 1, 2, ...
  ...
a(n) is the upper entry in the vector (M(T))^n * [1,0,0,0,...]; where T is the transpose operation. (End)
D-finite with recurrence: (n+2)*(2*n-1)*a(n) = 6*(2*n^2-1)*a(n-1) - (n-2)*(2*n+1)*a(n-2). - Vaclav Kotesovec, Oct 07 2012
a(n) ~ sqrt(48+34*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 07 2012
Recurrence (an alternative): (n+2)*a(n) = (4-n)*a(n-4) + 2*(2*n-5)*a(n-3) + 10*(n-1)*a(n-2) + 2*(2*n+1)*a(n-1), n >= 4. - Fung Lam, Feb 18 2014
a(n) = (n+1)*hypergeometric2F1([1-n, -n], [3], 2). - Peter Luschny, Nov 19 2014
a(n) = (A001003(n) + A001003(n+1))/2 = sum(A001003(k) * A001003(n-k), k=0..n). - Johannes W. Meijer, Apr 29 2015

Minor edits by Johannes W. Meijer, Mar 26 2012

A026376 a(n) is the number of integer strings s(0),...,s(n) counted by array T in A026374 that have s(n)=2; also a(n) = T(2n,n-1).

Original entry on oeis.org

1, 6, 30, 144, 685, 3258, 15533, 74280, 356283, 1713690, 8263596, 39938616, 193419915, 938430990, 4560542550, 22195961280, 108171753355, 527816696850, 2578310320610, 12607504827600, 61706212037295, 302275142049870, 1481908332595625, 7270432009471224

Offset: 1

Clark Kimberling

nonn

Number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1) and H=(2,0) and never going below the x-axis) from (0,0) to (2n+2,0), with exactly one peak at an even level. E.g., a(2)=6 because we have UUDDH, HUUDD, UDUUDD, UUDDUD, UUDHD and UHUDD. - Emeric Deutsch, Dec 28 2003
Number of left steps in all skew Dyck paths of semilength n+1. A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. Example: a(2)=6 because in the 10 (=A002212(3)) skew Dyck paths of semilength 3 ( namely UDUUDL, UUUDLD, UUDUDL, UUUDDL, UUUDLL and five Dyck paths that have no left steps) we have altogether 6 left steps. - Emeric Deutsch, Aug 05 2007
From Gary W. Adamson, May 17 2009: (Start)
Equals A026378 (1, 4, 17, 75, ...) convolved with A007317 (1, 2, 5, 15, 51, ...).
Equals A081671 (1, 3, 11, 45, ...) convolved with A002212 (1, 3, 10, 36, 137, ...).
(End)

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 18.
Toufik Mansour and José Luis Ramírez, Enumeration of Fuss-skew paths, Ann. Math. Inform. (2022) Vol. 55, 125-136. See p. 129.

Cf. A006318, A002212, A081671, A007317, A026378.

a := n -> simplify(GegenbauerC(n-1, -n, -3/2)):
seq(a(n), n=1..24); # Peter Luschny, May 09 2016

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

a(n)=if(n<0,0,polcoeff((1+3*x+x^2)^n,n-1))

A026376 = lambda n : n*hypergeometric([1, 3/2, 1-n], [1, 3], -4)
[round(A026376(n).n(100)) for n in (1..24)] # Peter Luschny, Sep 16 2014

# Recurrence:
def A026376():
    x, y, n = 1, 1, 1
    while True:
        x, y = y, ((6*n + 3)*y - (5*n - 5)*x) / (n + 2)
        yield n*x
        n += 1
a = A026376()
[next(a) for i in (1..24)] # Peter Luschny, Sep 16 2014

E.g.f.: exp(3x)*I_1(2x), where I_1 is Bessel function. - Michael Somos, Sep 09 2002
G.f.: (1 - 3*z - t)/(2*z*t) where t = sqrt(1-6*z+5*z^2). - Emeric Deutsch, May 25 2003
a(n) = [t^(n+1)](1+3t+t^2)^n. a := n -> Sum_{j=ceiling((n+1)/2)..n} 3^(2j-n-1)*binomial(n, j)*binomial(j, n+1-j). - Emeric Deutsch, Jan 30 2004
a(n) = Sum_{k=0..n} binomial(n, k)*binomial(2k, k+1). - Paul Barry, Sep 20 2004
a(n) = n*A002212(n). - Emeric Deutsch, Aug 05 2007
D-finite with recurrence (n+1)*a(n) - 9*n*a(n-1) + (23*n-27)*a(n-2) + 15*(-n+2)*a(n-3) = 0. - R. J. Mathar, Dec 02 2012
a(n) ~ 5^(n+1/2) / (2*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 13 2014
a(n) = n*hypergeometric([1, 3/2, 1-n],[1, 3],-4). - Peter Luschny, Sep 16 2014
a(n) = GegenbauerC(n-1, -n, -3/2). - Peter Luschny, May 09 2016

A098593 A triangle of Krawtchouk coefficients.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, -1, -1, 1, 1, -2, -2, -2, 1, 1, -3, -2, -2, -3, 1, 1, -4, -1, 0, -1, -4, 1, 1, -5, 1, 3, 3, 1, -5, 1, 1, -6, 4, 6, 6, 6, 4, -6, 1, 1, -7, 8, 8, 6, 6, 8, 8, -7, 1, 1, -8, 13, 8, 2, 0, 2, 8, 13, -8, 1, 1, -9, 19, 5, -6, -10, -10, -6, 5, 19, -9, 1, 1, -10, 26, -2, -17, -20, -20, -20, -17, -2, 26, -10, 1, 1, -11, 34, -14, -29, -25

Offset: 0

Paul Barry, Sep 17 2004

Row sums are A009545(n+1), with e.g.f. exp(x)(cos(x)+sin(x)). Diagonal sums are A077948.
The rows are the diagonals of the Krawtchouk matrices. Coincides with the Riordan array (1/(1-x),(1-2x)/(1-x)). - Paul Barry, Sep 24 2004
Corresponds to Pascal-(1,-2,1) array, read by antidiagonals. The Pascal-(1,-2,1) array has n-th row generated by (1-2x)^n/(1-x)^(n+1). - Paul Barry, Sep 24 2004
A modified version (different signs) of this triangle is given by T(n,k) = Sum_{j=0..n} C(n-k,j)*C(k,j)*cos(Pi*(k-j)). - Paul Barry, Jun 14 2007

			Rows begin {1}, {1,1}, {1,0,1}, {1,-1,-1,1}, {1,-2,-2,-2,1}, ...
From _Paul Barry_, Oct 05 2010: (Start)
Triangle begins
  1,
  1,  1,
  1,  0,  1,
  1, -1, -1,  1,
  1, -2, -2, -2,  1,
  1, -3, -2, -2, -3,  1,
  1, -4, -1,  0, -1, -4,  1,
  1, -5,  1,  3,  3,  1, -5,  1,
  1, -6,  4,  6,  6,  6,  4, -6,  1,
  1, -7,  8,  8,  6,  6,  8,  8, -7,  1,
  1, -8, 13,  8,  2,  0,  2,  8, 13, -8,  1
Production matrix (related to large Schroeder numbers A006318) begins
  1,     1,
  0,    -1,     1,
  0,    -2,    -1,    1,
  0,    -6,    -2,   -1,   1,
  0,   -22,    -6,   -2,  -1,   1,
  0,   -90,   -22,   -6,  -2,  -1,  1,
  0,  -394,   -90,  -22,  -6,  -2, -1,  1,
  0, -1806,  -394,  -90, -22,  -6, -2, -1,  1,
  0, -8558, -1806, -394, -90, -22, -6, -2, -1, 1
Production matrix of inverse is
    -1,   1,
    -2,   1,  1,
    -4,   2,  1,  1,
    -8,   4,  2,  1,  1,
   -16,   8,  4,  2,  1, 1,
   -32,  16,  8,  4,  2, 1, 1,
   -64,  32, 16,  8,  4, 2, 1, 1,
  -128,  64, 32, 16,  8, 4, 2, 1, 1,
  -256, 128, 64, 32, 16, 8, 4, 2, 1, 1 (End)

P. Feinsilver and J. Kocik, Krawtchouk matrices from classical and quantum walks, Contemporary Mathematics, 287 2001, pp. 83-96.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Paul Barry, A note on Krawtchouk Polynomials and Riordan Arrays, JIS 11 (2008) 08.2.2
P. Feinsilver and J. Kocik, Krawtchouk polynomials and Krawtchouk matrices, arxiv:quant-ph/0702073, 2007.

Cf. Pascal (1,m,1) array: A123562 (m = -3), A000012 (m = -1), A007318 (m = 0), A008288 (m = 1), A081577 (m = 2), A081578 (m = 3), A081579 (m = 4), A081580 (m = 5), A081581 (m = 6), A081582 (m = 7), A143683 (m = 8).

T[n_, k_] := Sum[Binomial[n - k, k - j]*Binomial[k, j]*(-1)^(k - j), {j, 0, n}]; Table[T[n, k], {n, 0, 49}, {k, 0, n}] // Flatten (* G. C. Greubel, Oct 15 2017 *)

for(n=0,10, for(k=0,n, print1(sum(i=0,k, binomial(n-k, k-i) *binomial(k, i)*(-1)^(k-i)), ", "))) \\ G. C. Greubel, Oct 15 2017

T(n, k) = Sum_{i=0..k} binomial(n-k, k-i)*binomial(k, i)*(-1)^(k-i), k<=n.
T(n, k) = T(n-1, k) + T(n-1, k-1) - 2*T(n-2, k-1) (n>0). - Paul Barry, Sep 24 2004
T(n, k) = [k<=n]*Hypergeometric2F1(-k,k-n;1;-1). - Paul Barry, Jan 24 2011
E.g.f. for the n-th subdiagonal: exp(x)*P(n,x), where P(n,x) is the polynomial Sum_{k = 0..n} (-1)^k*binomial(n,k)* x^k/k!. For example, the e.g.f. for the second subdiagonal is exp(x)*(1 - 2*x + x^2/2) = 1 - x - 2*x^2/2! - 2*x^3/3! - x^4/4! + x^5/5! + .... - Peter Bala, Mar 05 2017

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

Original entry on oeis.org

1, 2, 12, 100, 968, 10208, 113792, 1318832, 15732064, 191878592, 2381917824, 29995598208, 382257383168, 4920505410816, 63882881030656, 835554927932160, 10999486798112256, 145626782310460416, 1937772463214168064, 25901381584638605312, 347618773649248088064

Offset: 0

Paul D. Hanna, Nov 21 2012

nonn

			G.f.: A(x) = 1 + 2*x + 12*x^2 + 100*x^3 + 968*x^4 + 10208*x^5 +...
Related expansions:
A(x)^2 = 1 + 4*x + 28*x^2 + 248*x^3 + 2480*x^4 + 26688*x^5 +...
A(x)^4 = 1 + 8*x + 72*x^2 + 720*x^3 + 7728*x^4 + 87104*x^5 +...
The g.f. satisfies A(x) = G(x*A(x)^2) and G(x) = A(x/G(x)^2) where
G(x) = 1 + 2*x + 4*x^2 + 12*x^3 + 40*x^4 + 144*x^5 + 544*x^6 +...+ A025227(n+1)*x^n +...

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

Cf. A025227, A219535, A219536, A219537, A219538.

Cf. A006318, A364167.

nmax=20; aa=ConstantArray[0,nmax]; aa[[1]]=2; Do[AGF=1+Sum[aa[[n]]*x^n,{n,1,j-1}]+koef*x^j; sol=Solve[Coefficient[1+x*(AGF^2+AGF^4)-AGF,x,j]==0,koef][[1]];aa[[j]]=koef/.sol[[1]],{j,2,nmax}]; Flatten[{1,aa}] (* Vaclav Kotesovec, Sep 10 2013 *)

/* Formula A(x) = 1 + x*(A(x)^2 + A(x)^4): */
{a(n)=local(A=1);for(i=1,n,A=1+x*(A^2+A^4) +x*O(x^n));polcoeff(A,n)}
for(n=0,25,print1(a(n),", "))

/* Formula using Series Reversion: */
{a(n)=local(A=1,G=(1-sqrt(1-4*x-4*x^2+x^3*O(x^n)))/(2*x));A=sqrt((1/x)*serreverse(x/G^2));polcoeff(A,n)}
for(n=0,25,print1(a(n),", "))

Let G(x) = (1 - sqrt(1-4*x-4*x^2))/(2*x), then g.f. A(x) satisfies:
(1) A(x) = sqrt( (1/x)*Series_Reversion(x/G(x)^2) ),
(2) A(x) = G(x*A(x)^2) and G(x) = A(x/G(x)^2),
where x*G(x) is the g.f. of A025227.
Recurrence: 3*n*(3*n-1)*(3*n+1)*(131*n^3 - 666*n^2 + 1075*n - 558)*a(n) = 2*(26200*n^6 - 172500*n^5 + 431572*n^4 - 521613*n^3 + 316327*n^2 - 89058*n + 8640)*a(n-1) - 12*(n-2)*(1441*n^5 - 8767*n^4 + 19186*n^3 - 18172*n^2 + 6930*n - 810)*a(n-2) + 8*(n-3)*(n-2)*(2*n-5)*(131*n^3 - 273*n^2 + 136*n - 18)*a(n-3). - Vaclav Kotesovec, Sep 10 2013
a(n) ~ c*d^n/n^(3/2), where d = 2/81*(7217783 + 10611 * sqrt(786))^(1/3) + 74654/(81*(7217783 + 10611 * sqrt(786))^(1/3)) + 400/81 = 14.48001092254652246... is the root of the equation -16 + 132*d - 400*d^2 + 27*d^3 = 0 and c = 1/2358*sqrt(262)*sqrt((213070976 + 3034746 * sqrt(786))^(1/3) * ((213070976 + 3034746 * sqrt(786))^(2/3) + 336670 + 1310*(213070976 + 3034746 * sqrt(786))^(1/3)))/((213070976 + 3034746 * sqrt(786))^(1/3)*sqrt(Pi)) = 0.1929450901182412149... - Vaclav Kotesovec, Sep 10 2013
a(n) = (1/n) * Sum_{k=0..floor(n-1)/2} 2^(n-k) * binomial(n,k) * binomial(3*n-k,n-1-2*k) for n > 0. - Seiichi Manyama, Apr 01 2024
a(n) = Sum_{k=0..n} binomial(n,k) * binomial(2*n+2*k+1,n)/(2*n+2*k+1). - Seiichi Manyama, Apr 03 2024

cp's OEIS Frontend

A079489 a(n) = (2*4^n*binomial(2*n, n) - binomial(4*n + 1, 2*n)) / (n + 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A112478 Expansion of (1 + x + sqrt(1 + 6*x + x^2))/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A003516 Binomial coefficients C(2n+1, n-2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A349310 G.f. A(x) satisfies: A(x) = (1 + x * A(x)^4) / (1 - x).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A349311 G.f. A(x) satisfies: A(x) = (1 + x * A(x)^5) / (1 - x).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A010683 Let S(x,y) = number of lattice paths from (0,0) to (x,y) that use the step set { (0,1), (1,0), (2,0), (3,0), ...} and never pass below y = x. Sequence gives S(n-1,n) = number of 'Schröder' trees with n+1 leaves and root of degree 2.

Views

Author

A079489 a(n) = (24^nbinomial(2n, n) - binomial(4n + 1, 2*n)) / (n + 1).

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