cp's OEIS Frontend

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

%I A005717 M1612 #214 Aug 24 2025 06:26:59
%S A005717 1,2,6,16,45,126,357,1016,2907,8350,24068,69576,201643,585690,1704510,
%T A005717 4969152,14508939,42422022,124191258,363985680,1067892399,3136046298,
%U A005717 9217554129,27114249960,79818194925,235128465026,693085098852,2044217638456,6032675068061
%N A005717 Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.
%C A005717 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 A005717 The connection to Motzkin numbers comes from the Lagrange inversion formula. - _Michael Somos_, Oct 10 2003
%C A005717 Number of horizontal steps in all Motzkin paths of length n. - _Emeric Deutsch_, Nov 09 2003
%C A005717 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 A005717 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 A005717 a(n) is the number of Dyck (n+1)-paths containing exactly one UDU. - _David Callan_, Jul 15 2004
%C A005717 Number of peaks in all Motzkin paths of length n+1. - _Emeric Deutsch_, Sep 01 2004
%C A005717 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 A005717 a(n) is the number of lattice paths avoiding N^(>=3) from (0,0) to (n,n). - _Shanzhen Gao_, Apr 20 2010
%C A005717 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 A005717 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
%C A005717 a(n) is the number of ways to tile a strip of length 2*n+1 with squares, dominos, and trominos, where the number of trominos is always one more than the number of squares. - _Greg Dresden_ and Anna Kalynchuk, Jul 30 2025
%D A005717 Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
%D A005717 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005717 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 A005717 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 A005717 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 A005717 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 A005717 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 A005717 Richard K. Guy, <a href="/A005712/a005712.pdf">Letter to N. J. A. Sloane, 1987</a>.
%H A005717 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 A005717 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 A005717 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 A005717 Mark Shattuck, <a href="https://doi.org/10.54550/ECA2024V4S4R32">Subword Patterns in Smooth Words</a>, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.
%H A005717 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 A005717 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TrinomialCoefficient.html">Trinomial Coefficient</a>.
%F A005717 a(n) = Sum_{k=1..n} T(k, k-1), where T is the array defined in A025177.
%F A005717 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 A005717 E.g.f.: exp(x) * I_1(2x), where I_1 is the Bessel function. - _Michael Somos_, Sep 09 2002
%F A005717 a(n) = A111808(n,n-1). - _Reinhard Zumkeller_, Aug 17 2005
%F A005717 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 A005717 From _Paul Barry_, Feb 05 2007: (Start)
%F A005717 a(n) = n*Sum_{k=0..floor((n-1)/2), C(n-1,2k)*C(k)}, C(n) = A000108(n).
%F A005717 a(n) = Sum_{k=0..floor((n-1)/2)} (2k+1)*C(n,2k+1)*C(k).
%F A005717 a(n) = Sum_{k=0..n-1} ( Sum_{j=0..floor(k/2)} C(k,2j)*C(2j+1,j) ). (End)
%F A005717 a(n) = (A002426(n+1) - A002426(n))/2. - _Paul Barry_, May 22 2008
%F A005717 a(n) = n*A001006(n-1). - _Paul Barry_, Oct 05 2009
%F A005717 a(n) = Sum_{i=0..floor(n/2)} C(n+1,n-i) * C(n-i,i). - _Shanzhen Gao_, Apr 20 2010
%F A005717 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 A005717 a(n) ~ 3^(n+1/2)/(2*sqrt(Pi*n)). - _Vaclav Kotesovec_, Aug 09 2013
%F A005717 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 A005717 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 A005717 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 A005717 a(n) = GegenbauerC(n,-n-1,-1/2). - _Peter Luschny_, May 07 2016
%F A005717 a(n) = (-1)^(n+1) * n * hypergeom([3/2, 1-n], [3], 4). - _Vladimir Reshetnikov_, Sep 28 2016
%F A005717 a(n) = Sum_{k=0..n-1} binomial(n,k)*binomial(n-k, k+1) [Krymski and Okhotin]. - _Michel Marcus_, Dec 04 2020
%F A005717 a(n) = (1/2)*(A005773(n+1) - A005043(n)). - _Peter Bala_, Feb 11 2022
%F A005717 a(n) = A002426(n) - A005043(n). - _Amiram Eldar_, May 17 2024
%e A005717 G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 45*x^5 + 126*x^6 + 357*x^7 + ...
%p A005717 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 A005717 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 A005717 seq(A005717(i), i=1..27); # _Peter Luschny_, Sep 12 2011
%p A005717 a := n -> simplify(GegenbauerC(n,-n-1,-1/2)):
%p A005717 seq(a(n), n=0..28); # _Peter Luschny_, May 07 2016
%t A005717 Table[Coefficient[Expand[(1+x+x^2)^n], x, n-1], {n, 1, 40}]
%t A005717 Table[n*Hypergeometric2F1[(1 - n)/2, 1 - n/2, 2, 4], {n, 29}] (* _Arkadiusz Wesolowski_, Aug 13 2012 *)
%t A005717 Table[GegenbauerC[n,-n-1,-1/2],{n,0,100}] (* _Emanuele Munarini_, Oct 20 2016 *)
%o A005717 (PARI) {a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n-1))}; /* _Michael Somos_, Sep 09 2002 */
%o A005717 (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 A005717 (PARI)
%o A005717 N=10^3;  x='x+'x*O('x^N);
%o A005717 gf = 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2));
%o A005717 v005717 = Vec(gf);
%o A005717 /* _Joerg Arndt_, Aug 16 2012 */
%o A005717 (Python)
%o A005717 def A():
%o A005717     a, b, n = 0, 1, 1
%o A005717     while True:
%o A005717         yield b
%o A005717         n += 1
%o A005717         a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))
%o A005717 A005717 = A()
%o A005717 print([next(A005717) for _ in range(29)]) # _Peter Luschny_, May 16 2016
%o A005717 (Maxima) makelist(ultraspherical(n,-n-1,-1/2),n,0,12); /* _Emanuele Munarini_, Oct 20 2016 */
%Y A005717 A diagonal of A027907.
%Y A005717 Cf. A001006, A002426, A005043, A005773, A076540 (binomial transform).
%K A005717 nonn,easy,changed
%O A005717 1,2
%A A005717 _N. J. A. Sloane_
%E A005717 More terms from _Erich Friedman_, Jun 01 2001