|
%I #123 Aug 01 2022 09:40:24
%S 1,1,3,11,44,185,804,3579,16229,74690,347984,1638169,7780876,37245028,
%T 179503340,870374211,4243141332,20786340271,102275718924,505235129250,
%U 2504876652190,12459922302900,62167152967680,311040862133625
%N Expansion of c(x*c(x)), where c(x) is the g.f. for A000108.
%C Old name was: Expansion of 1/(1 - x*c(x) * c(x*c(x))), where c(x) is the g.f. of A000108.
%C Hankel transform appears to be A075845.
%C Catalan transform of Catalan numbers. - _Philippe Deléham_, Jun 20 2007
%C Number of functions f:[1,n] -> [1,n] satisfying the condition that, for all i < j, f(j) - (j - i) is not in the interval [1, f(i) - 1]; see the Callan reference. - _Joerg Arndt_, May 31 2013
%C This is the number of intervals in the comb posets of Pallo. See the Pallo and Csar et al. references for the definition of these posets. For the proof, see the Aval et al. reference - _F. Chapoton_, Apr 06 2015
%C Construct a lower triangular array (T(n,k))n,k>=0 by putting the sequence of Catalan numbers as the first column of the array and completing the remaining columns using the recurrence T(n, k) = T(n, k-1) + T(n-1, k). This sequence will then be the leading diagonal of the array. - _Peter Bala_, May 13 2017
%C a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 231 and 4132. (A permutation is called uniquely sorted if it has exactly one preimage under West's stack-sorting map. See the Defant link.) - _Colin Defant_, Jun 08 2019
%C a(n) is the number of 132-avoiding permutations of length 3*n whose disjoint cycle decomposition contains only 3-cycles (a,b,c) with a>b>c. See the Archer and Graves reference. - _Alexander Burstein_, Oct 21 2021
%H Alois P. Heinz, <a href="/A127632/b127632.txt">Table of n, a(n) for n = 0..1000</a>
%H K. Archer and C. Graves, <a href="https://arxiv.org/abs/2104.12664">Pattern-restricted permutations composed of 3-cycles</a>, arXiv:2104.12664 [math.CO], 2021.
%H J.-C. Aval and F. Chapoton, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s77aval.html">Poset structures on (m+2)-angulations and polynomial bases of the quotient by Gm-quasisymmetric functions</a>, Séminaire Lotharingien de Combinatoire, vol 77, article B77b.
%H Peter Bala, <a href="/A001517/a001517.pdf">A note on the Catalan transform of a sequence</a>
%H Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%H David Callan, <a href="http://arxiv.org/abs/1111.0996">A combinatorial interpretation of the Catalan transform of the Catalan numbers</a>, arXiv:1111.0996 [math.CO], 2011.
%H David Callan, <a href="https://arxiv.org/abs/1306.3193">Permutations avoiding 4321 and 3241 have an algebraic generating function</a>, arXiv:1306.3193 [math.CO], 2013.
%H S. Csar, R. Sengupta, and W. Suksompong, <a href="http://arxiv.org/abs/1108.5690">On a Subposet of the Tamari Lattice</a>, arXiv preprint arXiv:1108.5690 [math.CO], 2011.
%H Colin Defant, <a href="https://arxiv.org/abs/1904.02627">Catalan Intervals and Uniquely Sorted Permutations</a>, arXiv:1904.02627 [math.CO], 2019.
%H Tian-Xiao He and Louis W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2016.05.035">Row sums and alternating sums of Riordan arrays</a>, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95.
%H Hanna Mularczyk, <a href="https://arxiv.org/abs/1908.04025">Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations</a>, arXiv:1908.04025 [math.CO], 2019.
%H J. M. Pallo, <a href="http://dx.doi.org/10.1016/S0020-0190(03)00283-7">Right-arm rotation distance between binary trees</a>, Inform. Process. Lett., 87(4):173-177, 2003.
%H Y. Sun and Z. Wang, <a href="http://dx.doi.org/10.1007/s00373-010-0950-9">Consecutive pattern avoidances in non-crossing trees</a>, Graph. Combinat. 26 (2010) 815-832, table 1, {ud}.
%H S. Yakoubov, <a href="http://arxiv.org/abs/1310.2979">Pattern Avoidance in Extensions of Comb-Like Posets</a>, arXiv preprint arXiv:1310.2979 [math.CO], 2013.
%F a(n) = A127714(n+1, 2n+1).
%F G.f. A(x) satisfies: 0 = 1 - A(x) + A(x)^2 * x * c(x) where c(x) is the g.f. of A000108.
%F G.f.: 2/(1 + sqrt(2 * sqrt(1 - 4*x) - 1)). - _Michael Somos_, May 04 2007
%F a(n) = Sum_{k=0..n} A106566(n, k)*A000108(k). - _Philippe Deléham_, Jun 20 2007
%F a(n) = (Sum_{m=1..n} (m*Sum_{k=m..n} binomial(2*k-m-1, k-1)*binomial(2*n-k-1, n-1)))/n, a(0)=1. - _Vladimir Kruchinin_, Oct 08 2011
%F Conjecture: 3*n*(n-1)*(4*n-9)*(n+1)*a(n) - 8*n*(n-1)*(20*n^2-67*n+48)*a(n-1) + 8*(4*n-5)*(n-1)*(22*n^2-94*n+99)*a(n-2) - 8*(4*n-11)*(4*n-5)*(4*n-9)*(2*n-5)*a(n-3) = 0. - _R. J. Mathar_, May 04 2018
%F a(n) ~ 2^(4*n - 1/2) / (sqrt(Pi) * n^(3/2) * 3^(n - 1/2)). - _Vaclav Kotesovec_, Aug 14 2018
%F From _Alexander Burstein_, Nov 21 2019: (Start)
%F G.f.: A(x) = 1 + x*c(x)^2*m(x*c(x)^2), where m(x) is the g.f. of A001006 and c(x) is the g.f. of A000108.
%F G.f.: A(x) satisfies: A(-x*A(x)^5) = 1/A(x). (End)
%F From _Peter Luschny_, May 12 2021: (Start)
%F a(n) = Catalan(n - 1) * hypergeom([3/2, 2, 1 - n], [3, 2 - 2*n], 4) for n >= 1.
%F a(n) = A344056(n) / A344057(n). (End)
%F The G.f. satisfies the algebraic equation 0 = F^4*x - F^3 + 2*F^2 - 2*F + 1. - _F. Chapoton_, Oct 18 2021
%F D-finite with recurrence 3*n*(n-1)*(n+1)*a(n) -4*n*(7*n-2)*(n-1)*a(n-1) +8*(n-1)*(2*n^2+30*n-65)*a(n-2) +8*(56*n^3-520*n^2+1534*n-1445)*a(n-3) -32*(4*n-15)*(2*n-7)*(4*n-13)*a(n-4)=0. - _R. J. Mathar_, Aug 01 2022
%p a:= proc(n) option remember; `if`(n<3, [1, 1, 3][n+1],
%p ((8*(4*n-11))*(4*n-5)*(4*n-9)*(2*n-5)*a(n-3)
%p -(8*(4*n-5))*(n-1)*(22*n^2-94*n+99)*a(n-2)
%p +8*n*(n-1)*(20*n^2-67*n+48)*a(n-1))/
%p ((3*(4*n-9))*(n+1)*n*(n-1)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Apr 06 2015
%t a[n_] := Sum[m*(2*n-m-1)!*HypergeometricPFQ[{m/2+1/2, m/2, m-n}, {m, m-2*n+1}, 4]/(n!*(n-m)!), {m, 1, n}]; a[0]=1; Table[a[n], {n, 0, 23}] (* _Jean-François Alcover_, Jul 24 2012, after _Vladimir Kruchinin_ *)
%t a[n_] := CatalanNumber[n - 1] HypergeometricPFQ[{3/2, 2, 1 - n}, {3, 2 - 2 n}, 4];
%t a[0] := 1; Table[a[n], {n, 0, 23}] (* _Peter Luschny_, May 12 2021 *)
%o (PARI) {a(n)= if(n<1, n==0, polcoeff( serreverse( x*(1-x)^3*(1-x^3)/(1-x^2)^4 +x*O(x^n) ), n))} /* _Michael Somos_, May 04 2007 */
%o (PARI) {a(n)= local(A); if(n<1, n==0, A= serreverse( x-x^2 +x*O(x^n) ); polcoeff( 1/(1 - subst(A, x, A)), n))} /* _Michael Somos_, May 04 2007 */
%o (Maxima) a(n):=if n=0 then 1 else sum(m*sum(binomial(2*k-m-1,k-1)*binomial(2*n-k-1,n-1),k,m,n),m,1,n)/n; \\ _Vladimir Kruchinin_, Oct 08 2011
%Y Row sums of number triangle A127631.
%Y Cf. A127714, A075845, A000108, A009766, A344056, A344057, A121988.
%K easy,nonn
%O 0,3
%A _Paul Barry_, Jan 20 2007, Jan 25 2007
%E Better name from _David Callan_, Jun 03 2013
| 