A057509 -id:A057509 - cp's OEIS frontend

A127301 Matula-Goebel signatures for plane general trees encoded by A014486.

1, 2, 4, 3, 8, 6, 6, 7, 5, 16, 12, 12, 14, 10, 12, 9, 14, 19, 13, 10, 13, 17, 11, 32, 24, 24, 28, 20, 24, 18, 28, 38, 26, 20, 26, 34, 22, 24, 18, 18, 21, 15, 28, 21, 38, 53, 37, 26, 37, 43, 29, 20, 15, 26, 37, 23, 34, 43, 67, 41, 22, 29, 41, 59, 31, 64, 48, 48, 56, 40, 48, 36

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

This sequence maps A000108(n) oriented (plane) rooted general trees encoded in range [A014137(n-1)..A014138(n)] of A014486 to A000081(n+1) distinct non-oriented rooted general trees, encoded by their Matula-Goebel numbers. The latter encoding is explained in A061773.
A005517 and A005518 give the minimum and maximum value occurring in each such range.
Primes occur at positions given by A057548 (not in order, and with duplicates), and similarly, semiprimes, A001358, occur at positions given by A057518, and in general, A001222(a(n)) = A057515(n).
If the signature-permutation of a Catalan automorphism SP satisfies the condition A127301(SP(n)) = A127301(n) for all n, then it preserves the non-oriented form of a general tree, which implies also that it is Łukasiewicz-word permuting, satisfying A129593(SP(n)) = A129593(n) for all n >= 0. Examples of such automorphisms include A072796, A057508, A057509/A057510, A057511/A057512, A057164, A127285/A127286 and A127287/A127288.
A206487(n) tells how many times n occurs in this sequence. - Antti Karttunen, Jan 03 2013

			A000081(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, A014486(5) = 44 (= 101100 in binary = A063171(5)), encodes the following plane tree:
.....o
.....|
.o...o
..\./.
...*..
Matula-Goebel encoding for this tree gives a code number A000040(1) * A000040(A000040(1)) = 2*3 = 6, thus a(5)=6.
Likewise, A014486(6) = 50 (= 110010 in binary = A063171(6)) encodes the plane tree:
.o
.|
.o...o
..\./.
...*..
Matula-Goebel encoding for this tree gives a code number A000040(A000040(1)) * A000040(1) = 3*2 = 6, thus a(6) is also 6, which shows these two trees are identical if one ignores their orientation.

Antti Karttunen, Table of n, a(n) for n = 0..6917
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz
Index entries for sequences related to Matula-Goebel numbers

a(A014138(n)) = A007097(n+1), a(A014137(n)) = A000079(n+1) for all n.
a(|A106191(n)|) = A033844(n-1) for all n >= 1.
Cf. A001222, A005517, A005518, A057515, A057518, A057548, A127302, A129593, A153826, A209638, A243491, A243492, A243494, A243496.
For standard instead of binary encoding we have A358506.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists binary encodings of ordered rooted trees.
Cf. A001263, A061775, A196050, A206487, A358505.

mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
binbalQ[n_]:=n==0||With[{dig=IntegerDigits[n,2]},And@@Table[If[k==Length[dig],SameQ,LessEqual][Count[Take[dig,k],0],Count[Take[dig,k],1]],{k,Length[dig]}]];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]];
Table[mgnum[bint[n]],{n,Select[Range[0,1000],binbalQ]}] (* Gus Wiseman, Nov 22 2022 *)

(define (A127301 n) (*A127301 (A014486->parenthesization (A014486 n)))) ;; A014486->parenthesization given in A014486.
(define (*A127301 s) (if (null? s) 1 (fold-left (lambda (m t) (* m (A000040 (*A127301 t)))) 1 s)))

A001222(a(n)) = A057515(n) for all n.

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

Original entry on oeis.org

1, 2, 4, 10, 28, 136, 726, 5100, 40362, 363288, 3628810, 39921044, 479001612, 6227066928, 87178295296, 1307675013928, 20922789888016, 355687438476444, 6402373705728018, 121645100594641896, 2432902008177690360, 51090942175425331320, 1124000727777607680022

Offset: 1

Antti Karttunen, May 02 2001

If permutations are converted to (i,p(i)) permutation arrays, then this automorphism is obtained by their "SW-NE diagonal toroidal shifts" (see Matthias Engelhardt's Java program in A006841), while the Maple procedure below converts each permutation to a siteswap pattern (used in juggling), rotates it by one digit and converts the resulting new (or same) siteswap pattern back to a permutation.
When the subset of permutations listed by A064640 are subjected to the same automorphism one gets A002995.
The number of conjugacy classes of the symmetric group of degree n when conjugating only with the cyclic permutation group of degree n. - Attila Egri-Nagy, Aug 15 2014
Also the number of equivalence classes of permutations of {1...n} under the action of rotation of vertices in the cycle decomposition. The corresponding action on words applies m -> m + 1 for m < n and n -> 1, and rotates once to the right. For example, (24531) first becomes (35142) under the application of cyclic rotation, and then is rotated right to give (23514). - Gus Wiseman, Mar 04 2019

			If I have a five-element permutation like 25431, in cycle notation (1 2 5)(3 4), I mark the numbers 1-5 clockwise onto a circle and draw directed edges from 1 to 2, from 2 to 5, from 5 to 1 and a double-way edge between 3 and 4. All the 5-element permutations that produce some rotation (discarding the labels of the nodes) of that chord diagram belong to the same equivalence class with 25431. The sequence gives the count of such equivalence classes.

Cf. A006841, A060495. For other Maple procedures, see A060501 (Perm2SiteSwap2), A057502 (CountCycles), A057509 (rotateL), A060125 (PermRank3R and permul).
A061417[p] = A061860[p] = (p-1)!+(p-1) for all prime p's.
A064636 (derangements-the same automorphism).
A061417[n] = A064649[n]/n.
Cf. A000031, A000939, A002995, A008965, A060223, A064640, A086675 (digraphical necklaces), A179043, A192332, A275527 (path necklaces), A323858, A323859, A323870, A324513, A324514 (aperiodic permutations).

List([1..10],n->Size( OrbitsDomain( CyclicGroup(IsPermGroup,n), SymmetricGroup( IsPermGroup,n),\^))); # Attila Egri-Nagy, Aug 15 2014

a061417 = sum . a047917_row  -- Reinhard Zumkeller, Mar 19 2014

Algebraic formula: with(numtheory); SSRPCC := proc(n) local d,s; s := 0; for d in divisors(n) do s := s + phi(n/d)*((n/d)^d)*(d!); od; RETURN(s/n); end;
Empirically: with(group); SiteSwapRotationPermutationCycleCounts := proc(upto_n) local b,u,n,a,r; a := []; for n from 1 to upto_n do b := []; u := n!; for r from 0 to u-1 do b := [op(b),1+PermRank3R(SiteSwap2Perm1(rotateL(Perm2SiteSwap2(PermUnrank3Rfix(n,r)))))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
PermUnrank3Rfixaux := proc(n,r,p) local s; if(0 = n) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Rfixaux(n-1, r-(s*((n-1)!)), permul(p,[[n,n-s]]))); fi; end;
PermUnrank3Rfix := (n,r) -> convert(PermUnrank3Rfixaux(n,r,[]),'permlist',n);
SiteSwap2Perm1 := proc(s) local e,n,i,a; n := nops(s); a := []; for i from 1 to n do e := ((i+s[i]) mod n); if(0 = e) then e := n; fi; a := [op(a),e]; od; RETURN(convert(invperm(convert(a,'disjcyc')),'permlist',n)); end;

a[n_] := (1/n)*Sum[ EulerPhi[n/d]*(n/d)^d*d!, {d, Divisors[n]}]; Table[a[n], {n, 1, 21}] (* Jean-François Alcover, Oct 09 2012, from formula *)
Table[Length[Select[Permutations[Range[n]],#==First[Sort[NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]]]&]],{n,8}] (* Gus Wiseman, Mar 04 2019 *)

a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Indranil Ghosh, Apr 10 2017

from sympy import divisors, factorial, totient
def a(n):
    return sum(totient(n//d)*(n//d)**d*factorial(d) for d in divisors(n))//n
print([a(n) for n in range(1, 22)]) # Indranil Ghosh, Apr 10 2017

a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).

A127291 Signature-permutation of Elizalde's and Deutsch's 2003 bijection for Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 16 2007

Deutsch and Elizalde show in their paper that this automorphism converts certain properties concerning "tunnels" of Dyck path to another set of properties concerning the number of hills, even and odd rises, as well as the number of returns (A057515), thus proving the equidistribution of the said parameters.
This automorphism is implemented with function "tau" (Scheme code given below) that takes as its arguments an S-expression and a Catalan automorphism that permutes only the top level of the list (i.e., the top-level branches of a general tree, or the whole arches of a Dyck path) and thus when the permuting automorphism is applied to a list (parenthesization) of length 2n it induces some permutation of [1..2n].
This automorphism is induced in that manner by the automorphism *A127287 and likewise, *A127289 is induced by *A127285, *A057164 by *A057508, *A057501 by *A057509 and *A057502 by *A057510.
Note that so far these examples seem to satisfy the homomorphism condition, e.g., as *A127287 = *A127285 o *A057508 so is *A127291 = *A127289 o *A057164. and likewise, as *A057510 = *A057508 o *A057509 o *A057508, so is *A057502 = *A057164 o *A057501 o *A057164.
However, it remains open what are the exact criteria of the "picking automorphism" and the corresponding permutation that this method would induce a bijection. For example, if we give *A127288 (the inverse of *A127287) to function "tau" it will not induce *A127292 and actually not a bijection at all.
Instead, we have to compute the inverse of this automorphism with another, more specific algorithm that implements Deutsch's and Elizalde's description and is given in A127300.

A. Karttunen, Table of n, a(n) for n = 0..2055
Emeric Deutsch and Sergi Elizalde, A simple and unusual bijection for Dyck paths and its consequences, Annals of Combinatorics, 7 (2003), no. 3, 281-297.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A127292. a(n) = A127289(A057164(n)) = A057164(A127299(A057164(n))). A127291(A057548(n)) = A072795(A127291(n)), A127291(A072795(n)) = A127307(A127291(A057502(n))) for all n >= 1. The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A127293, A127294 and A127295. Number of fixed points begins as 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, ...

A034731 Dirichlet convolution of b_n=1 with Catalan numbers.

Original entry on oeis.org

1, 2, 3, 7, 15, 46, 133, 436, 1433, 4878, 16797, 58837, 208013, 743034, 2674457, 9695281, 35357671, 129646266, 477638701, 1767268073, 6564120555, 24466283818, 91482563641, 343059672916, 1289904147339, 4861946609466

Offset: 1

Erich Friedman

nonn

Also number of objects fixed by permutations A057509/A057510 (induced by shallow rotation of general parenthesizations/plane trees).

G. C. Greubel, Table of n, a(n) for n = 1..1000

Occurs for first time in A073202 as row 16.

Cf. A000108, A057509, A057510, A057546.

a[n_] := DivisorSum[n, CatalanNumber[#-1]&]; Array[a, 26] (* Jean-François Alcover, Dec 05 2015 *)

a(n) = sumdiv(n, d, binomial(2*(d-1),d-1)/d) \\ Michel Marcus, Jun 07 2013

{a(n) = my(A = sum(m=1, n, (1 - sqrt(1 - 4*x^m +x*O(x^n)))/2 )); polcoeff(A, n)}
for(n=1, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jan 12 2021

{a(n) = my(A = sum(m=1, n, binomial(2*m-2,m-1)/m * x^m/(1 - x^m +x*O(x^n)) )); polcoeff(A, n)}
for(n=1, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jan 12 2021

a(n) = Sum_{d divides n} C(d-1) where C() are the Catalan numbers (A000108).
a(n) ~ 4^(n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Dec 05 2015
L.g.f.: -log(Product_{k>=1} (1 - x^k)^(binomial(2*k-2,k-1)/k^2)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 23 2018
G.f.: Sum_{n>=1} (1 - sqrt(1 - 4*x^n))/2. - Paul D. Hanna, Jan 12 2021
G.f.: Sum_{n>=1} A000108(n-1) * x^n/(1 - x^n) where A000108(n) = binomial(2*n,n)/(n+1). - Paul D. Hanna, Jan 12 2021

More comments from Antti Karttunen, Jan 03 2003

A069775 Permutation of natural numbers induced by the automorphism gma069775! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

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 A069776. a(n) = A057163(A057509(A057163(n))) = A069773(A069770(n)). Cf. also A069787, A072797.

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

A123717 Signature permutation of a Catalan automorphism: row 253 of table A122203.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This is the signature-permutation of Catalan automorphism which is derived from nonrecursive Catalan automorphism *A123503 with the recursion schema SPINE (defined in A122203).

The number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation begins as 1,1,2,1,3,1,4,1,8,1,16,1,47,..., the LCM of cycle sizes as 1,1,1,2,12,12,120,120,840,840,5040,5040,55440,... (cf. A089423) and the cycle-count sequence seems to be A045629. (To be proved.)

A. Karttunen, paper in preparation, draft available by e-mail.

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123718. a(n) = A057509(A089854(n)). Row 253 of A122203.

A130919 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057511.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 11 2007

nonn

*A130919 = DEEPEN(*A057511) = NEPEED(*A057511) = DEEPEN(DEEPEN(*A057509)) = NEPEED(NEPEED(*A057509)). See A122283, A122284 for the definitions of DEEPEN and NEPEED transforms.

Inverse: A130920. A122351(n) = A083927(A130919(A057123(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 A130967 and A130968. Maximum cycle sizes seems to be given by A000793 (shifted once 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

cp's OEIS Frontend

A127301 Matula-Goebel signatures for plane general trees encoded by A014486.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Python

Formula

A127291 Signature-permutation of Elizalde's and Deutsch's 2003 bijection for Dyck paths.

Views

Author

Keywords

Comments

Links

Crossrefs

A034731 Dirichlet convolution of b_n=1 with Catalan numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A069775 Permutation of natural numbers induced by the automorphism gma069775! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A123717 Signature permutation of a Catalan automorphism: row 253 of table A122203.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A130919 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057511.

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