%I A000245 M2809 N1130
%S A000245 0,1,3,9,28,90,297,1001,3432,11934,41990,149226,534888,1931540,7020405,
               25662825,
%T A000245 94287120,347993910,1289624490,4796857230,17902146600,67016296620,251577050010,
%U A000245 946844533674,3572042254128,13505406670700,51166197843852,194214400834356
%N A000245 3(2n)!/((n+2)!(n-1)!).
%C A000245 This sequence represents the expected saturation of a binary search tree 
               (or BST) on n nodes times the number of binary search trees on n 
               nodes, or alternatively, the sum of the saturation of all binary 
               search trees on n nodes. - Marko Riedel (mriedel(AT)neuearbeit.de), 
               Jan 24 2002
%C A000245 1->12, 2->123, 3->1234 etc. starting with 1, gives A007001: 1, 12, 12123, 
               12123121231234... suming the digits gives this sequence. - Miklos 
               Kristof (kristmikl(AT)freemail.hu), Nov 05 2002
%C A000245 a(n-1) = number of n-th generation vertices in the tree of sequences 
               with unit increase labeled by 2 (cf. Zoran Sunik reference.) - Benoit 
               Cloitre (benoit7848c(AT)orange.fr), Oct 07 2003
%C A000245 With offset 1, number of permutations beginning with 12 and avoiding 
               32-1.
%C A000245 Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,
               1) which touch but do not cross the line x-y=1. - Herbert Kociemba 
               (kociemba(AT)t-online.de), May 24 2004
%C A000245 a(n)=number of Dyck (n+1)-paths that start with UU. For example, a(2)=3 
               counts UUUDDD, UUDUDD, UUDDUD. - David Callan (callan(AT)stat.wisc.edu), 
               Dec 08 2004
%C A000245 Hankel transform is (0,-1,-1,0,1,1,0,-1,-1, 0...). Hankel transform of 
               a(n+1) is (1,0,-1,-1,0,1,1,0,-1,-1,0...). - Paul Barry (pbarry(AT)wit.ie), 
               Feb 08 2008
%C A000245 Starting with offset 1 = row sums of triangle A154558 [From Gary W. Adamson 
               (qntmpkt(AT)yahoo.com), Jan 11 2009]
%C A000245 Starting with offset 1 equals INVERT transform of A014137, partial sums 
               of the Catalan nubmers: (1, 2, 4, 9, 23,...). [From Gary W. Adamson 
               (qntmpkt(AT)yahoo.com), May 15 2009]
%C A000245 Contribution from Aoife Hennessy (aoife.hennessy(AT)gmail.com), Sep 07 
               2009: (Start)
%C A000245 With offset 1, a(n) is the binomial transform of the shortened
%C A000245 Motzkin numbers: 1, 2, 4, 9, 21, 51, 127, 323....(A001006) (End)
%D A000245 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000245 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000245 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and 
               related issues, Discr. Math., 308 (2008), 1209-1221.
%D A000245 Paul Barry, A Catalan Transform and Related Transformations on Integer 
               Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
%D A000245 S. J. Cyvin and I. Gutman, Kekule structures in benzenoid hydrocarbons, 
               Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see 
               p. 196).
%D A000245 V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising 
               from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 
               395-405.
%D A000245 A. Papoulis, A new method of inversion of the Laplace transform, Quart. 
               Applied Math. 14 (1956), 405ff.
%D A000245 J. Riordan, The distribution of crossings of chords joining pairs of 
               2n points on a circle, Math. Comp., 29 (1975), 215-222.
%D A000245 Zoran Sunik, Self describing sequences and the Catalan family tree, Elect. 
               J. Combin., 10 (No. 1, 2003).
%H A000245 T. D. Noe, <a href="b000245.txt">Table of n, a(n) for n=0..100</a>
%H A000245 D. Callan, <a href="http://arXiv.org/abs/math.CO/0211380">A recursive 
               bijective approach to counting permutations...</a>
%H A000245 R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, <a href="http://www.cs.uwaterloo.ca/
               journals/JIS/index.html">J. Integer Seqs., Vol. 3 (2000), #00.1.6</
               a>
%H A000245 S. Kitaev and T. Mansour, <a href="http://arXiv.org/abs/math.CO/0205182">
               Simultaneous avoidance of generalized patterns</a>.
%H A000245 S. Kitaev, <a href="http://www.mat.univie.ac.at/users/slc/public_html/
               wpapers/s48kitaev.html">Generalized pattern avoidance with additional 
               restrictions</a>, Sem. Lothar. Combinat. B48e (2003).
