|
%I #112 Mar 07 2023 11:06:17
%S 1,1,1,2,5,13,35,97,275,794,2327,6905,20705,62642,190987,586219,
%T 1810011,5617914,17518463,54857506,172431935,543861219,1720737981,
%U 5459867166,17369553427,55391735455,177040109419,567019562429,1819536774089
%N Expansion of (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) in powers of x.
%C a(n) is the number of Dyck paths of semilength n with no UUDD. See A025242 for a bijection between paths avoiding DDUU versus UUDD.
%C Also number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k>=1. - _Alois P. Heinz_, Oct 07 2015
%C a(n) is the number of bargraphs of semiperimeter n (n>=2). Example: a(4) = 5; the 5 bargraphs correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3]. - _Emeric Deutsch_, May 20 2016 [a(n) are the row sums of A271942 for n >= 2. _Peter Luschny_, Oct 18 2020]
%C a(n) is the number of skew Motzkin paths of length n. A skew Motzkin path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down), F=(1,0) (flat) and A=(-1,1) (anti-down) so that down and anti-down steps do not overlap. - _Sergey Kirgizov_, Oct 03 2018
%C From _Gus Wiseman_, Jul 04 2019: (Start)
%C Conjecture: Also the number of maximal simple graphs with vertices {1..n} and no weakly nesting edges. Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. For example, the a(1) = 1 through a(5) = 13 edge-sets are:
%C {} {12} {13} {14} {15}
%C {12,23} {12,24} {12,25}
%C {13,24} {13,25}
%C {13,34} {14,25}
%C {12,23,34} {14,35}
%C {14,45}
%C {12,23,35}
%C {12,24,35}
%C {12,24,45}
%C {13,24,35}
%C {13,24,45}
%C {13,34,45}
%C {12,23,34,45}
%C Cf. A006125, A054726, A117662, A326244, A326257, A326289, A326293, A326329, A326337, A326338, A326340.
%C (End)
%C a(n) is the number of Dyck n-paths in which no nonterminal descent has the same length as the preceding ascent. Example: a(3) = 2 counts UUDUDD and UUUDDD where the latter path qualifies because DDD is the terminal descent. - _David Callan_, Dec 14 2021
%H Reinhard Zumkeller, <a href="/A082582/b082582.txt">Table of n, a(n) for n = 0..1000</a>
%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 A. Blecher, C. Brennan, and A. Knopfmacher, <a href="http://dx.doi.org/10.1080/0035919X.2015.1059905">Peaks in bargraphs</a>, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.
%H Miklos Bona and Elijah DeJonge, <a href="https://arxiv.org/abs/2003.10640">Pattern avoiding permutations and involutions with a unique longest increasing subsequence</a>, arXiv:2003.10640 [math.CO], 2020.
%H M. Bousquet-Mélou and A. Rechnitzer, <a href="https://doi.org/10.1016/S0196-8858(02)00553-5">The site-perimeter of bargraphs</a>, Adv. in Appl. Math. 31 (2003), 86-112.
%H Ralph L. Childress, <a href="https://arxiv.org/abs/2102.02777">Recursive Prime Factorizations: Dyck Words as Numbers</a>, arXiv:2102.02777 [cs.FL], 2021.
%H Emeric Deutsch and Sergi Elizalde, <a href="http://arxiv.org/abs/1609.00088">Statistics on bargraphs viewed as cornerless Motzkin paths</a>, arXiv:1609.00088 [math.CO], September 2016.
%H Chris Dyer, Gábor Melis, and Phil Blunsom, <a href="https://arxiv.org/abs/1909.09428">A Critical Analysis of Biased Parsers in Unsupervised Parsing</a>, arXiv:1909.09428 [cs.CL], 2019.
%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-2019.
%H Qing Lin Lu, <a href="https://doi.org/10.1007/s10114-016-5292-y">Skew Motzkin paths</a>, Acta Mathematica Sinica, English Series, 33(5) (2017), 657-667.
%F G.f.: (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4)) / (2*x) = 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4)).
%F G.f. A(x) satisfies the equation 0 = 1 - (1 + x^2) * A(x) + x * A(x)^2. - _Michael Somos_, Jul 22 2003
%F G.f. A(x) satisfies A(x) = 1 / (1 + x^2 - x * A(x)). - _Michael Somos_, Mar 28 2011
%F G.f. A(x) = 1 / (1 + x^2 - x / (1 + x^2 - x / (1 + x^2 - ... ))) continued fraction. - _Michael Somos_, Jul 01 2011
%F Series reversion of x * A(x) is x * A007477(-x). - _Michael Somos_, Jul 22 2003
%F a(n+1) = a(n) + Sum(a(k)*a(n-k): k=2..n), a(0) = a(1) = 1. - _Reinhard Zumkeller_, Nov 13 2012
%F G.f.: 1 + x - x*G(0), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - _Sergei N. Gladkovskii_, Jul 12 2013
%F D-finite with recurrence: (n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4) = 0. - _Robert Israel_, May 20 2016
%F a(n) = Sum_{k=0..n-2} Sum_{j=0..n-k-1} C(n-k-2,j)*C(k,j)*C(k+j+2,j)/(j+1), n>1, a(0)=1, a(1)=1. - _Vladimir Kruchinin_, Oct 18 2020
%F a(n) = Sum_{k=0..n-2} HypergeometricPFQ[{-k, 3 +k, k - n + 2}, {1, 2}, 1] for n >= 2. - _Peter Luschny_, Oct 18 2020
%F a(n) ~ sqrt(2+r) / (2 * sqrt(Pi) * n^(3/2) * r^n), where r = 0.295597742522084... is the real root of the equation r^3 + r^2 + 3*r - 1 = 0. - _Vaclav Kotesovec_, Jun 05 2022
%F G.f.: 1/G(x), with G(x) = 1 - (x-x^2)/(1-x/G(x)) (continued fraction). - _Nikolaos Pantelidis_, Jan 11 2023
%e 1 + x + x^2 + 2*x^3 + 5*x^4 + 13*x^5 + 35*x^6 + 97*x^7 + 275*x^8 + ...
%e a(3)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - _Emeric Deutsch_, Jan 27 2003
%p f:= gfun:-rectoproc({(n-1)*a(n)+(2*n+4)*a(n+2)+(-14-4*n)*a(n+3)+(5+n)*a(n+4), a(0) = 1, a(1) = 1, a(2) = 1, a(3) = 2},a(n),remember):
%p map(f,[$0..100]); # _Robert Israel_, May 20 2016
%t a[0]=1;a[n_Integer]:=a[n]=a[n-1]+Sum[a[k]*a[n-1-k],{k,2,n-1}];Table[a[n],{n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Mar 30 2011 *)
%t a[ n_] := SeriesCoefficient[ 2 / (1 + x^2 + Sqrt[1 - 4 x + 2 x^2 + x^4]), {x, 0, n}] (* _Michael Somos_, Jul 01 2011 *)
%t a[n_] := Sum[HypergeometricPFQ[{-k, 3 + k, k - n}, {1, 2}, 1], {k, 0, n}];
%t Join[{1, 1}, Table[a[n], {n, 0, 26}]] (* _Peter Luschny_, Oct 18 2020 *)
%o (PARI) {a(n) = polcoeff( (1 + x^2 - sqrt( 1 - 4*x + 2*x^2 + x^4 + x^2 * O(x^n))) / 2, n+1)} /* _Michael Somos_, Jul 22 2003 */
%o (PARI) {a(n) = if( n<0, 0, polcoeff( 2 /(1 + x^2 + sqrt( 1 - 4*x + 2*x^2 + x^4 + x * O(x^n))),n))} /* _Michael Somos_, Jul 01 2011 */
%o (PARI) {a(n) = local(A); if( n<0, 0, A = O(x); for( k = 0, n, A = 1 / (1 + x^2 - x * A)); polcoeff( A, n))} /* _Michael Somos_, Mar 28 2011 */
%o (Haskell)
%o a082582 n = a082582_list !! n
%o a082582_list = 1 : 1 : f [1,1] where
%o f xs'@(x:_:xs) = y : f (y : xs') where
%o y = x + sum (zipWith (*) xs' $ reverse xs)
%o -- _Reinhard Zumkeller_, Nov 13 2012
%o (Maxima)
%o a(n):=sum(sum((binomial(n-k-2,j)*binomial(k,j)*binomial(k+j+2,j))/(j+1),j,0,n-k-1),k,0,n-2); /* _Vladimir Kruchinin_, Oct 18 2020 */
%Y Apart from initial term, same as A025242.
%Y See A086581 for Dyck paths avoiding DDUU.
%Y Cf. A000108, A218321, A263316, A271942 (refinement).
%K easy,nonn
%O 0,4
%A _Emanuele Munarini_, May 07 2003
|
