login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005717 Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.
(Formerly M1612)
33

%I M1612 #187 Mar 01 2024 09:57:55

%S 1,2,6,16,45,126,357,1016,2907,8350,24068,69576,201643,585690,1704510,

%T 4969152,14508939,42422022,124191258,363985680,1067892399,3136046298,

%U 9217554129,27114249960,79818194925,235128465026,693085098852,2044217638456,6032675068061

%N Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.

%C Number of ordered trees with n+1 edges, having root of even degree and nonroot nodes of outdegree at most 2. - _Emeric Deutsch_, Aug 02 2002

%C The connection to Motzkin numbers comes from the Lagrange inversion formula. - _Michael Somos_, Oct 10 2003

%C Number of horizontal steps in all Motzkin paths of length n. - _Emeric Deutsch_, Nov 09 2003

%C Number of UHD's in all Motzkin paths of length n+2 (here U=(1,1), H=(1,0) and D=(1,-1)). Example: a(2)=2 because in the nine Motzkin paths of length 4, HHHH, HHUD, HUDH, H(UHD), UDHH, UDUD, (UHD)H, UHHD and UUDD, we have altogether two UHD's (shown between parentheses). - _Emeric Deutsch_, Dec 26 2003

%C Number of ordered trees with n+1 edges, having exactly one leaf at even height. Number of Dyck path of semilength n+1, having exactly one peak at even height. Example: a(3)=6 because we have uuu(ud)ddd, u(ud)dudud, udu(ud)dud, ududu(ud)d, u(ud)uuddd and uuudd(ud)d (here u=(1,1),d=(1,-1) and the unique peak at even height is shown between parentheses). - _Emeric Deutsch_, Mar 10 2004

%C a(n) is the number of Dyck (n+1)-paths containing exactly one UDU. - _David Callan_, Jul 15 2004

%C Number of peaks in all Motzkin paths of length n+1. - _Emeric Deutsch_, Sep 01 2004

%C This is a kind of Motzkin transform of A059841 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A059841 generates 1,0,1,2,6,16,... that is 1,0 followed by this sequence here. - _R. J. Mathar_, Nov 08 2008

%C a(n) is the number of lattice paths avoiding N^(>=3) from (0,0) to (n,n). - _Shanzhen Gao_, Apr 20 2010

%C a(n+1) is the number of binary strings having n 0's and n 1's and no appearance of 000. For example, for n = 1, there 2 strings: 01 and 10. For n = 2, there are 6: 0011, 0101, 0110, 1001, 1010, 1100. - _Toby Gottfried_, Sep 12 2011

%C a(n) is the number of paths in the half-plane x>=0, from (0,0) to (n,1), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=3, we have the 6 paths HHU, HUH, UDU, UUD, UHH, DUU. - _José Luis Ramírez Ramírez_, Apr 19 2015

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H G. C. Greubel, <a href="/A005717/b005717.txt">Table of n, a(n) for n = 1..1000</a>[Terms 1 to 200 computed by T. D. Noe; terms 201 to 1000 by G. C. Greubel, Jan 15 2017]

%H Kassie Archer and Christina Graves, <a href="https://arxiv.org/abs/2205.09686">A new statistic on Dyck paths for counting 3-dimensional Catalan words</a>, arXiv:2205.09686 [math.CO], 2022.

%H Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, <a href="https://arxiv.org/abs/2401.06228">The Combinatorics of Motzkin Polyominoes</a>, arXiv:2401.06228 [math.CO], 2024. See page 13.

%H Emeric Deutsch, <a href="https://doi.org/10.1016/j.disc.2003.10.021">Ordered trees with prescribed root degrees, node degrees, and branch lengths</a>, Discrete Mathematics 282 (2004), 89-94.

%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 23.

%H Richard K. Guy, <a href="/A005712/a005712.pdf">Letter to N. J. A. Sloane, 1987</a>

%H Stanislav Krymski and Alexander Okhotin, <a href="https://doi.org/10.1007/978-3-030-62536-8_9">Longer Shortest Strings in Two-Way Finite Automata</a>, in: Jirásková G., Pighizzini G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science, vol 12442. Springer, Cham.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="http://arxiv.org/abs/0912.0072">Une méthode pour obtenir la fonction génératrice d'une série</a>, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.

%H Chenying Wang, Piotr Miska, and István Mező, <a href="https://doi.org/10.1016/j.disc.2016.10.012">The r-derangement numbers</a>, Discrete Mathematics 340(7) (2017), 1681-1692.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TrinomialCoefficient.html">Trinomial Coefficient</a>

%F a(n) = Sum_{k=1..n} T(k, k-1), where T is the array defined in A025177.

%F G.f.: 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2)). - _Emeric Deutsch_, Aug 14 2002

%F E.g.f.: exp(x) * I_1(2x), where I_1 is the Bessel function. - _Michael Somos_, Sep 09 2002

