|
| |
|
|
A000245
|
|
3*(2*n)!/((n+2)!*(n-1)!).
(Formerly M2809 N1130)
|
|
55
|
|
|
|
0, 1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, 149226, 534888, 1931540, 7020405, 25662825, 94287120, 347993910, 1289624490, 4796857230, 17902146600, 67016296620, 251577050010, 946844533674, 3572042254128, 13505406670700, 51166197843852, 194214400834356
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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
1->12, 2->123, 3->1234 etc. starting with 1, gives A007001: 1, 12, 12123, 12123121231234... summing the digits gives this sequence. - Miklos Kristof, Nov 05 2002
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, Oct 07 2003
With offset 1, number of permutations beginning with 12 and avoiding 32-1.
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, May 24 2004
a(n)=number of Dyck (n+1)-paths that start with UU. For example, a(2)=3 counts UUUDDD, UUDUDD, UUDDUD. - David Callan, Dec 08 2004
a(n)=number of Dyck (n+2)-paths that start with UUDU. For example, a(2)=3 counts UUDUDDUD, UUDUDUDD, UUDUUDDD. - David Scambler, Feb 14 2011
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, Feb 08 2008
Starting with offset 1 = row sums of triangle A154558 [From Gary W. Adamson, Jan 11 2009]
Starting with offset 1 equals INVERT transform of A014137, partial sums of the Catalan numbers: (1, 2, 4, 9, 23,...). [From Gary W. Adamson, May 15 2009] With offset 1, a(n) is the binomial transform of the shortened Motzkin numbers: 1, 2, 4, 9, 21, 51, 127, 323....(A001006). [Aoife Hennessy (aoife.hennessy(AT)gmail.com), Sep 07 2009]
The Catalan sequence convolved with its shifted variant, e.g. a(5) = 90 = (1, 1, 2, 5, 14) dot (42, 14, 5, 2, 1) = (42 + 14 + 10 + 10 + 14 ) = 90. - Gary W. Adamson, Nov 22 2011
a(n+2) = A214292(2*n+3,n). - Reinhard Zumkeller, Jul 12 2012
|
|
|
REFERENCES
|
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178; http://www.combinatorics.org/Volume_18/PDF/v18i1p178.pdf.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
S. J. Cyvin and I. Gutman, Kekule structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 196).
P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_3(z).
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
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.
Kim, Ki Hang; Rogers, Douglas G.; Roush, Fred W. 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) - From N. J. A. Sloane, Jun 05 2012
A. Papoulis, A new method of inversion of the Laplace transform, Quart. Applied Math. 14 (1956), 405ff.
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Zoran Sunik, Self describing sequences and the Catalan family tree, Elect. J. Combin., 10 (No. 1, 2003).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..100
D. Callan, A recursive bijective approach to counting permutations...
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908, 2012.
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6
Guo-Niu Han, Enumeration of Standard Puzzles
S. Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. B48e (2003).
S. Kitaev and T. Mansour, Simultaneous avoidance of generalized patterns, arXiv:math.co/0205182
S. J. Tedford, Combinatorial interpretations of convolutions of the Catalan numbers, Integers 11 (2011) #A3
|
|
|
FORMULA
|
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). [Wolfdieter Lang]
For n>1, a(n)=3a(n-1)+Sum[a(k)a(n-k-2), k=1,...,n-3]. - John W. Layman, Dec 13 2002; proved by Michael Somos, Jul 05, 2003
G.f. is A(x) = C(x)*(1-x)/x-1/x = x(1+x*C(x)^2)*C(x)^2 where C(x) is g.f. for Catalan numbers, A000108.
G.f. satisfies x^2*A(x)^2+(3*x-1)*A(x)+x = 0.
Series reversion of g.f. A(x) is -A(-x). - Michael Somos, Jan 21 2004
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
An inverse Chebyshev transform of x^2. - Paul Barry, Oct 13 2004
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, Oct 13 2004
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)-2*C(1,k)+C(0, k))*(1+(-1)^(n-k))/(n+k+2)} - Paul Barry, Oct 13 2004
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, Feb 16 2006
E.g.f.: exp(2*x)*(Bessel_I(1,2x)-Bessel_I(2,2*x)); - Paul Barry, Jun 04 2007
a(n)=(1/pi)*int(x^n*(x-1)*sqrt(x*(4-x))/(2*x),x,0,4); - Paul Barry, Feb 08 2008
For n>1, a(n+1)=2*(2n+1)*(n+1)*a(n)/((n+3)*n). [From Sean A. Irvine, Dec 09 2009]
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>=2, a(n-1)=(-1)^(n-2)*coeff(charpoly(A,x),x^2). [From Milan Janjic, Jul 08 2010]
a(n) = sum of top row terms of M^(n-1), M = an infinite square production matrix as follows:
2, 1, 0, 0, 0, 0,...
1, 1, 1, 0, 0, 0,...
1, 1, 1, 1, 0, 0,...
1, 1, 1, 1, 1, 0,...
1, 1, 1, 1, 1, 1,...
...
- Gary W. Adamson, Jul 14 2011
E.g.f.: exp(2*x)*(BesselI(2,2*x)) = Q(0) - 1 where Q(k)= 1 - 2*x/(k + 1 - 3*((k+1)^2)/((k^2) + 8*k + 9 - (k+2)*((k+3)^2)*(2*k+3)/((k+3)*(2*k+3) - 3*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Dec 05 2011
a(n) = -binomial(2*n,n)/(n+1)*hypergeom([-1,n+1/2],[n+2],4). - Peter Luschny, Aug 15 2012
a(n) = sum(i=0..n-1, C(i)*C(n-i)), where C(i) denotes the i-th Catalan number. [From Dmitry Kruchinin, Mar 02 2013]
|
|
|
MAPLE
|
A000245 := n -> 3*binomial(2*n, n-1)/(n+2);
|
|
|
MATHEMATICA
|
Table[3(2n)!/((n+2)!(n-1)!), {n, 0, 30}] (* or *) Table[3*Binomial[2n, n-1]/(n+2), {n, 0, 30}] (* or *) Differences[CatalanNumber[Range[0, 31]]] (* From Harvey P. Dale, Jul 13 2011 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, 3*(2*n)!/(n+2)!/(n-1)!)
(Sage) [catalan_number(i+1)-catalan_number(i) for i in xrange(0, 28)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 17 2009]
(Sage)
def A000245_list(n) :
D = [0]*(n+1); D[1] = 1
b = False; h = 1; R = []
for i in range(2*n-1) :
if b :
for k in range(h, 0, -1) : D[k] += D[k-1]
h += 1; R.append(D[2])
else :
for k in range(1, h, 1) : D[k] += D[k+1]
b = not b
return R
A000245_list(29) # Peter Luschny, June 03 2012
|
|
|
CROSSREFS
|
First differences of Catalan numbers A000108.
T(n, n+3) for n=0, 1, 2, ..., array T as in A047072. Also a diagonal of A059365 and of A009766.
Cf. A099364.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A000108 A002057 A000344 A003517 A000588 A003518 A003519 A001392.
A154558 [From Gary W. Adamson, Jan 11 2009]
Cf. A014137 [From Gary W. Adamson, May 15 2009]
Sequence in context: A094826 A033190 A071724 * A143739 A189940 A047047
Adjacent sequences: A000242 A000243 A000244 * A000246 A000247 A000248
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
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, Oct 31, 2003.
|
|
|
STATUS
|
approved
|
| |
|
|
