A105633 - OEIS

%I #117 Mar 07 2023 11:06:44

%S 1,2,4,9,22,57,154,429,1223,3550,10455,31160,93802,284789,871008,

%T 2681019,8298933,25817396,80674902,253106837,796968056,2517706037,

%U 7977573203,25347126630,80738862085,257778971504,824798533933

%N Row sums of triangle A105632.

%C Binomial transform of A007477. INVERT transform of A082582. First differences give A086581 and A025242 (offset 1). Is this sequence equal to A057580?

%C a(n) = the number of Dyck paths of semilength n+1 avoiding UUDU. a(n) = the number of Dyck paths of semilength n+1 avoiding UDUU = the number of binary trees without zigzag (i.e., with no node with a father, with a right son and with no left son). This sequence is the first column of the triangle A116424. E.g., a(2) = 4 because there exist four Dyck paths of semilength 3 that avoid UUDU: UDUDUD, UDUUDD, UUDDUD, UUUDDD, as well as four Dyck paths of semilength 3 that avoid UDUU: UDUDUD, UUDUDD, UUDDUD, UUUDDD. - I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006

%C The sequence beginning 1,1,2,4,9,... gives the diagonal sums of A130749, and has g.f. 1/(1-x-x^2/(1-x/(1-x-x^2/(1-x/(1-x-x^2/(1-... (continued fraction); and general term Sum_{k=0..floor(n/2)} Sum_{j=0..n-k} binomial(n-k,j)*A090181(j,k). Its Hankel transform is A099443(n+1). - _Paul Barry_, Jun 30 2009

%C The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al. - _Kellen Myers_, Jun 15 2015

%C a(n) = the number of Dyck paths of semilength n+1 with no pairs of

%C consecutive valleys at the same height. _Sergi Elizalde_, Feb 25 2021

%H Vincenzo Librandi, <a href="/A105633/b105633.txt">Table of n, a(n) for n = 0..1000</a>

%H Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

%H Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, <a href="https://doi.org/10.37236/9482">Permutations avoiding a simsun pattern</a>, The Electronic Journal of Combinatorics (2020) Vol. 27, Issue 3, P3.45. (See a_n in Theorem 4.)

%H Jean-Luc Baril, Daniela Colmenares, José L. Ramírez, Emmanuel D. Silva, Lina M. Simbaqueba, and Diana A. Toquica, <a href="http://jl.baril.u-bourgogne.fr/bacorasisito.pdf">Consecutive pattern-avoidance in Catalan words according to the last symbol</a>, Univ. Bourgogne (France 2023).

%H Jean-Luc Baril and José Luis Ramírez, <a href="https://arxiv.org/abs/2302.12741">Descent distribution on Catalan words avoiding ordered pairs of Relations</a>, arXiv:2302.12741 [math.CO], 2023.

%H Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.

%H Maciej Bendkowski, <a href="https://maciejbendkowski.staff.tcs.uj.edu.pl/thesis/quantitative-aspects-and-generation-of-random-lambda-and-combinatory-logic-terms.pdf">Quantitative aspects and generation of random lambda and combinatory logic terms</a>, Ph.D. Thesis, Jagiellonian University, Kraków, 2017.

%H Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, <a href="http://arxiv.org/abs/1609.08106">Combinatorics of λ-terms: a natural approach</a>, arXiv:1609.08106 [cs.LO], 2016.

%H Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, <a href="http://arxiv.org/abs/1506.02367">A Natural Counting of Lambda Terms</a>, arXiv preprint arXiv:1506.02367 [cs.LO], 2015.

%H Maciej Bendkowski, K. Grygiel, and P. Tarau, <a href="http://arxiv.org/abs/1612.07682">Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers</a>, arXiv preprint arXiv:1612.07682 [cs.LO], 2016-2017.

%H David Callan, <a href="https://arxiv.org/abs/1911.02209">On Ascent, Repetition and Descent Sequences</a>, arXiv:1911.02209 [math.CO], 2019.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%H Juan B. Gil and Michael D. Weiner, <a href="https://arxiv.org/abs/1812.01682">On pattern-avoiding Fishburn permutations</a>, arXiv:1812.01682 [math.CO], 2018.

%H K. Grygiel and P. Lescanne, <a href="http://perso.ens-lyon.fr/pierre.lescanne/PUBLICATIONS/natural_counting.pdf">A natural counting of lambda terms</a>, Preprint 2015.

%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.

%H Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

%H A. Sapounakis et al., <a href="http://dx.doi.org/10.1016/j.disc.2006.03.044">Ordered trees and the inorder transversal</a>, Disc. Math., 306 (2006), 1732-1741.

%F G.f.: A(x) = (1-x - sqrt((1-x)^2 - 4*x^2/(1-x)))/(2*x^2).

%F a(n) = 2*a(n-1) + Sum_{i=1..n-2} a(i)*(a(n-1-i) - a(n-2-i)). a(n) = Sum_{i=0..floor(n/2)} (-1)^i * binomial(n+1-i,i) * binomial(2*(n+1)-3*i, n-2*i) /(n+1-i). - I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006

%F G.f.: (1/(1-x)^2)c(x^2/(1-x)^3), where c(x) is the g.f. of A000108. - _Paul Barry_, May 22 2009

%F 1/(1-x-x/(1-x^2/(1-x-x/(1-x^2/(1-x-x/(1-x^2/(1-... (continued fraction). - _Paul Barry_, Jun 30 2009

%F a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-k} binomial(n-k,j)(0^(j+k)+(1/(j+0^j))*binomial(j,k)*binomial(j,k+1)). - _Paul Barry_, Jun 30 2009

%F G.f. satisfies: A(x) = (1 + x*A(x)) * (1 + x*(1-x)*A(x)). - _Paul D. Hanna_, Sep 12 2012

%F G.f.: exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * (1-x)^k ). - _Paul D. Hanna_, Sep 12 2012

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

%F The recurrence is true, since by holonomic transformation, it can be computed formally using GFUN, associated with the equation: x^3 + x^2 - 2x + (x^3 + 3 x^2 -3x +1) A(x) + (x^5 + 2x^3 -4 x^2 + x) A'(x) = 0. - _Pierre Lescanne_, Jun 30 2015

%F G.f.: (1 - 1/(G(0)-x))/x^2 where G(k) =  1 + x/(1 + x/(x^2 - 1/G(k+1) )); (recursively defined continued fraction). - _Sergei N. Gladkovskii_, Dec 16 2012

%F a(n) ~ 2^(n/3-1/6) * 3^(n+2) * (13+3*sqrt(33))^((n+1)/3) * sqrt(4*(2879 + 561*sqrt(33))^(1/3) + 8*(7822 + 1362*sqrt(33))^(1/3) - 91 - 21*sqrt(33)) / (((26+6*sqrt(33))^(2/3) - (26+6*sqrt(33))^(1/3) - 8)^(n+3/2) * (4*(26+6*sqrt(33))^(1/3) - (26+6*sqrt(33))^(2/3) + 8) * n^(3/2) * sqrt(Pi)). - _Vaclav Kotesovec_, Mar 13 2014

%F a(n) = Sum_{i=0..n+1} (-1)^i*hypergeom([(i+1)/2, i/2+1, i-n-1], [1, 2], -4). - _Peter Luschny_, May 03 2018

%e G.f.: A(x) = 1 + 2*x + 4*x^2 + 9*x^3 + 22*x^4 + 57*x^5 + 154*x^6 + 429*x^7 + ...

%e with A(x)^2 = 1 + 4*x + 12*x^2 + 34*x^3 + 96*x^4 + 274*x^5 + 793*x^6 + ...

%e where A(x) = 1 + x*(2-x)*A(x) + x^2*(1-x)*A(x)^2.

%e The logarithm of the g.f. begins:

%e log(A(x)) = (1 + (1-x))*x + (1 + 2^2*(1-x) + (1-x)^2)*x^2/2 +

%e (1 + 3^2*(1-x) + 3^2*(1-x)^2 + (1-x)^3)*x^3/3 +

%e (1 + 4^2*(1-x) + 6^2*(1-x)^2 + 4^2*(1-x)^3 + (1-x)^4)*x^4/4 +

%e (1 + 5^2*(1-x) + 10^2*(1-x)^2 + 10^2*(1-x)^3 + 5^2*(1-x)^4 + (1-x)^5)*x^5/5 + ...

%e Explicitly,

%e log(A(x)) = 2*x + 4*x^2/2 + 11*x^3/3 + 32*x^4/4 + 97*x^5/5 + 301*x^6/6 + 947*x^7/7 + 3008*x^8/8 + 9623*x^9/9 + 30959*x^10/10 + ...

%p a := n -> add((-1)^i*hypergeom([(i+1)/2, i/2+1, i-n-1], [1, 2], -4), i=0..n+1):

%p seq(simplify(a(n)), n=0..26); # _Peter Luschny_, May 03 2018

%t CoefficientList[Series[(1 - x - Sqrt[(1 - x)^2 - 4 x^2/(1 - x)])/(2 x^2), {x, 0, 40}], x] (* _Vincenzo Librandi_, Mar 15 2014 *)

%o (PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(2/(1-X)/(1-X+sqrt((1-X)^2-4*X^2/(1-X))),n,x)}

%o (PARI) {a(n)=polcoeff(exp(sum(m=1,n+1,x^m/m*sum(k=0,m,binomial(m,k)^2*(1-x)^(m-k) + x*O(x^n)))),n)} \\ _Paul D. Hanna_, Sep 12 2012

%Y Cf. A105632, A057580, A116424, A216604. See also A258973.

%K nonn

%O 0,2

%A _Paul D. Hanna_, Apr 17 2005

%E More terms from I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006