cp's OEIS Frontend

A049124 Revert transform of (-1 + x + x^2)/((x - 1)*(x + 1)).

%I A049124 #110 Aug 23 2022 13:26:22
%S A049124 1,1,2,6,20,71,264,1015,4002,16094,65758,272208,1139182,4811807,
%T A049124 20487096,87832558,378846620,1642851797,7158220968,31323340342,
%U A049124 137595355130,606533278416,2682157911032,11895267124841,52895679368820,235792891885786,1053475824902774
%N A049124 Revert transform of (-1 + x + x^2)/((x - 1)*(x + 1)).
%C A049124 a(n) is the number of ways to dissect a convex (n+2)-gon with non-crossing diagonals so that no 2m-gons (m > 1) appear. - _Len Smiley_
%C A049124 Number of even trees (i.e., ordered trees in which all nodes have even outdegree) with n+1 leaves. - _Emeric Deutsch_, Mar 06 2002
%C A049124 a(n) is the number of permutations on [n-1] in which the last 2 entries of each 321 pattern are adjacent in position. For example, a(5)=20 counts all permutations on [4] except 3241, 4231, 4312, 4321, the first, for instance because the 2 and 1 are not adjacent. - _David Callan_, Jul 20 2005
%C A049124 a(n) is the number of directed diagonally convex polyominoes with perimeter 2*n (this holds for every n > 1). - _Svjetlan Feretic_, Jul 11 2016
%C A049124 From _Colin Defant_, Sep 17 2018: (Start)
%C A049124 Let L(u,v) be the set of integer partitions whose Young diagrams fit inside a u by v rectangle. Given lambda in L(u,v), let E(lambda) be the number of partitions whose Young diagrams fit inside the Young diagram of lambda. Also, for 1 <= i <= v, let x_i(lambda)-1 be the number of parts of lambda of length v+1-i. Let x_{v+1}(lambda) = u+v+1-Sum_{i=1..v} x_i(lambda) so that (x_1(lambda),..., x_{v+1}(lambda)) is a composition of u+v+1 into v+1 parts. Let F(lambda) = Product_{i=1..v+1} Catalan(x_i(lambda)). We have a(n) = Sum_{k=0..n-2} Sum_{lambda in L(n-2k-2)} E(lambda) * F(lambda).
%C A049124 a(n) is the number of permutations of [n-1] that avoid the patterns 2341, 3241, 3412, and 3421.
%C A049124 a(n) is the number of permutations pi of [n-1] such that s(pi) avoids the patterns 231, 312, and 321, where s is West's stack-sorting map. (End)
%C A049124 a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {4>1, 1>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the fourth element is larger than the first element, which in turn is larger than the second element. - _Sergey Kitaev_, Dec 09 2020
%H A049124 Alois P. Heinz, <a href="/A049124/b049124.txt">Table of n, a(n) for n = 0..1000</a>
%H A049124 Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.
%H A049124 D. Birmajer, J. B. Gil, M. D. Weiner, <a href="http://arxiv.org/abs/1503.05242">Colored partitions of a convex polygon by noncrossing diagonals</a>, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
%H A049124 Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H A049124 Stoyan Dimitrov, <a href="https://arxiv.org/abs/2002.12322">On permutation patterns with constrained gap sizes</a>, arXiv:2002.12322 [math.CO], 2020.
%H A049124 S. Feretic and D. Svrtan, <a href="http://dx.doi.org/10.1016/S0012-365X(96)83012-3">Combinatorics of diagonally convex directed polyominoes</a>, Discrete Math. 157 (1996), 147-168.
%H A049124 Alice L. L. Gao, Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H A049124 Alice L. L. Gao, Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H A049124 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 A049124 Mizera, Sebastian <a href="https://doi.org/10.1007/JHEP08(2017)097">Combinatorics and topology of Kawai-Lewellen-Tye relations</a>  J. High Energy Phys. 2017, No. 8, Paper No. 97, 54 p. (2017).
%H A049124 L. Smiley, <a href="http://www.math.uaa.alaska.edu/~smiley/vsd2.html">Even-gon reference</a>
%H A049124 L. Smiley, <a href="https://arxiv.org/abs/math/9907057">Variants of Schroeder Dissections</a>, arXiv:math/9907057 [math.CO], 1999.
%H A049124 <a href="/index/Res#revert">Index entries for reversions of series</a>
%F A049124 G.f. satisfies: A(x) = x + A(x)^2/(1-A(x)^2); by Lagrange Inversion: A(x) = x + Sum_{n>=0} d^n/dx^n (x^2/(1-x^2))^(n+1)/(n+1)!, or: A(x) = Sum_{n>=0} Sum_{k>=n} C(k-1, k-n)*(2*k)!/(2*k-n+1)!*x^(2*k-n+1)/n!. - _Paul D. Hanna_, Mar 24 2004
%F A049124 a(n) = Sum_{k=0..floor((n-1)/2)} C(n-k-1, k)*C(2*n-2*k, n)/(n+1) for n > 0, with a(0)=1. - _Paul D. Hanna_, Dec 15 2004
%F A049124 D-finite with recurrence 5*n*(n+1)*(91*n^2 - 367*n + 348)*a(n) = 12*n*(182*n^3 - 825*n^2 + 1053*n - 328)*a(n-1) - 4*(91*n^4 - 549*n^3 + 971*n^2 - 453*n - 108)*a(n-2) + 6*(n-3)*(182*n^3 - 825*n^2 + 1092*n - 384)*a(n-3) - 4*(n-4)*(n-3)*(91*n^2 - 185*n + 72)*a(n-4). - _Vaclav Kotesovec_, Jul 29 2013
%F A049124 Lim_{n->infinity} a(n)^(1/n) = z, where z = 4.730576939379622... is the root of the equation 4 - 12*z + 4*z^2 - 24*z^3 + 5*z^4 = 0. - _Vaclav Kotesovec_, Jul 29 2013
%e A049124 a(2)=2 because one diagonal may be placed 2 ways in the quadrilateral (placing none is not allowed).
%e A049124 Generated from Fibonacci polynomials (A011973) and odd self-convolutions of Catalan numbers (A039599):
%e A049124 a(0) = 1*   1 = 1.
%e A049124 a(1) = 1*   1 = 1.
%e A049124 a(2) = 1*   2 + 0*   1/3 = 2.
%e A049124 a(3) = 1*   5 + 1*   3/3 = 6.
%e A049124 a(4) = 1*  14 + 2*   9/3 +  0*  1/5 = 20.
%e A049124 a(5) = 1*  42 + 3*  28/3 +  1*  5/5 = 71.
%e A049124 a(6) = 1* 132 + 4*  90/3 +  3* 20/5 + 0* 1/7 = 264.
%e A049124 a(7) = 1* 429 + 5* 297/3 +  6* 75/5 + 1* 7/7 = 1015.
%e A049124 a(8) = 1*1430 + 6*1001/3 + 10*275/5 + 4*35/7 + 0*1/9 = 4002.
%e A049124 This process is equivalent to the formula:
%e A049124 a(n) = Sum_{k=0..floor((n-1)/2)} C(n-k-1,n-2k-1)*C(2n-2k,n-2k)/(n+1).
%e A049124 The odd self-convolutions of Catalan numbers begin:
%e A049124 A000108^1: {1, 1,  2,  5,  14,  42,  132, 329, 1430, ...}
%e A049124 A000108^3: {1, 3,  9, 28,  90, 297, 1001, ...}
%e A049124 A000108^5: {1, 5, 20, 75, 275, ...}
%e A049124 A000108^7: {1, 7, 35, ...}
%p A049124 Order := 20; solve(series((A-A^2-A^3)/(1-A^2),A)=x,A);
%t A049124 a[n_] := (2^n*(2n-1)!!* HypergeometricPFQ[{1/2-n/2, 1/2-n/2, 1-n/2, -n/2}, {1/2-n, 1-n, -n}, -4])/(n! + n*n!); Table[a[n], {n, 0, 24}] (* _Jean-François Alcover_, Jul 25 2011, after _Paul D. Hanna_ *)
%o A049124 (PARI) {a(n)=polcoeff(sum(m=0,n,sum(k=0,n, binomial(k+m-1,k)*binomial(2*k+2*m,m)*x^(2*k+m+1)/(2*k+m+1))),n)}
%o A049124 (PARI) {a(n)=if(n==0,1,sum(k=0,(n-1)\2,binomial(n-k-1,k)*binomial(2*n-2*k,n))/(n+1))} \\ _Paul D. Hanna_, Dec 15 2004
%Y A049124 Cf. A000108, A003168, A269228. Row sums of A319120.
%K A049124 nonn,easy,nice
%O A049124 0,3
%A A049124 _Olivier Gérard_
%E A049124 More terms from _Paul D. Hanna_, Dec 15 2004