This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A000957 M1624 N0635 #338 Aug 05 2025 10:38:48
%S A000957 0,1,0,1,2,6,18,57,186,622,2120,7338,25724,91144,325878,1174281,
%T A000957 4260282,15548694,57048048,210295326,778483932,2892818244,10786724388,
%U A000957 40347919626,151355847012,569274150156,2146336125648,8110508473252,30711521221376
%N A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.
%C A000957 Row-sum of signed Catalan triangle A009766. - _Wouter Meeussen_
%C A000957 There are two schools of thought about the best indexing for these numbers. Deutsch and Shapiro have a(4) = 6 whereas here a(5) = 6. The formulas given here use both labelings.
%C A000957 From D. G. Rogers, Oct 18 2005: (Start)
%C A000957 I notice that you have some other zero-one evaluations of binary bracketings (such as A055395). But if you have an operation # with 0#0 = 1#0 = 1, 0#1 = 1#1 = 0, and look at the number of bracketings of a string of n 0's that come out 0, you get another instance of the Fine numbers.
%C A000957 For Z = 1 + x(ZW + WW) = 1 + x CW and W = x(ZZ + ZW) = xZC. Hence Z = 1 + xxCCZ, the functional equational for the g.f. of the Fine numbers. Indeed, C = Z + W = Z + xCZ.
%C A000957 In terms of rooted planar trees with root of even degree, this says that of all rooted planar trees, some have root of even degree (Z) and some have root of odd degree (xCZ). (End)
%C A000957 Hankel transform of a(n+1) = [1,0,1,2,6,18,57,186,...] is A000012 = [1,1,1,1,1,...]. - _Philippe Deléham_, Oct 24 2007
%C A000957 Starting with offset 3 = iterates of M * [1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,1,...] as the super and subdiagonals. - _Gary W. Adamson_, Jan 09 2009
%C A000957 Starting with 1 and convolved with A068875 = the Catalan numbers with offset 1. - _Gary W. Adamson_, May 01 2009
%C A000957 For a relation to non-crossing partitions of the root system A_n, see A100754. - _Tom Copeland_, Oct 19 2014
%C A000957 From _Tom Copeland_, Nov 02 2014: (Start)
%C A000957 Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
%C A000957 Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)] = (x-2x^2)/(1-x)^2, and Fin(Cinv(x)) = P(x).
%C A000957 Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
%C A000957 BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
%C A000957 Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
%C A000957 Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
%C A000957 (End)
%C A000957 a(n+1) is the number of Dyck paths of semilength n avoiding UD at Level 0. For n = 3 the a(4) = 2 such Dyck paths are UUUDDD and UUDUDD. - _Ran Pan_, Sep 23 2015
%C A000957 For n >= 3, a(n) is the number of permutations pi of [n-2] such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - _Colin Defant_, Sep 16 2018
%C A000957 Named after the American scientist Terrence Leon Fine (1939-2021). - _Amiram Eldar_, Jun 08 2021
%D A000957 Emeric Deutsch and Louis W. Shapiro, Seventeen Catalan identities, Bull. Instit. Combin. Applic., Vol. 31 (2001), pp. 31-38.
%D A000957 Ki Hang Kim, Douglas G. Rogers and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013). - _N. J. A. Sloane_, Jun 05 2012
%D A000957 Louis W. Shapiro and Carol J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
%D A000957 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000957 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000957 Alois P. Heinz, <a href="/A000957/b000957.txt">Table of n, a(n) for n = 0..1670</a> (first 201 terms from T. D. Noe)
%H A000957 Francesca Aicardi, <a href="https://arxiv.org/abs/2310.07317">Fuss-Catalan Triangles</a>, arXiv:2310.07317 [math.CO], 2023.
%H A000957 Martin Aigner, <a href="http://dx.doi.org/10.1016/j.disc.2007.06.012">Enumeration via ballot numbers</a>, Discrete Math., 308 (2008), 2544-2563.
%H A000957 M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, <a href="https://doi.org/10.37236/1928">Sorting Classes</a>, Elec. J. of Comb., Vol. 12 (2005), R31.
%H A000957 Elena Barcucci, Elisa Pergola, Renzo Pinzani and Simone Rinaldi, <a href="https://www.emis.de/journals/SLC/wpapers/s46rinaldi.html">ECO method and hill-free generalized Motzkin paths</a>, Séminaire Lotharingien de Combinatoire, 46 (2001).
%H A000957 Jean-Luc Baril, <a href="https://doi.org/10.37236/665">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, Vol. 18 (2011), #P178.
%H A000957 Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, <a href="http://jl.baril.u-bourgogne.fr/narayana.pdf">Generalized Narayana arrays, restricted Dyck paths, and related bijections</a>, Univ. Bourgogne (France, 2025). See p. 4.
%H A000957 Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
%H A000957 Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.
%H A000957 Paul Barry, <a href="https://arxiv.org/abs/2004.04577">On a Central Transform of Integer Sequences</a>, arXiv:2004.04577 [math.CO], 2020.
%H A000957 Paul Barry, <a href="https://arxiv.org/abs/2107.14278">Series reversion with Jacobi and Thron continued fractions</a>, arXiv:2107.14278 [math.NT], 2021.
%H A000957 Paul Barry, <a href="https://arxiv.org/abs/2307.00098">Moment sequences, transformations, and Spidernet graphs</a>, arXiv:2307.00098 [math.CO], 2023.
%H A000957 Paul Barry, <a href="https://arxiv.org/abs/2412.05461">The Triple Riordan Group</a>, arXiv:2412.05461 [math.CO], 2024. See pp. 6, 10.
%H A000957 George Beck and Karl Dilcher, <a href="https://arxiv.org/abs/2106.10400">A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence</a>, arXiv:2106.10400 [math.CO], 2021.
%H A000957 Rachael Boyd and Richard Hepworth, <a href="https://arxiv.org/abs/2006.04261">Combinatorics of injective words for Temperley-Lieb algebras</a>, arXiv:2006.04261 [math.AT], 2020.
%H A000957 Naiomi Tuere Cameron, <a href="https://web.archive.org/web/20050315140649/http://www.math.hmc.edu/~cameron/dissertation.pdf">Random walks, trees and extensions of Riordan group techniques</a>, Dissertation, Howard University, 2002.
%H A000957 Naiomi T. Cameron and Jillian E. McLeod, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.html">Returns and Hills on Generalized Dyck Paths</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.6.1.
%H A000957 Peter J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., Vol. 75, No. 1-3 (1989), pp. 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., Vol. 43 (1989), pp. 89-102.
%H A000957 Johann Cigler and Christian Krattenthaler, <a href="https://arxiv.org/abs/2003.01676">Hankel determinants of linear combinations of moments of orthogonal polynomials</a>, arXiv:2003.01676 [math.CO], 2020.
%H A000957 Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, <a href="https://arxiv.org/abs/2312.16786">On some discrete statistics of parking functions</a>, arXiv:2312.16786 [math.CO], 2023. See p. 13.
%H A000957 Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro and Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
%H A000957 Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, <a href="http://math.colgate.edu/~integers/u8/u8.Abstract.html">A bijection between the triangulations of convex polygons and ordered trees</a>, Integers, Vol. 20 (2020), Article #A8.
%H A000957 Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H A000957 Emeric Deutsch and Louis W. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., Vol. 241 (2001), pp. 241-265.
%H A000957 Filippo Disanto, Andrea Frosini and Simone Rinaldi and Renzo Pinzani, <a href="http://www.seams-bull-math.ynu.edu.cn/downloadfile.jsp?filemenu=_200805&filename=The%20Combinatorics%20of%20Convex%20Permutominoes.pdf">The Combinatorics of Convex Permutominoes</a>, Southeast Asian Bulletin of Mathematics, Vol. 32 (2008), pp. 883-912.
%H A000957 R. R. X. Du, J. He, and X. Yun, <a href="http://arxiv.org/abs/1501.07468">Counting vertices in plane and k-ary trees with given outdegree</a>, arXiv preprint arXiv:1501.07468 [math.CO], 2015.
%H A000957 Shalosh B. Ekhad, Mingjia Yang and Doron Zeilberger, <a href="http://arxiv.org/abs/1707.04654">Automated proofs of many conjectured recurrences in the OEIS made by R. J. Mathar</a>, arXiv:1707.04654 [math.HO], 2017.
%H A000957 Sergio Falcon, <a href="http://www.mathnet.or.kr/mathnet/thesis_file/CKMS-28-4-827-832.pdf">Catalan transform of the K-Fibonacci sequence</a>, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.
%H A000957 Terrence Fine, <a href="http://dx.doi.org/10.1016/S0019-9958(70)90177-4">Extrapolation when very little is known about the source</a>, Information and Control, Vol. 16 (1970), pp. 331-359.
%H A000957 Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.
%H A000957 Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, <a href="https://arxiv.org/abs/2507.23619">Picturesque convolution-like recurrences and partial sums' generation</a>, arXiv:2507.23619 [math.NT], 2025. See p. 27.
%H A000957 Taras Goy and Mark Shattuck, <a href="https://arxiv.org/abs/2303.10223">Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries</a>, arXiv:2303.10223 [math.CO], 2023.
%H A000957 Taras Goy and Mark Shattuck, <a href="https://doi.org/10.15330/cmp.15.2.420-436">Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries</a>, Carpathian Math. Publ. 15 (2023), No. 2, 420-436.
%H A000957 Candice Jean-Louis and Asamoah Nkwanta, <a href="http://dx.doi.org/10.1016/j.laa.2012.10.027">Some algebraic structure of the Riordan group</a>, Linear Algebra and its Applications, Vol. 438, No. 5 (2013), pp. 2018-2035. - _N. J. A. Sloane_, Jan 03 2013
%H A000957 Sergey Kitaev, Anna de Mier, Marc Noy, <a href="http://dx.doi.org/10.1016/j.ejc.2013.06.013">On the number of self-dual rooted maps</a>, European J. Combin., Vol. 35 (2014), pp. 377-387. MR3090510. See page 827.
%H A000957 Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
%H A000957 Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (<a href="http://arxiv.org/abs/1302.2274">arXiv:1302.2274</a>)
%H A000957 John W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, Vol. 4 (2001), Article 01.1.5.
%H A000957 Toufik Mansour and Mark Shattuck, <a href="http://arxiv.org/abs/1407.3516">Chebyshev Polynomials and Statistics on a New Collection of Words in the Catalan Family</a>, arXiv:1407.3516 [math.CO], 2014.
%H A000957 Peter McCalla and Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.
%H A000957 Asamoah Nkwanta and Akalu Tefera, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Nkwanta/nkwanta4.html">Curious Relations and Identities Involving the Catalan Generating Function and Numbers</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.9.5.
%H A000957 Paul Peart and Wen-Jin Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/PEART/peart1.html">Generating Functions via Hankel and Stieltjes Matrices</a>, J. Integer Seqs., Vol. 3 (2000), Article 00.2.1.
%H A000957 Paul Peart and Wen-Jin Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/PEART/pwatjis2.html">Dyck Paths With No Peaks at Height k</a>, J. Integer Sequences, Vol. 4 (2001), Article 01.1.3.
%H A000957 Aaron Robertson, Dan Saracino and Doron Zeilberger, <a href="http://arXiv.org/abs/math.CO/0203033">Refined restricted permutations</a>, arXiv:math/0203033 [math.CO], 2002.
%H A000957 D. G. Rogers, <a href="http://dx.doi.org/10.1016/0097-3165(77)90082-6">Similarity relations on finite ordered sets</a>, J. Combin. Theory, Series A, Vol. 23, No. 1 (1977), pp. 88-98. Erratum, loc. cit., Vol. 25 (1978), pp. 95-96.
%H A000957 Louis W. Shapiro and Carol J. Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shapiro/shapiro7.html">A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height</a>, JIS, Vol. 12 (2009), Article 09.3.2.
%H A000957 Volker Strehl, <a href="http://dx.doi.org/10.1016/0012-365X(77)90124-8">A note on similarity relations</a>, Discr. Math., Vol. 19, No. 1 (1977), pp. 99-102.
%H A000957 Hua Sun and Yi Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Wang/wang11.html">A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers</a>, J. Int. Seq., Vol. 17 (2014), Article 14.5.2
%H A000957 Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, M.Sc. Thesis, Reykjavik Univ., May 2016.
%H A000957 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A000957 Catalan(n) = 2*a(n+1) + a(n), n >= 1. [Corrected by _Pontus von Brömssen_, Jul 23 2022]
%F A000957 a(n) = (A064306(n-1) + (-1)^(n-1))/2^n, n >= 1.
%F A000957 G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) (compare g.f. for Catalan numbers, A000108). - _Emeric Deutsch_
%F A000957 a(n) ~ 4^n/(9*n*sqrt(n*Pi)). (Corrected by _Peter Luschny_, Oct 26 2015.)
%F A000957 a(n) = (2/(n-1))*Sum_{j=0..n-3}(-2)^j*(j+1)*binomial(2n-1, n-3-j), n>=2. - _Emeric Deutsch_, Dec 26 2003
%F A000957 a(n) = 3*Sum_{j=0..floor((n-1)/2)} binomial(2n-2j-2, n-1) - binomial(2n, n) for n>0. - _Emeric Deutsch_, Jan 28 2004
%F A000957 Reversion of g.f. (x-2x^2)/(1-x)^2. - _Ralf Stephan_, Mar 22 2004
%F A000957 a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, C(1/2, k)8^k})+0^n; a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, (-1)^(k-1)*2^k*(2k)!/((k!)^2*(2k-1))})+0^n. - _Paul Barry_, Jun 10 2005
%F A000957 Hankel determinant transform is 1-n. - _Michael Somos_, Sep 17 2006
%F A000957 a(n+1) = A126093(n,0). - _Philippe Deléham_, Mar 05 2007
%F A000957 a(n+1) has g.f. 1/(1-0*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(..... (continued fraction). - _Paul Barry_, Dec 02 2008
%F A000957 From _Paul Barry_, Jan 17 2009: (Start)
%F A000957 G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;
%F A000957 a(n+1) = Sum_{k=0..n} (-1)^k*C(2n-k,n-k)*(k+1)/(n+1). (End)
%F A000957 a(n) = 3*(-1/2)^(n+1) + Gamma(n+1/2)*4^n*hypergeom([1, n+1/2],[n+2],-8) /(sqrt(Pi)*(n+1)!) (for n>0). - _Mark van Hoeij_, Nov 11 2009
%F A000957 Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n>=1, a(n+1) = (-1)^n*charpoly(A,1). - _Milan Janjic_, Jul 08 2010
%F A000957 a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
%F A000957 0, 1, 0, 0, 0, 0, ...
%F A000957 1, 1, 1, 0, 0, 0, ...
%F A000957 1, 1, 1, 1, 0, 0, ...
%F A000957 1, 1, 1, 1, 1, 0, ...
%F A000957 1, 1, 1, 1, 1, 1, ...
%F A000957 ...
%F A000957 - _Gary W. Adamson_, Jul 14 2011
%F A000957 a(n+1) = Sum_{k=0..n} A039598(n,k)*(-2)^k. - _Philippe Deléham_, Nov 04 2011
%F A000957 D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - _R. J. Mathar_, Nov 15 2011
%F A000957 a(n) = sum(sum(2^(s-2n-2k)*(n/n+2k)binomial(n+2k, k)*binomial(s-n-1, s-2n-2k), (k=0, ..., floor((s-2n)/2)), (n=1, ..., s) with s>=2. - _José Luis Ramírez Ramírez_, Mar 22 2012
%F A000957 0 = a(n)*(16*a(n+1) + 22*a(n+2) - 20*a(n+3)) + a(n+1)*(34*a(n+1) + 53*a(n+2) - 38*a(n+3)) + a(n+2)*(10*a(n+2) + 4*a(n+3)) for all n in Z if we extend by a(0)=-1, a(-n) = -3/4 * (-2)^n if n>0. - _Michael Somos_, Jan 31 2014 [Corrected by _Pontus von Brömssen_, Aug 04 2022]
%F A000957 G.f. A(x) satisfies x*A'(x)/A(x) = x + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for A072547. - _Peter Bala_, Oct 01 2015
%F A000957 a(n) = 2^n*(n-2)*(2*n-1)!!*(3*(n-1)*hypergeom([1,3-n], [3+n], 2)-n-2)/(n+2)! + 0^n. - _Vladimir Reshetnikov_, Oct 25 2015
%F A000957 a(n) = binomial(2*n,n)*(hypergeom([1,(1-n)/2,1-n/2],[1-n,3/2-n],1)*3/(4-2/n)-1) for n>=2. - _Peter Luschny_, Oct 26 2015
%F A000957 O.g.f. A(x) satisfies 1 + A(x) = (1 + 3*Sum_{n >= 1} Catalan(n)*x^n)/(1 + 2*Sum_{n >= 1} Catalan(n)*x^n) = (1 + 2*Sum_{n >= 1} binomial(2*n,n)*x^n )/(1 + 3/2*Sum_{n >= 1} binomial(2*n,n)*x^n). - _Peter Bala_, Sep 01 2016
%F A000957 a(n) = Sum_{i=2..n-1} C(n-i-1)*(a(i)+a(i-1)), a(0)=0, a(1)=1, where C(n) = A000108(n). - _Vladimir Kruchinin_, Apr 23 2020
%e A000957 G.f. = x + x^3 + 2*x^4 + 6*x^5 + 18*x^6 + 57*x^7 + 186*x^8 + 622*x^9 + 2120*x^10 + ...
%p A000957 t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1,x,90); A000957 := n- coeff(t2,x,n);
%p A000957 A000957 := proc(n): if n = 0 then 0 else add((-1)^(n+k-1)*binomial(n+k-1, n-1)*(n-k)/n, k=0..n-1) fi: end: seq(A000957(n), n=0..28); # _Johannes W. Meijer_, Jul 22 2013
%p A000957 # third Maple program:
%p A000957 a:= proc(n) option remember; `if`(n<3, n*(2-n),
%p A000957 ((7*n-12)*a(n-1)+(4*n-6)*a(n-2))/(2*n))
%p A000957 end:
%p A000957 seq(a(n), n=0..32); # _Alois P. Heinz_, Apr 23 2020
%t A000957 Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} ], {n, 0, 36} ] (* _Wouter Meeussen_ *)
%t A000957 a[0] = 0; a[n_] := (1/2)*(-3*(-1/2)^n + 2^(n+1)*(2n-1)!!* Hypergeometric2F1Regularized[2, 2n+1, n+2, -1]); (* _Jean-François Alcover_, Feb 22 2012 *)
%t A000957 Table[2^n (n-2) (2n-1)!! (3 (n-1) Hypergeometric2F1[1, 3-n, 3+n, 2] - n - 2)/(n+2)! + KroneckerDelta[n], {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 25 2015 *)
%o A000957 (PARI) {a(n) = if( n<1, 0, polcoeff( 1 / (1 + 2 / (1 - sqrt(1 - 4*x + x*O(x^n)))), n))}; /* _Michael Somos_, Sep 17 2006 */
%o A000957 (PARI) {a(n) = if( n<1, 0, polcoeff( 1 / (1 + 1 / serreverse(x - x^2 + x*O(x^n))), n))}; /* _Michael Somos_, Sep 30 2006 */
%o A000957 (Haskell)
%o A000957 a000957 n = a000957_list !! n
%o A000957 a000957_list = 0 : 1 :
%o A000957 (map (`div` 2) $ tail $ zipWith (-) a000108_list a000957_list)
%o A000957 -- _Reinhard Zumkeller_, Nov 12 2011
%o A000957 (Magma) [0,1] cat [n le 1 select n-1 else (Catalan(n)-Self(n-1))/2: n in [1..30]]; // _Vincenzo Librandi_, Nov 17 2016
%o A000957 (Sage)
%o A000957 def Fine():
%o A000957 f, c, n = 1, 1, 1
%o A000957 yield 0
%o A000957 while True:
%o A000957 yield f
%o A000957 n += 1
%o A000957 c = c * (4*n - 6) // n
%o A000957 f = (c - f) // 2
%o A000957 a = Fine()
%o A000957 print([next(a) for _ in range(29)]) # _Peter Luschny_, Nov 30 2016
%o A000957 (Maxima)
%o A000957 C(n):=binomial(2*n,n)/(n+1);
%o A000957 a(n):=if n<=0 then 0 else if n=1 then 1 else sum(C(n-i-1)*(a(i)+a(i-1)),i,2,n-1);
%o A000957 /* _Vladimir Kruchinin_, Apr 23 2020 */
%o A000957 (Python)
%o A000957 from itertools import count, islice
%o A000957 def A000957_gen(): # generator of terms
%o A000957 yield from (0,1,0)
%o A000957 a, c = 0, 1
%o A000957 for n in count(1):
%o A000957 yield (a:=(c:=c*((n<<2)+2)//(n+2))-a>>1)
%o A000957 A000957_list = list(islice(A000957_gen(),20)) # _Chai Wah Wu_, Apr 26 2023
%Y A000957 A column of A065600.
%Y A000957 Sequence with signs: A064310.
%Y A000957 Bisections: A138413, A138414.
%Y A000957 Logarithmic derivative: A072547.
%Y A000957 Cf. A068875, A000108, A000045, A005043, A057078, A007317, A091867, A104597.
%Y A000957 Cf. A000012, A009766, A039598, A055395, A064306, A100754, A126093.
%K A000957 nonn,nice,easy
%O A000957 0,5
%A A000957 _N. J. A. Sloane_