|
| |
|
|
A005043
|
|
Motzkin sums: a(n) = (n-1)*(2*a(n-1)+3*a(n-2))/(n+1). Also called Riordan numbers or ring numbers.
(Formerly M2587)
|
|
68
|
|
|
|
1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
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).
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.
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
Number of Motzkin paths of length n with no horizontal steps at level 0. - Emeric Deutsch, Nov 09 2003
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
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
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
First diagonal of triangular array in A059346.
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
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
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
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
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
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
Binomial transform of A126930. [From Philippe DELEHAM, Nov 26 2009]
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
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
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
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]
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]
Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - David Scambler, Apr 17 2012
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]
|
|
|
REFERENCES
|
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
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. L. Andrews and T. Thirunamachandran, On three-dimensional rotational averages, J. Chem. Phys., 67 (1977), 5026-5033.
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.
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
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
D. Callan, Pattern avoidance in "flattened" partitions, Discrete Math., 309 (2009), 4187-4191.
BENOIT COLLINS, ION NECHITA AND DEPING YE, THE ABSOLUTE POSITIVE PARTIAL TRANSPOSE PROPERTY FOR RANDOM INDUCED STATES, Arxiv preprint arXiv:1108.1935, 2011
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
R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191. [From Emeric Deutsch, May 29 2010]
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
P. Hanlon, Counting interval graphs. Trans. Amer. Math. Soc. 272 (1982), no. 2, 383-426.
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.
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
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
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combin. Theory, A 23 (1975), 214-222.
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.
H. C. H. Schubert, Math. Annalen, 1895.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D n Verma, Towards Classifying Finite Point-Set Configurations, preprint, 1997.
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.
F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..200
David Callan, Riordan numbers are differences of trinomial coefficients.
W. Y. C. Chen, E. Y. P. Deng and L. L. M. Yang, Riordan paths and derangements
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 423
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, 2008.
Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, Restricted rooted non-separable planar maps, Arxiv preprint arXiv:1202.1790, 2012.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.
E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique
Eric Weisstein's World of Mathematics, Isotropic Tensor.
|
|
|
FORMULA
|
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).]
G.f.: (1+x-sqrt(1-2*x-3*x^2))/(2*x*(1+x)).
G.f.: 2/(1+x+sqrt(1-2*x-3*x^2)) - Paul Peart (ppeart(AT)fac.howard.edu), May 27, 2000
a(n+1) + (-1)^n = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0) - Bernhart.
a(n) = (1/(n+1)) * Sum_{i} (-1)^i*binomial(n+1, i)*binomial(2*n-2*i, n-i) - Bernhart.
G.f. A(x) satisfies A = 1/(1+x) + x*A^2.
E.g.f.: exp(x)*(BesselI(0, 2*x)-BesselI(1, 2*x)). - Vladeta Jovovic, Apr 28 2003
a(n)=A001006(n-1)-a(n-1).
a(n+1) = Sum[k=0..n, (-1)^k*A026300(n, k) ], where A026300 is the Motzkin triangle.
a(n)=sum{k=0..n, (-1)^k*binomial(n, k)*binomial(k, floor(k/2))} - Paul Barry, Jan 27 2005
a(n) = Sum_{k>=0} A086810(n-k, k) . - Philippe DELEHAM, May 30 2005
a(n+2) = Sum_{ k>=0} A064189(n-k, k) . - Philippe DELEHAM, May 31 2005
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
Inverse binomial transform of A000108 (Catalan numbers) . - Philippe DELEHAM, Oct 20 2006
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
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]
G.f.: 1/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). [Paul Barry, May 16 2009]
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]
a(n) = -(-1)^n * hypergeom([1/2, n+2],[2],4/3) / sqrt(-3) [Mark van Hoeij, Jul 02 2010]
a(n) = (-1)^n*hypergeometric([-n,1/2],[2],4). - Peter Luschny, Aug 15 2012
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]
a(n) ~ 3^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 02 2012
|
|
|
EXAMPLE
|
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.
|
|
|
MAPLE
|
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;
Order := 20: solve(series((x-x^2)/(1-x+x^2), x)=y, x); # outputs g.f.
|
|
|
MATHEMATICA
|
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)
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 *)
|
|
|
PROG
|
(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 */
(Maxima) a[0]:1$
a[1]:0$
a[n]:=(n-1)*(2*a[n-1]+3*a[n-2])/(n+1)$
makelist(a[n], n, 0, 12); /* Emanuele Munarini, Mar 02 2011 */
(Haskell)
a005043 n = a005043_list !! n
a005043_list = 1 : 0 : zipWith div
(zipWith (*) [1..] (zipWith (+)
(map (* 2) $ tail a005043_list) (map (* 3) a005043_list))) [3..]
-- Reinhard Zumkeller, Jan 31 2012
(PARI) N=66; Vec(serreverse(x/(1+x*sum(k=1, N, x^k))+O(x^N))) /* Joerg Arndt, Aug 19 2012 */
|
|
|
CROSSREFS
|
Row sums of triangle A020474, first differences of A082395.
Cf. A126120.
A178514 [From Emeric Deutsch, May 29 2010]
Sequence in context: A052827 A033192 A174297 * A099323 A058534 A063778
Adjacent sequences: A005040 A005041 A005042 * A005044 A005045 A005046
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Thanks to Laura L. M. Yang (yanglm(AT)hotmail.com) for a correction, Aug 29, 2004
|
|
|
STATUS
|
approved
|
| |
|
|
