A086625 -id:A086625 - cp's OEIS frontend

A127379 Signature-permutation of Callan's 2006 bijection on Dyck Paths, mirrored version (A057164-conjugate).

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 13, 12, 14, 15, 19, 22, 21, 16, 20, 17, 18, 23, 24, 25, 27, 26, 28, 29, 33, 36, 35, 30, 34, 31, 32, 37, 38, 39, 41, 40, 51, 52, 60, 64, 63, 56, 62, 58, 59, 42, 43, 53, 54, 55, 44, 61, 45, 46, 47, 57, 48, 50, 49, 65, 66, 67, 69, 68, 70, 71

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

It's much easier to implement Callan's 2006 bijection for S-expressions if one considers a mirror-image of the graphical description given by Callan (on page 3). Then this automorphism is just RIBS-transformation (explained in A122200) of the automorphism A127377 and Callan's original variant A127381 is obtained as A057164(a(A057164(n))).

A. Karttunen, Table of n, a(n) for n = 0..2055
D. Callan, A Bijection on Dyck Paths and Its Cycle Structure, 2006, 17pp.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A127380. a(n) = A057164(A127381(A057164(n))). The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A127384 and A086625 shifted once right. The maximum cycles and LCM's of cycle sizes begin as 1, 1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, ... A127302(a(n)) = A127302(n) holds for all n. A127388 shows a variant which is an involution.

Differs from A073289 and A122349 for the first time at n=54, where a(n)=54, while A073289(54) = A122349(54) = 61.

A127388 Signature-permutation of a Catalan automorphism, a self-inverse variant of A127379.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 13, 12, 14, 15, 19, 22, 21, 16, 20, 18, 17, 23, 24, 25, 27, 26, 28, 29, 33, 36, 35, 30, 34, 32, 31, 37, 38, 39, 41, 40, 51, 52, 60, 64, 63, 56, 62, 59, 58, 42, 43, 53, 54, 55, 47, 61, 50, 49, 44, 57, 48, 46, 45, 65, 66, 67, 69, 68, 70, 71

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

This automorphism is RIBS-transformation (explained in A122200) of the automorphism A127387.

The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this involution are given by A127386 and A086625 shifted once right (this automorphism has the same fixed points as A127379/A127380). A127302(a(n)) = A127302(n) holds for all n.

A127389 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutations A127377/A127378 and A127387.

Original entry on oeis.org

1, 1, 0, 1, 2, 4, 10, 23, 56, 138, 344, 870, 2220, 5716, 14828, 38717, 101682, 268416, 711810, 1895432, 5066030, 13586082, 36547534, 98593064, 266661162, 722953814, 1964358938, 5348367006, 14589803090, 39870312218, 109136843138

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

This is INVERTi transform of A086625 (appropriately shifted). I.e. INVERT([1, 1, 0, 1, 2, 4, 10, 23, 56, 138, 344, 870, 2220, 5716]) gives: 1, 2, 3, 6, 12, 26, 59, 138, 332, 814, 2028, 5118, ... (beginning of A086625)

{a(n)=local(A=1+x+x*O(x^n));for(i=0,n,A=(1 + x*A^2)*(1+x)/(1+x+2*x^2));polcoeff(A,n)}

G.f. satisfies: A(x) = (1 + x*A(x)^2)*(1+x)/(1+x+2*x^2).

Generating function, PARI-program and most of the terms supplied by Paul D. Hanna, Jan 15 2007

A127381 Signature-permutation of Callan's 2006 bijection on Dyck Paths.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 13, 12, 14, 15, 19, 22, 18, 16, 21, 17, 20, 23, 24, 25, 27, 26, 28, 29, 33, 36, 32, 30, 35, 31, 34, 37, 38, 39, 41, 40, 51, 52, 60, 64, 46, 47, 59, 50, 49, 42, 43, 56, 63, 55, 44, 58, 45, 48, 53, 62, 54, 61, 57, 65, 66, 67, 69, 68, 70, 71

Offset: 0

Antti Karttunen, Jan 16 2007

This automorphism is much easier to implement for S-expressions when viewed as a A057164-conjugate of A127379. See the comments in the latter entry.

A. Karttunen, Table of n, a(n) for n = 0..2055
D. Callan, A Bijection on Dyck Paths and its Cycle Structure, The Electronic Journal of Combinatorics 14 (2007), #R28
Index entries for signature-permutations of Catalan automorphisms

Inverse: A127382. a(n) = A057164(A127379(A057164(n))). The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A127384 and A086625 shifted once right. The maximum cycles and LCM's of cycle sizes begin as 1, 1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, ...

A086623 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies f(x,y) = (1-xy)/[(1-x)(1-y)] + xyf(x,y)^2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 4, 8, 8, 4, 1, 1, 5, 14, 19, 14, 5, 1, 1, 6, 22, 40, 40, 22, 6, 1, 1, 7, 32, 76, 100, 76, 32, 7, 1, 1, 8, 44, 132, 222, 222, 132, 44, 8, 1, 1, 9, 58, 213, 448, 570, 448, 213, 58, 9, 1, 1, 10, 74, 324, 834, 1316, 1316, 834, 324, 74, 10, 1, 1

Offset: 0

Paul D. Hanna, Jul 24 2003

The first row and column of 1's together form: (1-xy)/[(1-x)(1-y)], while the remaining square table (excluding the first row and column) give the coefficients of f(x,y)^2.

			Rows begin:
1,1,_1,__1,___1,___1,____1,____1,_____1, ...
1,1,_2,__3,___4,___5,____6,____7,_____8, ...
1,2,_4,__8,__14,__22,___32,___44,____58, ...
1,3,_8,_19,__40,__76,__132,__213,___324, ...
1,4,14,_40,_100,_222,__448,__834,__1450, ...
1,5,22,_76,_222,_570,_1316,_2782,__5458, ...
1,6,32,132,_448,1316,_3442,_8180,_17928, ...
1,7,44,213,-834,2782,_8180,21685,_52694, ...
1,8,58,324,1450,5458,17928,52694,141112, ...

Cf. A086624 (diagonal), A086625 (antidiagonal sums).

A086624 Main diagonal of square table A086623 of coefficients of f(x,y) that satisfies f(x,y) = (1-xy)/[(1-x)(1-y)] + xy*f(x,y)^2.

Original entry on oeis.org

1, 1, 4, 19, 100, 570, 3442, 21685, 141112, 941990, 6419174, 44493000, 312818326, 2226155632, 16008452202, 116167346499, 849724397580, 6259403310366, 46399703925202, 345894094030552

Offset: 0

Paul D. Hanna, Jul 24 2003

nonn

Cf. A086623 (table), A086625 (antidiagonal sums).

A152172 a(n) is the number of Dyck paths of semilength n without height of peaks 0 (mod 3) and height of valleys 1 (mod 3).

Original entry on oeis.org

1, 1, 2, 3, 6, 12, 26, 59, 138, 332, 814, 2028, 5118, 13054, 33598, 87143, 227542, 597640, 1577866, 4185108, 11146570, 29798682, 79932298, 215072896, 580327122, 1569942098, 4257254850, 11569980794, 31508150890, 85968266198, 234975421554, 643317390627

Offset: 0

Jun Ma (majun(AT)math.sinica.edu.tw), Nov 27 2008

nonn

Hankel transform gives A328380(n+1). - Thomas Scheuerle, Oct 23 2024

Shu-Chung Liu, Jun Ma, Yeong-Nan Yeh, Dyck Paths with Peak- and Valley-Avoiding Sets, Stud. Appl Math. 121 (3) (2008) 263-289.

Almost the same as A086625. - R. J. Mathar, Dec 03 2008

Cf. A000108, A328380.

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
      `if`(t=0 and irem(y, 3)=0, 0, b(x-1, y-1, 1))+
      `if`(t=1 and irem(y, 3)=1, 0, b(x-1, y+1, 0))))
    end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=0..35);  # Alois P. Heinz, Oct 23 2024

CoefficientList[Series[(1+x-2x^2-Sqrt[1-2x-3x^2+4x^4])/(2(1-x)x), {x, 0, 30}], x] (* Harvey P. Dale, Apr 10 2012 *)

{a(n) = my(A, E=ellinit([1, -1, 0, -1, 1]),b=1,c=1,v=[1]); if( n<0, 0, A = O(x); for(k=1, n, v=concat(v,(1/b)*(1/c)); b=(1/b)*(1/c); c=(1-ellmul(E,[0,1],2*k+1)[1])/b; v=concat(v,c) ); for(k=1, #v,A = 1 /(1 - v[#v+1-k]*x*A));polcoeff(A, n))}; \\ Thomas Scheuerle, Oct 23 2024

{a(n) = my(A,v=[1,1,-1,-1,3]); if( n<0, 0, A = O(x); for(k=1, n+1, v=concat(v,(1/v[#v])*(1/v[#v-1])); v=concat(v,(v[#v-2]*v[#v-1]-2)/(v[#v-4]*v[#v-3]*v[#v-2]^2*v[#v-1]^2*v[#v]))); for(k=1, #v,A = 1 /(1 - v[#v+1-k]*x*A));polcoeff(A, n))} \\ Thomas Scheuerle, Oct 23 2024

G.f.: (1+x-2*x^2-sqrt(1-2*x-3*x^2+4*x^4))/(2*(1-x)*x).
(n+1)*a(n) - 2*n*a(n-1) + (7-3*n)*a(n-2) + 4*a(n-3) + 4*(n-4)*a(n-4) = 0 for n>=4. - R. J. Mathar, Aug 14 2012
G.f.: 1 - 1/G(0) where G(k) = 1 - 1/(x  + x^2/(1 + x/G(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Nov 28 2012
G.f.: 1/(1-x/(1-b_{0}*x/(1-c_{0}*x/(1-b_{1}*x/(1-c_{1}*x/(...)))))), with (1-b_{n}*c_{n}) = the x-coordinate of (2*n+1) times the point [0, 1] under the group law of the elliptic curve y^2 + x*y = x^3 - x^2 - x+1. b_{n} = (1/b_{n-1})*(1/c_{n-1}) with b_{0} = 1, also c_{n} = (c_{n-1}*b_{n-1} - 2)/(b_{n}*c_{n-2}*b_{n-2}*(c_{n-1}*b_{n-1})^2) - Thomas Scheuerle, Oct 23 2024

cp's OEIS Frontend

A127379 Signature-permutation of Callan's 2006 bijection on Dyck Paths, mirrored version (A057164-conjugate).

Views

Author

Keywords

Comments

Links

Crossrefs

A127388 Signature-permutation of a Catalan automorphism, a self-inverse variant of A127379.

Views

Author

Keywords

Comments

Links

Crossrefs

A127389 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutations A127377/A127378 and A127387.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

Extensions

A127381 Signature-permutation of Callan's 2006 bijection on Dyck Paths.

Views

Author

Keywords

Comments

Links

Crossrefs

A086623 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^n*y^k in f(x,y) that satisfies f(x,y) = (1-xy)/[(1-x)(1-y)] + xy*f(x,y)^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

A086624 Main diagonal of square table A086623 of coefficients of f(x,y) that satisfies f(x,y) = (1-xy)/[(1-x)(1-y)] + xy*f(x,y)^2.

Views

Author

Keywords

Crossrefs

A152172 a(n) is the number of Dyck paths of semilength n without height of peaks 0 (mod 3) and height of valleys 1 (mod 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A086623 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies f(x,y) = (1-xy)/[(1-x)(1-y)] + xyf(x,y)^2.