A057502 -id:A057502 - cp's OEIS frontend

A065163 Maximal orbit size in the symmetric group partitioned by the upper records version of the Foata transform (i.e., a(n) is the maximum cycle length found in the corresponding permutations A065181-A065184 in range [0, n!-1]).

1, 1, 3, 7, 25, 216, 963, 23435, 92225, 2729205, 17313348, 182553725, 4235194171

Offset: 1

Antti Karttunen, Oct 19 2001

Note: the number of fixed terms in each successive range [0, n!-1] is given by A000045(n+1) (Fibonacci numbers) and the corresponding positions by A060112. (Foata transform fixes a permutation only if it is composed of disjoint adjacent transpositions.)

This version of the Foata transform is one of several. This map takes a permutation s in S_n with k cycles to a permutation t in S_n with k upper records, i.e., k indices i for which t(i) > max{t(j): j < i}. - Theodore Zhu, Aug 15 2014

Cf. A065161, A065162.

For the requisite Maple procedures see sequences A057502, A057542, A060117, A060125.

FoataPermutationCycleCounts_Lengths_and_LCM := proc(upto_n) local u,n,a,b,i,f; a := []; b := []; f := 1; for i from 0 to upto_n! -1 do b := [op(b),1+PermRank3R(Foata(PermUnrank3R(i)))]; if((f - 1) = i) then a := [op(a),[CountCycles(b), CycleLengths1(b), CyclesLCM(b)]]; print (a); f := f*(nops(a)+1); fi; od; RETURN(a); end;
lcmlist := proc(a) local z,e; z := 1; for e in a do z := ilcm(z,e); od; RETURN(z); end;
CyclesLCM := b -> lcmlist(map(nops,convert(b,'disjcyc')));

More terms from Theodore Zhu, Aug 15 2014

A069774 Permutation of natural numbers induced by the automorphism RoblDownCar_et_SwapInv! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Inverse of A069773, the car/cdr-flipped conjugate of A057502, i.e. A069774(n) = A057163(A057502(A057163(n))). Cf. also A069776.

A082313 Involution of natural numbers: A057501-conjugate of A057164.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 17 2003. Proposed by Wouter Meeussen in Dec 15 2001

nonn

Note: This is isomorphic with Meeussen's "skewcatacycleft" operation acting on the interpretation (gg) of the exercise 19 by Stanley.

a(n) = A069888(A057502(n)). Occurs in A073200 as row 604463486276865131809167. Cf. also A082314, A082315, A082333, A082334.

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) = A057501(A057164(A057502(n)))

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

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

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

Inverse: A086427. a(n) = A086431(A086427(A086431(n))) = A057164(A085174(A057164(n))) = A086425(A057502(A086426(n))). Occurs in A073200. Cf. also A086430 (whole step rotate).

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

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

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

Original entry on oeis.org

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

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: A085173. a(n) = A085161(A085173(A085161(n))) = A085169(A057502(A085170(n))) = A074684(A057502(A074683(n))). Occurs in A073200. Cf. also A085160 (whole step rotate), A086428.

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

A123502 Signature permutation of a Catalan automorphism: first recurse into the left subtree of the right hand side subtree of a binary tree and after that apply *A123498 at the root.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 5, 6, 8, 9, 10, 17, 16, 18, 11, 20, 12, 14, 15, 13, 19, 21, 22, 23, 24, 25, 26, 27, 45, 46, 44, 42, 49, 48, 43, 47, 50, 28, 29, 54, 53, 55, 30, 57, 31, 37, 38, 32, 39, 40, 41, 33, 61, 34, 51, 52, 35, 56, 58, 59, 36, 60, 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: A123501. A057502(n) = A083927(a(A057123(n))) = A083927(A085160(A057123(n))).

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.

A064639 Positions of non-crossing fixed-point-free involutions encoded by A014486 (after reflection) in A055089. Permutation of A064640.

Original entry on oeis.org

0, 1, 7, 23, 127, 143, 415, 659, 719, 5167, 5183, 5455, 5699, 5759, 16687, 16703, 26815, 36899, 36959, 28495, 38579, 40031, 40319, 368047, 368063, 368335, 368579, 368639, 379567, 379583, 389695, 399779, 399839, 391375, 401459, 402911, 403199

Offset: 0

Antti Karttunen, Oct 15 2001

nonn

Maple procedure deepreverse given in A057502, for others, follow A064638. Same sequence sorted: A064640.

map(PermRevLexRank,map(NonCrossingTransposRev, A014486)); NonCrossingTransposRev := n -> convert(NonCrossingTransposAux(deepreverse(binexp2pars(n)),1),'permlist',binwidth(n));

cp's OEIS Frontend

A065163 Maximal orbit size in the symmetric group partitioned by the upper records version of the Foata transform (i.e., a(n) is the maximum cycle length found in the corresponding permutations A065181-A065184 in range [0, n!-1]).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A069774 Permutation of natural numbers induced by the automorphism RoblDownCar_et_SwapInv! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A082313 Involution of natural numbers: A057501-conjugate of A057164.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

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

Views

Author

Keywords

Comments

Links

Crossrefs

A123502 Signature permutation of a Catalan automorphism: first recurse into the left subtree of the right hand side subtree of a binary tree and after that apply *A123498 at the root.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A064639 Positions of non-crossing fixed-point-free involutions encoded by A014486 (after reflection) in A055089. Permutation of A064640.

Views

Author

Keywords

Crossrefs

Programs

Maple