%F a(n) = A111808(n,n-1). - _Reinhard Zumkeller_, Aug 17 2005

%F a(n) = Sum_{k=0..floor((n-1)/3)} (-1)^k * binomial(n,k) * binomial(2n-2-3k, n-1). - _David Callan_, Jul 03 2006

%F From _Paul Barry_, Feb 05 2007: (Start)

%F a(n) = n*Sum_{k=0..floor((n-1)/2), C(n-1,2k)*C(k)}, C(n) = A000108(n).

%F a(n) = Sum_{k=0..floor((n-1)/2)} (2k+1)*C(n,2k+1)*C(k).

%F a(n) = Sum_{k=0..n-1} ( Sum_{j=0..floor(k/2)} C(k,2j)*C(2j+1,j) ). (End)

%F a(n) = (A002426(n+1) - A002426(n))/2. - _Paul Barry_, May 22 2008

%F a(n) = n*A001006(n-1). - _Paul Barry_, Oct 05 2009

%F a(n) = Sum_{i=0..floor(n/2)} C(n+1,n-i) * C(n-i,i). - _Shanzhen Gao_, Apr 20 2010

%F D-finite with recurrence: (n+1)*a(n) - 3*n*a(n-1) - (n+3)*a(n-2) + 3*(n-2)*a(n-3) = 0. - _R. J. Mathar_, Nov 28 2011

%F a(n) ~ 3^(n+1/2)/(2*sqrt(Pi*n)). - _Vaclav Kotesovec_, Aug 09 2013

%F 0 = a(n) * 3*(n+1)*(n+2) + a(n+1) * (n+2)*(2*n+3) - a(n+2) * (n+1)*(n+3) for all n in Z. - _Michael Somos_, Apr 03 2014

%F G.f.: z*M(z)/(1-z-2*z^2*M(z)), where M(z) is the g.f. of Motzkin paths. - _José Luis Ramírez Ramírez_, Apr 19 2015

%F Working with an offset of 0, a(n) = [x^n](1 + x + x^2)^(n+1); binomial transform is A076540. - _Peter Bala_, Jun 15 2015

%F a(n) = GegenbauerC(n,-n-1,-1/2). - _Peter Luschny_, May 07 2016

%F a(n) = (-1)^(n+1) * n * hypergeom([3/2, 1-n], [3], 4). - _Vladimir Reshetnikov_, Sep 28 2016

%F a(n) = Sum_{k=0..n-1} binomial(n,k)*binomial(n-k, k+1) [Krymski and Okhotin]. - _Michel Marcus_, Dec 04 2020

%F a(n) = (1/2)*(A005773(n+1) - A005043(n)). - _Peter Bala_, Feb 11 2022

%e G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 45*x^5 + 126*x^6 + 357*x^7 + ...

%p seq(add(binomial(i, k) *binomial(i-k, k+1), k=0..floor(i/2)), i=1..30); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001

%p M:= proc(n) option remember; `if` (n<2, 1, (3*(n-1)*M(n-2) +(2*n+1) *M(n-1))/ (n+2)) end: A005717 := n -> n*M(n-1):

%p seq(A005717(i), i=1..27); # _Peter Luschny_, Sep 12 2011

%p a := n -> simplify(GegenbauerC(n,-n-1,-1/2)):

%p seq(a(n), n=0..28); # _Peter Luschny_, May 07 2016

%t Table[Coefficient[Expand[(1+x+x^2)^n], x, n-1], {n, 1, 40}]

%t Table[n*Hypergeometric2F1[(1 - n)/2, 1 - n/2, 2, 4], {n, 29}] (* _Arkadiusz Wesolowski_, Aug 13 2012 *)

%t Table[GegenbauerC[n,-n-1,-1/2],{n,0,100}] (* _Emanuele Munarini_, Oct 20 2016 *)

%o (PARI) {a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n-1))}; /* _Michael Somos_, Sep 09 2002 */

%o (PARI) {a(n) = if( n<0, 0, n * polcoeff( serreverse( x / (1 + x + x^2) + x * O(x^n)), n))}; /* _Michael Somos_, Oct 10 2003 */

%o (PARI)

%o N=10^3; x='x+'x*O('x^N);

%o gf = 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2));

%o v005717 = Vec(gf);

%o /* _Joerg Arndt_, Aug 16 2012 */

%o (Sage, Python)

%o def A():

%o a, b, n = 0, 1, 1

%o while True:

%o yield b

%o n += 1

%o a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))

%o A005717 = A()

%o print([next(A005717) for _ in range(29)]) # _Peter Luschny_, May 16 2016

%o (Maxima) makelist(ultraspherical(n,-n-1,-1/2),n,0,12); /* _Emanuele Munarini_, Oct 20 2016 */

%Y A diagonal of A027907.

%Y Cf. A001006, A002426, A005043, A005773, A076540 (binomial transform).

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Erich Friedman_, Jun 01 2001

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)