A057501 -id:A057501 - cp's OEIS frontend

A057517 Binary encodings of the Catalan mountain ranges with exactly one sea-level valley, i.e., the rooted plane trees with root degree = 2.

10, 44, 50, 180, 184, 204, 210, 226, 724, 728, 740, 744, 752, 820, 824, 844, 850, 866, 908, 914, 930, 962, 2900, 2904, 2916, 2920, 2928, 2964, 2968, 2980, 2984, 2992, 3012, 3016, 3024, 3040, 3284, 3288, 3300, 3304, 3312, 3380, 3384, 3404, 3410, 3426

Offset: 1

Antti Karttunen, Sep 03 2000

nonn

This bijective mapping from all rooted plane trees to one node larger, root degree = 2 trees illustrates the fact that CONV(A000108, A000108) = LEFT(A000108). (Catalan numbers shift left under convolution).

Cf. A057501 (for binexp2pars, pars2binexp, car, cdr), A057518, A057519, A057122. Single-trunked trees: A057547.

alltrees2doubletrunked := n -> pars2binexp(alltrees2doubletrunkedP(binexp2pars(n)));
alltrees2doubletrunkedP := h -> [car(h),cdr(h)];

a(n) = alltrees2doubletrunked(A014486(n)) (Starting from n=1).

A057547 A014486-encodings of Catalan mountain ranges with no sea-level valleys, i.e., the rooted plane general trees with root degree = 1.

Original entry on oeis.org

2, 12, 52, 56, 212, 216, 228, 232, 240, 852, 856, 868, 872, 880, 916, 920, 932, 936, 944, 964, 968, 976, 992, 3412, 3416, 3428, 3432, 3440, 3476, 3480, 3492, 3496, 3504, 3524, 3528, 3536, 3552, 3668, 3672, 3684, 3688, 3696, 3732, 3736, 3748, 3752, 3760

Offset: 0

Antti Karttunen Sep 07 2000

This one-to-one correspondence between all rooted plane trees and one node larger, root degree = 1 trees illustrates the fact that INVERT(A000108) = LEFT(A000108). (Catalan numbers shift left under Cameron's A transformation.)
From Ruud H.G. van Tol, May 13 2024: (Start)
Sequence on a lattice:
Tree         Paths                  Decimal  Count
|_           10                           2      1
|.         1100                        12      1
||._       110100    -111000        52,56      2
|||_._     11010100  -11110000    212-240      5
|||_|.   1101010100-1111100000  852-992     14
... (End)

Ruud H.G. van Tol, Table of n, a(n) for n = 0..2055
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Index entries for encodings of plane rooted trees

Double-trunked trees: A057517. Cf. also A057548, A057549.

alltrees2singletrunked := n -> pars2binexp([binexp2pars(n)]); # Just surround with extra parentheses.

a_rows(N) = my(a=Vec([[2]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, for(i=1, valuation(t, 2), listput(~c, (t<<2)+(2<Ruud H.G. van Tol, May 25 2024

a(n) = A014486(A057548(n)) and also from n > 0 onward = A079946(A014486(n)).

a(n) = alltrees2singletrunked(A014486[n]) (see Maple code below and in A057501).

A069889 Self-inverse permutation of natural numbers induced by the automorphism RotateHandshakes_et_DeepReverse! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

This automorphism reflects non-crossing handshakes (the interpretation n of Stanley's exercise 19) over the diagonal that goes through corner at "11 o'clock".

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
R. P. Stanley, Exercises on Catalan and Related Numbers
Index entries for sequences that are permutations of the natural numbers

Composition of A057501 and A057164, i.e. A069888(n) = A057164(A057501(n)). Cf. also A069888.

A085173 Permutation of natural numbers induced by the Catalan bijection gma085173 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "rising slope" mapping illustrated in A085161.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A085174. a(n) = A085161(A085174(A085161(n))) = A085169(A057501(A085170(n))) = A074684(A057501(A074683(n))). Occurs in A073200. Cf. also A085159 (whole step rotate), A086427.

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A123501 Signature permutation of a Catalan automorphism: apply *A123497 at the root, then recurse into the left subtree of the right hand side subtree of a binary tree.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123502. A057501(n) = A083927(a(A057123(n))) = A083927(A085159(A057123(n))).

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4

Offset: 0

Peter Luschny, Aug 09 2012

See Antti Karttunen's code in A057117. Karttunen writes: "Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES (Kreher and Stinson) book."

For all n>0, a(A014486(n)) = n = A080300(A014486(n)). The sequence A080300 differs from this one in that it gives 0 for those n which are not found in A014486. - Antti Karttunen, Aug 10 2012

G. C. Greubel, Table of n, a(n) for n = 0..1000
A. Karttunen, Catalan's Triangle and ranking of Mountain Ranges
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.
F. Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.

Cf. A213704, A057117, A057164, A057505, A057506, A057501, A057502, A057511, A057512, A057123, A057117, A057509, A057510, A057161, A057162, A072766, A071654, A071652, A075161, A061856, A072635, A072788, A057518, A075168, A080119, A057120, A072773.

A215406 := proc(n) local m,a,y,t,x,u,v;
m := iquo(A070939(n), 2);
a := A030101(n);
y := 0; t := 1;
for x from 0 to 2*m-2 do
    if irem(a, 2) = 1 then y := y + 1
    else u := 2*m - x;
         v := m-1 - iquo(x+y,2);
         t := t + A037012(u,v);
         y := y - 1 fi;
    a := iquo(a, 2) od;
A014137(m) - t end:
seq(A215406(i),i=0..199); # Peter Luschny, Aug 10 2012

A215406[n_] := Module[{m, d, a, y, t, x, u, v}, m = Quotient[Length[d = IntegerDigits[n, 2]], 2]; a = FromDigits[Reverse[d], 2]; y = 0; t = 1; For[x = 0, x <= 2*m - 2, x++, If[Mod[a, 2] == 1, y++, u = 2*m - x; v = m - Quotient[x + y, 2] - 1; t = t - Binomial[u - 1, v - 1] + Binomial[u - 1, v]; y--]; a = Quotient[a, 2]]; (1 - I*Sqrt[3])/2 - 4^(m + 1)*Gamma[m + 3/2]*Hypergeometric2F1[1, m + 3/2, m + 3, 4]/(Sqrt[Pi]*Gamma[m + 3]) - t]; Table[A215406[n] // Simplify, {n, 0, 86}] (* Jean-François Alcover, Jul 25 2013, translated and adapted from Peter Luschny's Maple program *)

def A215406(n) : # CatalanRankGlobal(n)
    m = A070939(n)//2
    a = A030101(n)
    y = 0; t = 1
    for x in (1..2*m-1) :
        u = 2*m - x; v = m - (x+y+1)/2
        mn = binomial(u, v) - binomial(u, v-1)
        t += mn*(1 - a%2)
        y -= (-1)^a
        a = a//2
    return A014137(m) - t

A064638 Positions of non-crossing fixed-point-free involutions encoded by A014486 in A055089. Permutation of A064640.

Original entry on oeis.org

0, 1, 7, 23, 127, 415, 143, 659, 719, 5167, 16687, 5455, 26815, 28495, 5183, 16703, 5699, 36899, 38579, 5759, 36959, 40031, 40319, 368047, 1174447, 379567, 1901647, 1992367, 368335, 1174735, 389695, 2627455, 2718175, 391375, 2629135, 2799055

Offset: 0

Antti Karttunen, Oct 02 2001

nonn

Maple procedure binexp2pars given in A057501, permul in A060125.

map(PermRevLexRank,map(NonCrossingTranspos, A014486));
NonCrossingTranspos := n -> convert(NonCrossingTransposAux(binexp2pars(n),1),'permlist',binwidth(n));
NonCrossingTransposAux := proc(s,ii) local e,p,i,j; i := ii; p := []; for e in s do p := permul(p,NonCrossingTransposAux(e,i+1)); j := i+CountParens(e)+1; p := permul(p,[[i,j]]); i := j+1; od; RETURN(p); end;
CountParens := proc(s) local e,k; if(0 = nops(s)) then RETURN(0); fi; e := 0; for k in s do e := e+2+CountParens(k); od; RETURN(e); end;

A129599 Prime-factorization encoded partition code for the Łukasiewicz-word, variant of A129593.

Original entry on oeis.org

1, 3, 25, 25, 343, 35, 35, 343, 35, 14641, 847, 847, 847, 55, 847, 55, 847, 14641, 847, 55, 847, 847, 55, 371293, 24167, 24167, 1573, 1183, 24167, 1183, 1573, 24167, 1183, 1183, 1183, 1183, 65, 24167, 1183, 1183, 1183, 65, 1573, 1183, 24167

Offset: 0

Antti Karttunen, May 01 2007

nonn

In addition to all the automorphisms whose signature permutation satisfies the more restricted condition A127301(SP(n)) = A127301(n) for all n, there are also general tree-rotating automorphisms like *A057501, *A057502, *A069771 and *A069772 that satisfy also the condition A129599(SP(n)) = A129599(n) for all n. However, in contrast to A129593 this is not invariant under the automorphism *A072797. A000041(n) distinct values (seem to) occur in each range [A014137(n)..A014138(n)].

			The terms A079436(5), A079436(6) and A079436(8) are 2010, 2100 and 1110. After adding one to each number except the first one we get 2121, 2211 and 1221, each one which produces partition 1+1+2+2. Converting it to prime-exponents like explained in A129595, we get 2^0 * 3^0 * 5^1 * 7^1 = 35, thus a(5) = a(6) = a(8) = 35.

A. Karttunen, Table of n, a(n) for n = 0..625
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz

Variant: A129593.

Construction: add one to each number of the Łukasiewicz-word of a general plane tree encoded by A014486(n) (i.e. A079436(n)) except the first number, sort the numbers into ascending order and interpreting it as a partition of a natural number, encode it in the manner explained in A129595.

A082314 Involution of natural numbers: A057502-conjugate of A057164.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 17 2003

nonn

Index entries for signature-permutations induced by Catalan automorphisms

a(n) = A057502(A069889(n)). Occurs in A073200 as row 2361759710983228099211. Cf. also A082313.

Number of cycles: A007123. Number of fixed-points: A001405. Max. cycle size: A046698. LCM of cycle sizes: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

a(n) = A057502(A057164(A057501(n)))

cp's OEIS Frontend

A057517 Binary encodings of the Catalan mountain ranges with exactly one sea-level valley, i.e., the rooted plane trees with root degree = 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

A057547 A014486-encodings of Catalan mountain ranges with no sea-level valleys, i.e., the rooted plane general trees with root degree = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A069889 Self-inverse permutation of natural numbers induced by the automorphism RotateHandshakes_et_DeepReverse! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

A085173 Permutation of natural numbers induced by the Catalan bijection gma085173 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A123501 Signature permutation of a Catalan automorphism: apply *A123497 at the root, then recurse into the left subtree of the right hand side subtree of a binary tree.

Views

Author

Keywords

Links

Crossrefs

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

A064638 Positions of non-crossing fixed-point-free involutions encoded by A014486 in A055089. Permutation of A064640.

Views

Author

Keywords

Crossrefs

Programs

Maple

A129599 Prime-factorization encoded partition code for the Łukasiewicz-word, variant of A129593.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A082314 Involution of natural numbers: A057502-conjugate of A057164.

Views

Author

Keywords

Links

Crossrefs

Formula