A127714 -id:A127714 - cp's OEIS frontend

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

Paul Barry, Jan 20 2007, Jan 25 2007

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

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.

Row sums of number triangle A127631.

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

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

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

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

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

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

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

Better name from David Callan, Jun 03 2013

A152400 Triangle T, read by rows, where column k of T = column 0 of matrix power T^(k+1) for k>0, with column 0 of T = unsigned column 0 of T^-1 (shifted).

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 14, 8, 3, 1, 86, 45, 15, 4, 1, 645, 318, 99, 24, 5, 1, 5662, 2671, 794, 182, 35, 6, 1, 56632, 25805, 7414, 1636, 300, 48, 7, 1, 633545, 280609, 78507, 16844, 2990, 459, 63, 8, 1, 7820115, 3381993, 926026, 194384, 33685, 5026, 665, 80, 9, 1

Offset: 0

Paul D. Hanna, Dec 05 2008

			Triangle T begins:
1;
1, 1;
3, 2, 1;
14, 8, 3, 1;
86, 45, 15, 4, 1;
645, 318, 99, 24, 5, 1;
5662, 2671, 794, 182, 35, 6, 1;
56632, 25805, 7414, 1636, 300, 48, 7, 1;
633545, 280609, 78507, 16844, 2990, 459, 63, 8, 1;
7820115, 3381993, 926026, 194384, 33685, 5026, 665, 80, 9, 1;...
where column k of T = column 0 of T^(k+1) for k>0
and column 0 of T = unsigned column 0 of T^-1 (shifted).
Amazingly, column k of T^(j+1) = column j of T^(k+1) for j>=0, k>=0.
Matrix inverse T^-1 begins:
1;
-1, 1;
-1, -2, 1;
-3, -2, -3, 1;
-14, -7, -3, -4, 1;
-86, -37, -12, -4, -5, 1;
-645, -252, -71, -18, -5, -6, 1;...
where unsigned column 0 of T^-1 = column 0 of T (shifted).
Matrix square T^2 begins:
1;
2, 1;
8, 4, 1;
45, 22, 6, 1;
318, 152, 42, 8, 1;
2671, 1251, 345, 68, 10, 1;
25805, 11869, 3253, 648, 100, 12, 1;
280609, 126987, 34546, 6898, 1085, 138, 14, 1;...
where column 0 of T^2 = column 1 of T,
and column 2 of T^2 = column 1 of T^3.
Matrix cube T^3 begins:
1;
3, 1;
15, 6, 1;
99, 42, 9, 1;
794, 345, 81, 12, 1;
7414, 3253, 798, 132, 15, 1;
78507, 34546, 8679, 1518, 195, 18, 1;
926026, 407171, 103707, 18734, 2565, 270, 21, 1;...
where column 0 of T^3 = column 2 of T,
and column 3 of T^3 = column 2 of T^4.
Matrix power T^4 begins:
1;
4, 1;
24, 8, 1;
182, 68, 12, 1;
1636, 648, 132, 16, 1;
16844, 6898, 1518, 216, 20, 1;
194384, 81218, 18734, 2912, 320, 24, 1;
2476868, 1047638, 249202, 40932, 4950, 444, 28, 1;...
where column 0 of T^4 = column 3 of T,
and column 2 of T^4 = column 3 of T^3.
Related triangle A127714 begins:
1;
1, 1, 1;
1, 2, 2, 3, 3, 3;
1, 3, 5, 5, 8, 11, 11, 14, 14, 14;
1, 4, 9, 14, 14, 22, 33, 44, 44, 58, 72, 72, 86, 86, 86;...
where right border = column 0 of this triangle A152400.

Cf. columns: A127715, A152401, A152402, A152403, A152404.

Cf. related triangles: A152405, A127714.

T(n, k)=if(k>n || n<0,0, if(k==n,1, if(k==0,sum(j=1,n,T(n,j)*T(j-1,0)), sum(j=0,n-k,T(n-k, j)*T(j+k-1, k-1)));))

Column k of T^(j+1) = column j of T^(k+1) for all j>=0, k>=0.
Column k: T(n,k) = Sum_{j=0..n-k} T(n-k,j)*T(j+k-1,k-1) for n>=k>0.
Column 0: T(n,0) = Sum_{j=1..n} T(n,j)*T(j-1,0) for n>=0.