%F A000245 Comment from wolfdieter.lang(AT)physik.uni-karlsruhe.de: G.f.: x*(c(x))^3 
               = (-1+(1-x)*c(x))/x, c(x) = g.f. for Catalan numbers. Also a(n)=3*n*Catalan(n)/
               (n+2).
%F A000245 For n>1, a(n)=3a(n-1)+Sum[a(k)a(n-k-2), k=1,...,n-3]. - John W. Layman 
               (layman(AT)math.vt.edu), Dec 13 2002; proved by Michael Somos, Jul 
               05, 2003
%F A000245 G.f. is A(x) = C(x)(1-x)/x-1/x = x(1+xC(x)^2)C(x)^2 where C(x) is g.f. 
               for Catalan numbers, A000108.
%F A000245 G.f. satisfies x^2A(x)^2+(3x-1)A(x)+x=0.
%F A000245 Series reversion of g.f. A(x) is -A(-x). - Michael Somos, Jan 21 2004
%F A000245 a(n+1)=sum(i+j+k=n, C(i)C(j)C(k)) with i, j, k>=0 and where C(k) denotes 
               the k-th Catalan number. - Benoit Cloitre, Nov 09 2003
%F A000245 An inverse Chebyshev transform of x^2. - Paul Barry (pbarry(AT)wit.ie), 
               Oct 13 2004
%F A000245 The sequence is 0, 0, 1, 0, 3, 0, 9, 0, ...with zeros restored. Second 
               binomial transform of (-1)^n*A005322(n). The g.f. is transformed 
               to x^2 under the Chebyshev transformation A(x)->(1/(1+x^2))A(x/(1+x^2)). 
               For a sequence b(n), this corresponds to taking sum{k=0..floor(n/
               2), C(n-k, k)(-1)^k*b(n-2k)}, or sum{k=0..n, C((n+k)/2, k)b(k)(-1)^((n-k)/
               2)(1+(-1)^(n-k))/2}. - Paul Barry (pbarry(AT)wit.ie), Oct 13 2004
%F A000245 G.f.: (c(x^2)(1-x^2)-1)/x^2, c(x) the g.f. of A000108; a(n)=sum{k=0..n, 
               (k+1)C(n, (n-k)/2)(-1)^k(C(2, k)-2C(1, k)+C(0, k))(1+(-1)^(n-k))/
               (n+k+2)} - Paul Barry (pbarry(AT)wit.ie), Oct 13 2004
%F A000245 C(n+1)-C(n)=sum{k=0..n, C(n,k)*2^(n-k)*(-1)^(k+1)*C(k,floor((k-1)/2))}; 
               - Paul Barry (pbarry(AT)wit.ie), Feb 16 2006
%F A000245 E.g.f.: exp(2x)(Bessel_I(1,2x)-Bessel_I(2,2x)); - Paul Barry (pbarry(AT)wit.ie), 
               Jun 04 2007
%F A000245 a(n)=(1/pi)*int(x^n*(x-1)*sqrt(x(4-x))/(2x),x,0,4); - Paul Barry (pbarry(AT)wit.ie), 
               Feb 08 2008
%p A000245 A000245 := n -> 3*binomial(2*n,n-1)/(n+2);
%o A000245 (PARI) a(n)=if(n<1,0,3*(2*n)!/(n+2)!/(n-1)!)
%o A000245 (Other) sage: [catalan_number(i+1)-catalan_number(i) for i in xrange(0,
               28)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 
               2009]
%Y A000245 First differences of Catalan numbers A000108.
%Y A000245 T(n, n+3) for n=0, 1, 2, ..., array T as in A047072. Also a diagonal 
               of A059365 and of A009766.
%Y A000245 Cf. A099364.
%Y A000245 A diagonal of any of the essentially equivalent arrays A009766, A030237, 
               A033184, A059365, A099039, A106566, A130020, A047072.
%Y A000245 Cf. A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392.
%Y A000245 A154558 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 11 2009]
%Y A000245 Cf. A014137 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 15 2009]
%Y A000245 Sequence in context: A094826 A033190 A071724 this_sequence A143739 A047047 
               A071744
%Y A000245 Adjacent sequences: A000242 A000243 A000244 this_sequence A000246 A000247 
               A000248
%K A000245 nonn,easy,nice
%O A000245 0,3
%A A000245 N. J. A. Sloane (njas(AT)research.att.com).
%E A000245 I changed the description and added an initial 0, to make this coincide 
               with the first differences of the Catalan numbers A000108. Some of 
               the other lines will need to be changed as a result. - N. J. A. Sloane 
               (njas(AT)research.att.com), Oct 31, 2003.