A127632 Expansion of c(x*c(x)), where c(x) is the g.f. for A000108.

1, 1, 3, 11, 44, 185, 804, 3579, 16229, 74690, 347984, 1638169, 7780876, 37245028, 179503340, 870374211, 4243141332, 20786340271, 102275718924, 505235129250, 2504876652190, 12459922302900, 62167152967680, 311040862133625

Offset: 0

Author

Paul Barry, Jan 20 2007, Jan 25 2007

Keywords

• easy
• nonn

Comments

Old name was: Expansion of 1/(1 - x*c(x) * c(x*c(x))), where c(x) is the g.f. of A000108.

Hankel transform appears to be A075845.

Catalan transform of Catalan numbers. - Philippe Deléham, Jun 20 2007

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

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

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

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

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• K. Archer and C. Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.
• J.-C. Aval and F. Chapoton, Poset structures on (m+2)-angulations and polynomial bases of the quotient by Gm-quasisymmetric functions, Séminaire Lotharingien de Combinatoire, vol 77, article B77b.
• Peter Bala, A note on the Catalan transform of a sequence
• Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
• David Callan, A combinatorial interpretation of the Catalan transform of the Catalan numbers, arXiv:1111.0996 [math.CO], 2011.
• David Callan, Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193 [math.CO], 2013.
• S. Csar, R. Sengupta, and W. Suksompong, On a Subposet of the Tamari Lattice, arXiv preprint arXiv:1108.5690 [math.CO], 2011.
• Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.
• Tian-Xiao He and Louis W. Shapiro, Row sums and alternating sums of Riordan arrays, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95.
• Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
• J. M. Pallo, Right-arm rotation distance between binary trees, Inform. Process. Lett., 87(4):173-177, 2003.
• Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832, table 1, {ud}.
• S. Yakoubov, Pattern Avoidance in Extensions of Comb-Like Posets, arXiv preprint arXiv:1310.2979 [math.CO], 2013.

Crossrefs

Row sums of number triangle A127631.

Cf. A127714, A075845, A000108, A009766, A344056, A344057, A121988.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, [1, 1, 3][n+1],
      ((8*(4*n-11))*(4*n-5)*(4*n-9)*(2*n-5)*a(n-3)
      -(8*(4*n-5))*(n-1)*(22*n^2-94*n+99)*a(n-2)
      +8*n*(n-1)*(20*n^2-67*n+48)*a(n-1))/
      ((3*(4*n-9))*(n+1)*n*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 06 2015

Mathematica

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 *)
a[n_] := CatalanNumber[n - 1] HypergeometricPFQ[{3/2, 2, 1 - n}, {3, 2 - 2 n}, 4];
a[0] := 1; Table[a[n], {n, 0, 23}] (* Peter Luschny, May 12 2021 *)

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 */

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 */

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 */

Formula

a(n) = A127714(n+1, 2n+1).

G.f. A(x) satisfies: 0 = 1 - A(x) + A(x)^2 * x * c(x) where c(x) is the g.f. of A000108.

G.f.: 2/(1 + sqrt(2 * sqrt(1 - 4*x) - 1)). - Michael Somos, May 04 2007

a(n) = Sum_{k=0..n} A106566(n, k)*A000108(k). - Philippe Deléham, Jun 20 2007

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

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

a(n) ~ 2^(4*n - 1/2) / (sqrt(Pi) * n^(3/2) * 3^(n - 1/2)). - Vaclav Kotesovec, Aug 14 2018

From Alexander Burstein, Nov 21 2019: (Start)

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.

G.f.: A(x) satisfies: A(-x*A(x)^5) = 1/A(x). (End)

From Peter Luschny, May 12 2021: (Start)

a(n) = Catalan(n - 1) * hypergeom([3/2, 2, 1 - n], [3, 2 - 2*n], 4) for n >= 1.

a(n) = A344056(n) / A344057(n). (End)

The G.f. satisfies the algebraic equation 0 = F^4*x - F^3 + 2*F^2 - 2*F + 1. - F. Chapoton, Oct 18 2021

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

Extensions

Better name from David Callan, Jun 03 2013