A152405 Square array, read by antidiagonals, where row n+1 is generated from row n by first removing terms in row n at positions {m*(m+1)/2, m>=0} and then taking partial sums, starting with all 1's in row 0.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 14, 8, 3, 1, 86, 45, 14, 4, 1, 645, 318, 86, 22, 5, 1, 5662, 2671, 645, 152, 31, 6, 1, 56632, 25805, 5662, 1251, 232, 41, 7, 1, 633545, 280609, 56632, 11869, 2026, 327, 53, 8, 1, 7820115, 3381993, 633545, 126987, 20143, 2991, 457, 66, 9, 1

Offset: 0

Paul D. Hanna, Dec 05 2008

			Table begins:
(1),(1),1,(1),1,1,(1),1,1,1,(1),1,1,1,1,(1),1,...;
(1),(2),3,(4),5,6,(7),8,9,10,(11),12,13,14,15,(16),...;
(3),(8),14,(22),31,41,(53),66,80,95,(112),130,149,169,190,...;
(14),(45),86,(152),232,327,(457),606,775,965,(1202),1464,1752,2067,...;
(86),(318),645,(1251),2026,2991,(4455),6207,8274,10684,(13934),17653,...;
(645),(2671),5662,(11869),20143,30827,(48480),70355,96990,128959,...;
(5662),(25805),56632,(126987),223977,352936,(582183),874664,1240239,...;
(56632),(280609),633545,(1508209),2748448,4438122,(7641111),11831184,...;
(633545),(3381993),7820115,(19651299),36837937,60743909,...; ...
where row n equals the partial sums of row n-1 after removing terms
at positions {m*(m+1)/2, m>=0} (marked by parenthesis in above table).
For example, to generate row 3 from row 2:
[3,8, 14, 22, 31,41, 53, 66,80,95, 112, 130,...]
remove terms at positions {0,1,3,6,10,...}, yielding:
[14, 31,41, 66,80,95, 130,149,169,190, ...]
then take partial sums to obtain row 3:
[14, 45,86, 152,232,327, 457,606,775,965, ...].
Continuing in this way generates all rows of this table.
RELATION TO POWERS OF A SPECIAL TRIANGULAR MATRIX.
Columns 0 and 1 are found in triangle T=A152400, which begins:
1;
1, 1;
3, 2, 1;
14, 8, 3, 1;
86, 45, 15, 4, 1;
645, 318, 99, 24, 5, 1;
5662, 2671, 794, 182, 35, 6, 1;
56632, 25805, 7414, 1636, 300, 48, 7, 1; ...
where column k of T = column 0 of matrix power T^(k+1) for k>=0.
Furthermore, matrix powers of triangle T=A152400 satisfy:
column k of T^(j+1) = column j of T^(k+1) for all j>=0, k>=0.
Column 3 of this square array = column 1 of T^2:
1;
2, 1;
8, 4, 1;
45, 22, 6, 1;
318, 152, 42, 8, 1;
2671, 1251, 345, 68, 10, 1;
25805, 11869, 3253, 648, 100, 12, 1; ...
RELATED TRIANGLE A127714 begins:
1;
1, 1, 1;
1, 2, 2, 3, 3, 3;
1, 3, 5, 5, 8, 11, 11, 14, 14, 14;
1, 4, 9, 14, 14, 22, 33, 44, 44, 58, 72, 72, 86, 86, 86;...
where right border = column 0 of this square array.

Cf. columns: A127715, A152401, A152404.
Cf. related triangles: A152400, A127714.
Cf. variants: A125781, A127054, A136212, A136217, A135876, A135878, A136730.

{T(n, k)=local(A=0, m=0, c=0, d=0); if(n==0, A=1, until(d>k, if(c==m*(m+1)/2, m+=1, A+=T(n-1, c); d+=1); c+=1)); A}

cp's OEIS Frontend

A127715 Rightmost border of triangle A127714: a(n) = A127714(n, (n+1)*(n+2)/2 - 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A127716 a(n) = A127714(n, n*(n+1)/2).

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A152400 Triangle T, read by rows, where column k of T = column 0 of matrix power T^(k+1) for k>0, with column 0 of T = unsigned column 0 of T^-1 (shifted).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A152405 Square array, read by antidiagonals, where row n+1 is generated from row n by first removing terms in row n at positions {m*(m+1)/2, m>=0} and then taking partial sums, starting with all 1's in row 0.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI