A001683 -id:A001683 - cp's OEIS frontend

A208355 Right edge of the triangle in A208101.

1, 1, 1, 2, 2, 5, 5, 14, 14, 42, 42, 132, 132, 429, 429, 1430, 1430, 4862, 4862, 16796, 16796, 58786, 58786, 208012, 208012, 742900, 742900, 2674440, 2674440, 9694845, 9694845, 35357670, 35357670, 129644790, 129644790, 477638700, 477638700, 1767263190

Offset: 0

Reinhard Zumkeller, Mar 04 2012

nonn

Number of achiral polyominoes composed of n+1 triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. An achiral polyomino is identical to its reflection. - Robert A. Russell, Jan 20 2024

			a(0)=1; a(1)=1; a(2)=1; a(3)=2. - _Robert A. Russell_, Jan 19 2024
____      ________
\  /  /\  \  /\  /  /\     /\
 \/  /__\  \/__\/  /__\   /__\____
     \  /         /\  /\  \  /\  /
      \/         /__\/__\  \/__\/

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
D. Levin, L. Pudwell, M. Riehl, and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
Zhicong Lin, David G. L. Wang, and Tongyuan Zhao, A decomposition of ballot permutations, pattern avoidance and Gessel walks, arXiv:2103.04599 [math.CO], 2021.

Cf. A099363, A208101.

Polyominoes: A001683(n+2) (oriented), A000207 (unoriented). A369314 (chiral), A000108 (rooted), A047749 ({4,oo}).

a208355 n = a208101 n n
a208355_list = map last a208101_tabl

[Ceiling(Catalan(n div 2)): n in [1..40]]; // Vincenzo Librandi, Feb 18 2014

A208355_list := proc(len) local D, b, h, R, i, k;
    D := [seq(0, j=0..len+2)]; D[1] := 1; b := true; h := 2; R := NULL;
    for i from 1 to 2*len do
        if b then
            for k from h by -1 to 2 do D[k] := D[k] - D[k-1] od;
            h := h + 1; R := R, abs(D[2]);
        else
            for k from 1 by 1 to h do D[k] := D[k] + D[k+1] od;
        fi;
        b := not b:
    od;
    return R
end:
A208355_list(38); # Peter Luschny, Dec 19 2017

T[, 0] = 1; T[n, 1] := n; T[n_, n_] := T[n - 1, n - 2]; T[n_, k_] /; 1 < k < n := T[n, k] = T[n - 1, k] + T[n - 1, k - 2];
a[n_] := T[n, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 03 2018, from A208101 *)
Table[If[EvenQ[n], Binomial[n,n/2]/(n/2+1), Binomial[n+1,(n+1)/2]/((n+3)/2)], {n,0,40}] (* Robert A. Russell, Jan 19 2024 *)

a(n) = A000108(floor((n+1)/2)), where A000108 = Catalan numbers.
a(n) = A208101(n,n).
a(n) = abs(A099363(n)).
Conjecture: -(n+3)*(n-2)*a(n) - 4*a(n-1) + 4*(n-1)^2*a(n-2) = 0. - R. J. Mathar, Aug 04 2015
From Robert A. Russell, Jan 19 2024: (Start)
a(2m) = C(2m,m)/(m+1); a(2m-1) = a(2m); a(n+2)/a(n) ~ 4.
a(n-1) = 2*A000207(n) - A001683(n+2) = A001683(n+2) - 2*A369314(n) = A000207(n) - A369314(n). (End)
G.f.: (G(z^2)+z*G(z^2)-1)/z, where G(z)=1+z*G(z)^2, the generating function for A000108. - Robert A. Russell, Jan 26 2024
G.f.: ((((1+z)*(1-sqrt(1-4*z^2)))/(2*z^2))-1)/z. - Robert A. Russell, Jan 28 2024
From Peter Bala, Feb 05 2024: (Start)
G.f.: 1/(1 + 2*x) * c(x/(1 + 2*x))^3, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
a(n) = Sum_{k = 0..n} (-2)^(n-k)*binomial(n, k)*A000245(k+1).
a(n) = (-2)^n * hypergeom([-n, 3/2, 2], [1, 4], 2). (End)

A295224 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals up to rotation (k >= 3).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 2, 7, 6, 1, 1, 3, 12, 25, 19, 1, 1, 3, 19, 57, 108, 49, 1, 1, 4, 26, 118, 366, 492, 150, 1, 1, 4, 35, 203, 931, 2340, 2431, 442, 1, 1, 5, 46, 332, 1989, 7756, 16252, 12371, 1424, 1, 1, 5, 57, 494, 3766, 20254, 68685, 115940, 65169, 4522

Offset: 1

Andrew Howroyd, Nov 17 2017

The polygon prior to dissection will have n*(k-2)+2 sides.
In the Harary, Palmer and Read reference these are the sequences called H.
T(n,k) is the number of oriented polyominoes containing n k-gonal tiles of the hyperbolic regular tiling with Schläfli symbol {k,oo}. Stereographic projections of several of these tilings on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. T(n,2) could represent polyominoes of the Euclidean regular tiling with Schläfli symbol {2,oo}; T(n,2) = 1. - Robert A. Russell, Jan 21 2024

			Array begins:
  =====================================================
  n\k|    3     4      5       6        7         8
  ---|-------------------------------------------------
   1 |    1     1      1       1        1         1 ...
   2 |    1     1      1       1        1         1 ...
   3 |    1     2      2       3        3         4 ...
   4 |    4     7     12      19       26        35 ...
   5 |    6    25     57     118      203       332 ...
   6 |   19   108    366     931     1989      3766 ...
   7 |   49   492   2340    7756    20254     45448 ...
   8 |  150  2431  16252   68685   219388    580203 ...
   9 |  442 12371 115940  630465  2459730   7684881 ...
  10 | 1424 65169 854981 5966610 28431861 104898024 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.
Wikipedia, Fuss-Catalan number

Columns k=3..6 are A001683(n+2), A005034, A005038, A221184(n-1).
Cf. A033282, A070914, A295222, A295259, A295260.
Polyominoes: A295260 (unoriented), A070914 (rooted).

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
T[n_, k_] := u[n, k, 1] + (If[EvenQ[n], u[n/2, k, 1], 0] - u[n, k, 2])/2 + DivisorSum[GCD[n - 1, k], EulerPhi[#]*u[(n - 1)/#, k, k/#]&]/k;
Table[T[n - k + 1, k], {n, 1, 13}, {k, n, 3, -1}] // Flatten (* Jean-François Alcover, Nov 21 2017, after Andrew Howroyd *)

\\ here u is Fuss-Catalan sequence with p = k+1.
u(n, k, r)={r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
T(n,k) = u(n,k,1) + (if(n%2==0, u(n/2,k,1))-u(n,k,2))/2 + sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d,k,k/d))/k;
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

from sympy import binomial, gcd, totient, divisors
def u(n, k, r): return r*binomial((k - 1)*n + r, n)//((k - 1)*n + r)
def T(n, k): return u(n, k, 1) + ((u(n//2, k, 1) if n%2==0 else 0) - u(n, k, 2))//2 + sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # Indranil Ghosh, Dec 13 2017, after PARI code

T(n,k) ~ A295222(n,k)/n for fixed k.

A006343 Arkons: number of elementary maps with n-1 nodes.

Original entry on oeis.org

1, 0, 1, 1, 4, 10, 34, 112, 398, 1443, 5387, 20482, 79177, 310102, 1228187, 4910413, 19792582, 80343445, 328159601, 1347699906, 5561774999, 23052871229, 95926831442, 400587408251, 1678251696379, 7051768702245, 29710764875014

Offset: 0

N. J. A. Sloane

K. Appel and W. Haken, Every planar map is four colorable. With the collaboration of J. Koch. Contemporary Mathematics, 98. American Mathematical Society, Providence, RI, 1989. xvi+741 pp. ISBN: 0-8218-5103-9.
F. R. Bernhart, Topics in Graph Theory Related to the Five Color Conjecture. Ph.D. Dissertation, Kansas State Univ., 1974.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
F. R. Bernhart, Fundamental chromatic numbers, Unpublished. (Annotated scanned copy)
F. R. Bernhart and N. J. A. Sloane, Correspondence, 1977.
F. R. Bernhart and N. J. A. Sloane, Emails, April-May 1994.
G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60, (1946). 355-451.

Cf. A000108, A000934, A007318.

a006343 0 = 1
a006343 n = sum $ zipWith div
   (zipWith (*) (map (a007318 n) ks)
                (map (\k -> a007318 (2*n - 3*k - 4) (n - 2*k - 2)) ks))
   (map (toInteger . (n - 1 -)) ks)
   where ks = [0 .. (n - 2) `div` 2]
-- Reinhard Zumkeller, Aug 23 2012

A006343:=n->add(binomial(n,k)*binomial(2*n-3*k-4,n-2*k-2)/(n-k-1), k=0..(n-2)/2): (1, seq(A006343(n), n=1..30)); # Wesley Ivan Hurt, Jun 22 2015

a[n_] := Sum[ Binomial[n, k]*Binomial[2*n-3*k-4, n-2*k-2]/(n-k-1), {k, 0, (n-2)/2}]; a[0] = 1; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Dec 14 2012, from formula *)

a(n-1) = Sum (n-k-1)^(-1)*binomial(n, k)*binomial(2*n-3*k-4, n-2*k-2); k = 0..[ (n-2)/2 ], n >= 3.
From Peter Bala, Jun 22 2015: (Start)
O.g.f. A(x) equals 1/x * series reversion ( x/(1 + x^2*C(x)) ), where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for A000108.
A(x) is an algebraic function satisfying x^3*A^3(x) - (x - 1)*A^2(x) + (x - 2)*A(x) + 1 = 0. (End)
a(n) ~ sqrt(s*(1 - s + 3*r^2*s^2) / (1 - r + 3*r^3*s)) / (2*sqrt(Pi) * n^(3/2) * r^(n - 1/2)), where r = 0.2229935155751761877673240243525445951244491757706... and s = 1.116796494086474135831052534637944909439048671327... are real roots of the system of equations 1 + (r-2)*s + r^3*s^3 = (r-1)*s^2, r + 2*s + 3*r^3*s^2 = 2 + 2*r*s. - Vaclav Kotesovec, Nov 27 2017
Conjecture: D-finite with recurrence: -(n+3)*(n-1)*a(n) +(11*n^2-2*n-45)*a(n-1) -(37*n+29)*(n-3)*a(n-2) +(29*n^2-125*n+78)*a(n-3) +(61*n-106)*(n-3)*a(n-4) -155*(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Feb 20 2020

Erroneously duplicated term 4 removed per Frank Bernhart's report by Max Alekseyev, Feb 11 2010

A057162 Signature-permutation of a Catalan Automorphism: rotate one step clockwise the triangulations of polygons encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated clockwise.

In A057161 and A057162, the cycles between A014138(n-1)-th and A014138(n)-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A001683(n+2) equivalence classes of flexagons (or unlabeled plane boron trees), thus the latter sequence can be counted with the Maple procedure A057162_CycleCounts given below. Cf. also the comments in A057161.

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 51-54.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057161.
Also, an "ENIPS"-transform of A069773, and thus occurs as row 17 of A130402.
Other related permutations: A057163, A057164, A057501, A057503, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularizationR(A014486[n]))
RotateTriangularizationR := n -> ReflectBinTree(RotateTriangularization(ReflectBinTree(n)));
with(group); A057162_CycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,RotateTriangularization(CatalanUnrank(n,r)))]; od; a := [op(a),(`if`((n < 2),1,nops(convert(b,'disjcyc'))))]; od; RETURN(a); end;
# See also the code in A057161.

As a composition of related permutations:
a(n) = A069768(A057508(n)).
a(n) = A057163(A057161(A057163(n))).
a(n) = A057164(A057503(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 143.]

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 56, 153, 451, 1357, 4212, 13308, 42898, 140276, 465324, 1561955, 5300285, 18156813, 62732842, 218405402, 765657940

Offset: 0

Antti Karttunen Sep 03 2000

It is much faster to compute this sequence empirically with the given C-program than to calculate the terms with the formula in its present form.

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences related to rooted trees
A. Karttunen, C-program for computing empirically the initial terms of this sequence

CountCycles given in A057502, for other procedures, follow A057511 and A057501.
Similarly generated sequences: A001683, A002995, A003239, A038775, A057507. Cf. also A000081.
Occurs for first time in A073201 as row 12. Cf. A057546 and also A000081.

A057513 := proc(n) local i; `if`((0=n),1,(1/A003418(n-1))*add(A079216bi(n,i),i=1..A003418(n-1))); end;
# Or empirically:
DeepRotatePermutationCycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,DeepRotateL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;

a(0)=1, a(n) = (1/A003418(n-1))*Sum_{i=1..A003418(n-1)} A079216(n, i) [Needs improvement.] - Antti Karttunen, Jan 03 2003

A073201 Array of cycle count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 1, 1, 1, 22, 11, 3, 1, 1, 1, 66, 31, 7, 2, 1, 1, 1, 217, 96, 22, 4, 3, 1, 1, 1, 715, 305, 66, 11, 7, 2, 1, 1, 1, 2438, 1007, 217, 30, 22, 4, 2, 2, 1, 1, 8398, 3389, 715, 93, 66, 11, 3, 5, 1, 1, 1, 29414, 11636, 2438, 292, 217, 30, 6, 14, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of separate orbits/cycles to which the Catalan bijection given in the corresponding row of A073200 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Note that for involutions (self-inverse Catalan bijections) this is always (A000108(n)+Affffff(n))/2, where Affffff is the corresponding "fix-count sequence" from the table A073202.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Only the first known occurrence(s) given (marked with ? if not yet proved/unclear): rows 0, 2, 4, etc.: A007595, Row 1: A073191, Rows 6 (& 8): A073431, Row 7: A000108, Rows 12, 14, 20, ...: A057513, Rows 16, 18, ...: A003239, Row 57, ..., 164: A007123, Row 168: A073193, Row 261: A002995, Row 2614: A057507, Row 2618 (?), row 17517: A001683.

A089860 Permutation of natural numbers induced by Catalan automorphism *A089860 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.....B...C.......C...A
......\./.........\./
...A...x...-->... .x...B...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
(a . (b . c)) --> ((c . a) . b) ___ (a . ()) --> (() . a)
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 16 of A089840. Inverse of A089862. a(n) = A089855(A069770(n)) = A069770(A089851(n)) = A069770(A074680(A069770(n))) = A057163(A089862(A057163(n))).

Number of cycles: A001683 (probably, not checked). Number of fixed points: A019590. Max. cycle size & LCM of all cycle sizes: A089410 (in each range limited by A014137 and A014138).

A graphical description and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A089862 Permutation of natural numbers induced by Catalan automorphism *A089862 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.A...B...............C...A
..\./.................\./
...x...C...-->.....B...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (b . (c . a)) __ (() . a) ----> (a . ())
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 20 of A089840. Inverse of A089860. a(n) = A089853(A069770(n)) = A069770(A089857(n)) = A069770(A074679(A069770(n))) = A057163(A089860(A057163(n))). Number of cycles: A001683 (seems to be, not checked). Number of fixed points: A019590. Max. cycle size & LCM of all cycle sizes: A089410 (in each range limited by A014137 and A014138).

A graphical description and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A005038 Number of nonequivalent dissections of a polygon into n pentagons by nonintersecting diagonals up to rotation.

Original entry on oeis.org

1, 1, 2, 12, 57, 366, 2340, 16252, 115940, 854981, 6444826, 49554420, 387203390, 3068067060, 24604111560, 199398960212, 1631041938108, 13451978877748, 111765327780200, 934774244822704, 7865200653146905

Offset: 1

N. J. A. Sloane

Also, with a different offset, number of colored quivers in the 3-mutation class of a quiver of Dynkin type A_n. - N. J. A. Sloane, Jan 22 2013

Number of oriented polyominoes composed of n pentagonal cells of the hyperbolic regular tiling with Schläfli symbol {5,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Jan 23 2024

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..1000
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Hermund A. Torkildsen, Colored quivers of type A and the cell-growth problem, arXiv:1004.4512 [math.RT], 2010.
Hermund A. Torkildsen, Colored quivers of type A and the cell-growth problem, J. Algebra and Applications, 12 (2013), #1250133. - From _N. J. A. Sloane_, Jan 22 2013

Column k=5 of A295224.

Polyominoes: A005040 (unoriented), A369471 (chiral), A369472 (achiral), A001683(n+2) {3,oo}, A005034 {4,oo}, A221184{n-1} {6,oo}.

p=5; Table[Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) +If[OddQ[n], 0, Binomial[(p-1)n/2, n/2]/((p-2)n+2)]+Plus @@ Map[EulerPhi[ # ]Binomial[((p-1)n+1)/#, (n-1)/# ]/((p-1)n+1)&, Complement[Divisors[GCD[p, n-1]], {1}]], {n, 1, 20}] (* Robert A. Russell, Dec 11 2004 *)

a(n) ~ 2^(8*n + 1/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n + 5/2)). - Vaclav Kotesovec, Mar 13 2016

a(n) = A005040(n) + A369471(n) = 2*A005040(n) - A369472(n) = 2*A369471(n) + A369472(n). - Robert A. Russell, Jan 23 2024

a(21) corrected by Sean A. Irvine, Mar 11 2016

Name edited by Andrew Howroyd, Nov 20 2017

A057503 Signature-permutation of a Catalan Automorphism: Deutsch's 1998 bijection on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Deutsch shows in his 1998 paper that this automorphism maps the number of returns of Dyck path to the height of the last peak, i.e., that A057515(n) = A080237(A057503(n)) holds for all n, thus the two parameters have the same distribution.

From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505, when the other side of the formula is also "recursivized" in the same way. - Antti Karttunen, Jun 06 2014

Antti Karttunen, Table of n, a(n) for n = 0..2055
Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
Antti Karttunen, C program which computes this sequence..
Antti Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 53-54.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057504. Row 17 of A122285. Cf. A057501, A057161, A057505.

The number of cycles, count of the fixed points, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n)] of this permutation are given by LEFT(LEFT(A001683)), LEFT(A019590), A057544 and A057544, the same sequences as for A057162 because this is a conjugate of it (cf. the Formula section).

a(0) = 0, and for n >= 1, a(n) = A085201(A072771(n), A057548(a(A072772(n)))). [This formula reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to the unary form of function 'list'].
a(n) = A057164(A057162(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 144.]
Other identities:
A057515(n) = A080237(a(n)) holds for all n. [See the Comments section.]

Equivalence with Emeric Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

cp's OEIS Frontend

A208355 Right edge of the triangle in A208101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Formula

A295224 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals up to rotation (k >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A006343 Arkons: number of elementary maps with n-1 nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A057162 Signature-permutation of a Catalan Automorphism: rotate one step clockwise the triangulations of polygons encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A089860 Permutation of natural numbers induced by Catalan automorphism *A089860 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A089862 Permutation of natural numbers induced by Catalan automorphism *A089862 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords