|
%I M2587
%S 1,0,1,1,3,6,15,36,91,232,603,1585,4213,11298,30537,83097,227475,
%T 625992,1730787,4805595,13393689,37458330,105089229,295673994,
%U 834086421,2358641376,6684761125,18985057351,54022715451,154000562758
%N Motzkin sums: a(n) = (n-1)*(2*a(n-1)+3*a(n-2))/(n+1). Also called Riordan numbers or ring numbers.
%C I'm not sure "Motzkin sums" is a good name for this. It has the property that Motzkin(n) = A001006(n) = a(n) + a(n+1), e.g. A001006(4) = 9 = 3 + 6 = a(4) + a(5).
%C Number of 'Catalan partitions', that is partitions of a set 1,2,3,...,n into parts that are not singletons and whose convex hulls are disjoint when the points are arranged on a circle (so when the parts are all pairs we get Catalan numbers) - Aart Blokhuis (aartb(AT)win.tue.nl), Jul 04, 2000.
%C Number of ordered trees with n edges and no vertices of outdegree 1. For n > 1, number of dissections of a convex polygon by nonintersecting diagonals with a total number of n+1 edges. - _Emeric Deutsch_, Mar 06 2002
%C Number of Motzkin paths of length n with no horizontal steps at level 0. - _Emeric Deutsch_, Nov 09 2003
%C Number of Dyck paths of semilength n with no peaks at odd level. Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUDUDD, where U=(1,1), D=(1,-1). Number of Dyck paths of semilength n with no ascents of length 1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUUDDD. - _Emeric Deutsch_, Dec 05 2003
%C Arises in Schubert calculus as follows. Let P = complex projective space of dimension n+1. Take n projective subspaces of codimension 3 in P in general position. Then a(n) is the number of lines of P intersecting all these subspaces. - F. Hirzebruch, Feb 09, 2004
%C Difference between central trinomial coefficient and its predecessor. Example: a(6)=15=141-126 and (1+x+x^2)^6=...+ 126*x^5 + 141*x^6 +... (Catalan number A000108(n) is difference between central binomial coefficient and its predecessor.) - _David Callan_, Feb 07 2004
%C First diagonal of triangular array in A059346.
%C a(n) = number of 321-avoiding permutations on [n] in which each left-to-right maximum is a descent (i.e. is followed by a smaller number). For example, a(4) counts 4123, 3142, 2143. - _David Callan_, Jul 20 2005
%C The Hankel transform of this sequence give A000012 = [1, 1, 1, 1, 1, 1, 1, . . .]; example : Det([1, 0, 1, 1; 0, 1, 1, 3; 1, 1, 3, 6; 1, 3, 6, 15]) = 1 . - _Philippe DELEHAM_, May 28 2005
%C The number of projective invariants of degree 2 for n labeled points on the projective line. - Benjamin J. Howard (bhoward(AT)ima.umn.edu), Nov 24 2006
%C Define a random variable X=trA^2, where A is a 2 X 2 unitary symplectic matrix chosen from USp(2) with Haar measure. The n-th central moment of X is E[(X+1)^n] = a(n). - Andrew V. Sutherland (drew(AT)math.mit.edu), Dec 02 2007
%C Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the n-th tensor power of V is a(n). - Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008
%C Starting with offset 3 = iterates of M * [1,1,1,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - _Gary W. Adamson_, Jan 08 2009
%C Binomial transform of A126930. [From _Philippe DELEHAM_, Nov 26 2009]
%C a(n) has the following standard-Young-tableaux (SYT) interpretation: binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1)=f^(k,k,1^{n-2k}) where f^lambda equals the number of SYT of shape lambda. - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010
%C a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n-2k}) for all 1=< k =< floor(n/2). - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010
%C a(n) is the number of derangements of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(3)=1 because p=231=(123) is the only derangement of {1,2,3} with genus 0. Indeed, cp'=231*312=123=(1)(2)(3) and so g(p)= (1/2)(3+1-1-3)=0. - _Emeric Deutsch_, May 29 2010
%C The Hankel transform of a(n+1) is A128834. The Hankel transform of a(n+2) is floor((2*n+4)/3) = A004523(n+2). [Paul Barry, Mar 8 2011]
%C The Kn11 triangle sums of triangle A175136 lead to A005043(n+2), while the Kn12(n) = A005043(n+4)-2^(n+1), Kn13(n) = A005043(n+6)-(n^2+9*n+56)*2^(n-2) and the Kn4(n) = A005043(2*n+2) = A099251(n+1) triangle sums are related to the sequence given above. For the definitions of these triangle sums see A180662. [From Johannes W. Meijer, May 06 2011]
%C Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - _David Scambler_, Apr 17 2012
%C This is true. Proof. The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck n-paths to those Dyck (2n)-paths in which each ascent is of length 2. It sends descents of length 1 in the n-path to descents of length 2 in the (2n)-path. But Dyck n-paths with no descents of length 1 are equinumerous with Riordan n-paths (Motzkin n-paths with no flatsteps at ground level) as follows. Given a Dyck n-path with no descents of length 1, split it into consecutive step pairs, then replace UU by U, DD by D, UD by a blue flatstep (F), DU by a red flatstep, and concatenate the new steps to get a colored Motzkin path. Each red F will be (immediately) preceded by a blue F or a D. In the latter case, transfer the red F so that it precedes the matching U of the D. Finally, erase colors to get the required Riordan path. For example, with lowercase f denoting a red flatstep, U^5 D^2 U D^4 U^4 D^3 U D^2 -> (U^2, U^2, UD, DU, D^2, D^2, U^2, U^2 D^2, DU, D^2) -> UUFfDDUUDfD -> UUFFDDUFUDD. [_David Callan_, Apr 25 2012]
%D M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
%D Almkvist, Gert; Dicks, Warren; Formanek, Edward; Hilbert series of fixed free algebras and noncommutative classical invariant theory. J. Algebra 93 (1985), no. 1, 189-214.
%D D. L. Andrews and T. Thirunamachandran, On three-dimensional rotational averages, J. Chem. Phys., 67 (1977), 5026-5033.
%D 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.
%D P. Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
%D F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
%D D. Callan, Pattern avoidance in "flattened" partitions, Discrete Math., 309 (2009), 4187-4191.
%D BENOIT COLLINS, ION NECHITA AND DEPING YE, THE ABSOLUTE POSITIVE PARTIAL TRANSPOSE PROPERTY FOR RANDOM INDUCED STATES, Arxiv preprint arXiv:1108.1935, 2011
%D D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
%D R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
%D S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191. [From _Emeric Deutsch_, May 29 2010]
%D Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, Arxiv preprint arXiv:1110.6638, 2011
%D P. Hanlon, Counting interval graphs. Trans. Amer. Math. Soc. 272 (1982), no. 2, 383-426.
%D B. Howard, J. Millson, A. Snowden and R. Vakil, http://arXiv.org/abs/math.AG/0505096, "The projective invariants of ordered points on the line", preprint, 2005.
%D S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, Restricted non-separable planar maps and some pattern avoiding permutations, http://staff.ru.is/henningu/papers/maps/maps.pdf, 2012. - From _N. J. A. Sloane_, Jan 01 2013
%D Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), 227-238; http://www.mat.unisi.it/newsito/puma/public_html/22_2/manara_perelli-cippo.pdf. - From _N. J. A. Sloane_, Oct 13 2012
%D J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combin. Theory, A 23 (1975), 214-222.
%D E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601-620.
%D H. C. H. Schubert, Math. Annalen, 1895.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D _D n Verma_, Towards Classifying Finite Point-Set Configurations, preprint, 1997.
%D Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords, http://people.brandeis.edu/~gessel/homepage/students/wangthesis.pdf.
%D F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.
%H T. D. Noe, <a href="/A005043/b005043.txt">Table of n, a(n) for n=0..200</a>
%H David Callan, <a href="http://www.stat.wisc.edu/~callan/papersother/">Riordan numbers are differences of trinomial coefficients</a>.
%H W. Y. C. Chen, E. Y. P. Deng and L. L. M. Yang, <a href="http://arXiv.org/abs/math.CO/0602298">Riordan paths and derangements</a>
%H E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/abs/math.CO/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=423">Encyclopedia of Combinatorial Structures 423</a>
%H Kiran S. Kedlaya and Andrew V. Sutherland, <a href="http://arXiv.org/abs/0803.4462">Hyperelliptic curves, L-polynomials and random matrices</a>, 2008.
%H Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, <a href="http://arxiv.org/abs/1202.1790">Restricted rooted non-separable planar maps</a>, Arxiv preprint arXiv:1202.1790, 2012.
%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.4153/CJM-1997-015-x">On some alternative characterizations of Riordan arrays</a>, Canad. J. Math., 49 (1997), 301-320.
%H E. Royer, <a href="http://www.carva.org/emmanuel.royer">Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IsotropicTensor.html">Isotropic Tensor.</a>
%F a(n)=sum((-1)^(n-k)*binomial(n, k)*A000108(k), k=0..n). a(n)=sum(binomial(n+1, k)*binomial(n-k-1, k-1), k=0..ceil(n/2))/(n+1); (for n>1) - Len Smiley (smiley(AT)math.uaa.alaska.edu). [Comment from Amitai Regev (amitai.regev(AT)weizmann.ac.il), Mar 02 2010: the latter sum should be over the range k=1..floor(n/2).]
%F G.f.: (1+x-sqrt(1-2*x-3*x^2))/(2*x*(1+x)).
%F G.f.: 2/(1+x+sqrt(1-2*x-3*x^2)) - Paul Peart (ppeart(AT)fac.howard.edu), May 27, 2000
%F a(n+1) + (-1)^n = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0) - Bernhart.
%F a(n) = (1/(n+1)) * Sum_{i} (-1)^i*binomial(n+1, i)*binomial(2*n-2*i, n-i) - Bernhart.
%F G.f. A(x) satisfies A = 1/(1+x) + x*A^2.
%F E.g.f.: exp(x)*(BesselI(0, 2*x)-BesselI(1, 2*x)). - _Vladeta Jovovic_, Apr 28 2003
%F a(n)=A001006(n-1)-a(n-1).
%F a(n+1) = Sum[k=0..n, (-1)^k*A026300(n, k) ], where A026300 is the Motzkin triangle.
%F a(n)=sum{k=0..n, (-1)^k*binomial(n, k)*binomial(k, floor(k/2))} - _Paul Barry_, Jan 27 2005
%F a(n) = Sum_{k>=0} A086810(n-k, k) . - _Philippe DELEHAM_, May 30 2005
%F a(n+2) = Sum_{ k>=0} A064189(n-k, k) . - _Philippe DELEHAM_, May 31 2005
%F Moment representation: a(n)=(1/(2*pi))*Int(x^n*sqrt((1+x)(3-x))/(1+x),x,-1,3); - _Paul Barry_, Jul 09 2006
%F Inverse binomial transform of A000108 (Catalan numbers) . - _Philippe DELEHAM_, Oct 20 2006
%F a(n) = (2/pi)* Integral_{t_0..pi} (4cos^2(x)-1)^n*sin^2(x)dx - Andrew V. Sutherland (drew(AT)math.mit.edu), Dec 02 2007
%F G.f.: 1/(1-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-.....(continued fraction). [_Paul Barry_, Jan 22 2009]
%F G.f.: 1/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). [_Paul Barry_, May 16 2009]
%F G.f.: 1/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-... (continued fraction). [_Paul Barry_, Mar 02 2010]
%F a(n) = -(-1)^n * hypergeom([1/2, n+2],[2],4/3) / sqrt(-3) [_Mark van Hoeij_, Jul 02 2010]
%F a(n) = (-1)^n*hypergeometric([-n,1/2],[2],4). - _Peter Luschny_, Aug 15 2012
%F Let A(x) be the g.f., then x*A(x) is the reversion of x/(1 + x^2*sum(k>=0, x^k)); see A215340 for the correspondence to Dyck paths without length-1 ascents. [_Joerg Arndt_, Aug 19 2012 and Apr 16 2013]
%F a(n) ~ 3^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 02 2012
%e a(5)=6 because the only dissections of a polygon with a total number of 6 edges are: five pentagons with one of the five diagonals and the hexagon with no diagonals.
%p A005043 := proc(n) option remember; if n <= 1 then 1-n else (n-1)*(2*A005043(n-1)+3*A005043(n-2))/(n+1); fi; end;
%p Order := 20: solve(series((x-x^2)/(1-x+x^2),x)=y,x); # outputs g.f.
%t a[0] = 1; a[1] = 0; a[n_] := a[n] = (n - 1)*(2*a[n - 1] + 3*a[n - 2])/(n + 1); Table[ a[n], {n, 0, 30}] (from _Robert G. Wilson v_, Jun 14 2005)
%t Table[(-3)^(1/2)/6 * (-1)^n*(3*Hypergeometric2F1[1/2,n+1,1,4/3]+ Hypergeometric2F1[1/2,n+2,1,4/3]), {n,0,32}] (* cf. Mark van Hoeij in A001006 *) (* _Wouter Meeussen_, Jan 23 2010 *)
%o (PARI) a(n)=if(n<0, 0, n++; polcoeff(serreverse((x-x^3)/(1+x^3)+x*O(x^n)), n)) /* _Michael Somos_, May 31 2005 */
%o (Maxima) a[0]:1$
%o a[1]:0$
%o a[n]:=(n-1)*(2*a[n-1]+3*a[n-2])/(n+1)$
%o makelist(a[n],n,0,12); /* _Emanuele Munarini_, Mar 02 2011 */
%o (Haskell)
%o a005043 n = a005043_list !! n
%o a005043_list = 1 : 0 : zipWith div
%o (zipWith (*) [1..] (zipWith (+)
%o (map (* 2) $ tail a005043_list) (map (* 3) a005043_list))) [3..]
%o -- _Reinhard Zumkeller_, Jan 31 2012
%o (PARI) N=66; Vec(serreverse(x/(1+x*sum(k=1,N,x^k))+O(x^N))) /* _Joerg Arndt_, Aug 19 2012 */
%Y Row sums of triangle A020474, first differences of A082395.
%Y Cf. A126120.
%Y A178514 [From _Emeric Deutsch_, May 29 2010]
%K nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_.
%E Thanks to Laura L. M. Yang (yanglm(AT)hotmail.com) for a correction, Aug 29, 2004
|
