A060502 a(n) = number of occupied digit slopes in the factorial base representation of n (see comments for the definition); number of drops in the n-th permutation of list A060117.
0, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 3, 2, 2, 2, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1
Offset: 0
Examples
For n=23 ("321" in factorial base representation, A007623), all the digits are maximal for their positions (they occur on the "maximal slope"), thus there is only one distinct digit slope present and a(23)=1. Also, for the 23rd permutation in the ordering A060117, [2341], there is just one drop, as p[4] = 1 < 4.
For n=29 ("1021"), there are three nonzero digits, where both 2 and the rightmost 1 are on the maximal slope, while the most significant 1 is on the "sub-sub-sub-maximal", thus there are two occupied slopes in total, and a(29) = 2. In the 29th permutation of A060117, [23154], there are two drops as p[3] = 1 < 3 and p[5] = 4 < 5.
For n=37 ("1201"), there are three nonzero digits, where the rightmost 1 is on the maximal slope, 2 is on the submaximal, and the most significant 1 is on the "sub-sub-sub-maximal", thus there are three occupied slopes in total, and a(37) = 3. In the 37th permutation of A060117, [51324], there are three drops at indices 2, 4 and 5.
Links
Crossrefs
Cf. A000120, A001221, A007489, A007623, A033312, A060117, A060118, A060130, A060498, A225901, A275734, A275806.
Cf. A007489 (positions of records, the first occurrence of each n).
Programs
-
Maple
# The following program follows the original 2001 interpretation of this sequence: A060502 := n -> avg(Perm2SiteSwap3(PermUnrank3R(n))); with(group); permul := (a, b) -> mulperms(b, a); # factorial_base(n) gives the digits of A007623(n) as a list, uncorrupted even when there are digits > 9: factorial_base := proc(nn) local n, a, d, j, f; n := nn; if(0 = n) then RETURN([0]); fi; a := []; f := 1; j := 2; while(n > 0) do d := floor(`mod`(n, (j*f))/f); a := [d, op(a)]; n := n - (d*f); f := j*f; j := j+1; od; RETURN(a); end; # PermUnrank3R(r) gives the permutation with rank r in list A060117: PermUnrank3R := proc(r) local n; n := nops(factorial_base(r)); convert(PermUnrank3Raux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end; PermUnrank3Raux := proc(n, r, p) local s; if(0 = r) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Raux(n-1, r-(s*((n-1)!)), permul(p, [[n, n-s]]))); fi; end; Perm2SiteSwap3 := proc(p) local ip,n,i,a; n := nops(p); ip := convert(invperm(convert(p,'disjcyc')),'permlist',n); a := []; for i from 1 to n do if(0 = ((ip[i]-i) mod n)) then a := [op(a),0]; else a := [op(a), n-((ip[i]-i) mod n)]; fi; od; RETURN(a); end; avg := a -> (convert(a, `+`)/nops(a));
Formula
From Antti Karttunen, Aug 11-21 2016: (Start)
The following formula reflects the original definition of computing the average, with a few unnecessary steps eliminated:
a(n) = 1/s * Sum_{i=1..s} ((p[i]-i) modulo s), where p is the permutation of rank n as ordered in the list A060117, and s is its size (the number of its elements) computed as s = 1+A084558(n).
a(n) = Sum_{i=1..s} [p[i]
a(n) = 1/s * Sum_{i=1..s} ((i-p[i]) modulo s). [If inverse permutations from list A060118 are used, then we just flip the order of difference that is used in the first formula].
Following formulas do not need intermediate construction of permutation lists:
Other identities and observations. For all n >= 0:
a(n!) = 1.
a(A033312(n)) = 1 for all n > 1.
a(n) = a(A153880(n)) = a(A255411(n)). [The shift-operations do not change the number of distinct slopes.]
a(A275804(n)) = A060130(A275804(n)). [A275804 gives all the positions where this coincides with A060130.]
(End)
Extensions
Entry revised, with a new interpretation and formulas. Maple-code cleaned up. - Antti Karttunen, Aug 11 2016
Another new interpretation added and the original definition moved to the comments - Antti Karttunen, Aug 24 2016
A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.
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
Comments
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
Examples
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.
Links
Crossrefs
Programs
-
GAP
List([1..10],n->Size( OrbitsDomain( CyclicGroup(IsPermGroup,n), SymmetricGroup( IsPermGroup,n),\^))); # Attila Egri-Nagy, Aug 15 2014
-
Haskell
a061417 = sum . a047917_row -- Reinhard Zumkeller, Mar 19 2014
-
Maple
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;
-
Mathematica
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 *) -
PARI
a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Indranil Ghosh, Apr 10 2017
-
Python
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
Formula
a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).
A060495 Each permutation in the list A060117 converted to Site Swap notation, with "zero throws" (fixed elements) replaced with n, the length of siteswap.
1, 11, 312, 111, 231, 222, 4413, 1313, 4112, 1111, 2411, 2312, 4242, 1241, 4233, 1223, 2222, 2231, 3441, 3342, 3131, 3122, 3423, 3333, 55514, 14514, 51414, 11314, 25314, 24414, 55113, 14113, 51112, 11111, 25111, 24112, 52512, 12511, 52413
Offset: 0
Comments
This sequence is not well-defined for n >= 3628800 because the Site Swap notation can contain values exceeding 9, for example, the Site Swap notation for a(3628800) is [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 10]. - Sean A. Irvine, Nov 25 2022
Crossrefs
Programs
-
Maple
Perm2SiteSwap1 := proc(p) local ip,n,i,a; n := nops(p); ip := convert(invperm(convert(p,'disjcyc')),'permlist',n); a := []; for i from 1 to n do a := [op(a),((ip[i]-i) mod n)]; od; RETURN(a); end; SiteSwap1ToDec := proc(s) local i,z,n; n := nops(s); z := 0; for i from 1 to n do z := 10*z; if(0 = s[i]) then z := z+n; else z := z+s[i]; fi; od; RETURN(z); end;
Formula
a(n) = SiteSwap1ToDec(Perm2SiteSwap1(PermUnrank3R(n))).
A275849 Number of unoccupied slopes in factorial base representation of n: a(n) = A084558(n) - A060502(n).
0, 0, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 2, 1, 2, 2, 2, 1, 1, 0, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 3, 2, 2, 2, 2, 1, 2, 1, 1, 1, 3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3, 4
Offset: 0
Links
Crossrefs
A060500 a(n) = number of drops in the n-th permutation of list A060118; the average of digits (where "digits" may eventually obtain also any values > 9) in each siteswap pattern A060496(n).
0, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 1, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 3, 3, 3, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2
Offset: 0
Keywords
Links
Programs
-
Maple
A060500 := avg(Perm2SiteSwap1(PermUnrank3R(n))); # PermUnrank3R(r) gives the permutation with rank r in list A060117: PermUnrank3R := proc(r) local n; n := nops(factorial_base(r)); convert(PermUnrank3Raux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end; PermUnrank3Raux := proc(n, r, p) local s; if(0 = r) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Raux(n-1, r-(s*((n-1)!)), permul(p, [[n, n-s]]))); fi; end; Perm2SiteSwap1 := proc(p) local ip, n, i, a; n := nops(p); ip := convert(invperm(convert(p, 'disjcyc')), 'permlist', n); a := []; for i from 1 to n do a := [op(a), ((ip[i]-i) mod n)]; od; RETURN(a); end; avg := a -> (convert(a,`+`)/nops(a));
-
Scheme
(define (A060500 n) (let ((s (+ 1 (A084558 n))) (p (A060118permvec-short n))) (let loop ((d 0) (i 1)) (if (> i s) d (loop (+ d (if (< (vector-ref p (- i 1)) i) 1 0)) (+ 1 i)))))) (define (A060118permvec-short rank) (permute-A060118 (make-initialized-vector (+ 1 (A084558 rank)) 1+) (+ 1 (A084558 rank)) rank)) (define (permute-A060118 elems size permrank) (let ((p (vector-head elems size))) (let unrankA060118 ((r permrank) (i 1)) (cond ((zero? r) p) (else (let* ((j (1+ i)) (m (modulo r j))) (cond ((not (zero? m)) (let ((org-i (vector-ref p i))) (vector-set! p i (vector-ref p (- i m))) (vector-set! p (- i m) org-i)))) (unrankA060118 (/ (- r m) j) j)))))))
Formula
From Antti Karttunen, Aug 18 2016: (Start)
The following formula reflects the original definition of computing the average, with a few unnecessary steps eliminated:
a(n) = 1/s * Sum_{i=1..s} ((i-p[i]) modulo s), where p is the permutation of rank n as ordered in the list A060117, and s is its size (the number of its elements) computed as s = 1+A084558(n).
a(n) = 1/s * Sum_{i=1..s} ((p[i]-i) modulo s). [If inverse permutations from list A060118 are used, then we just flip the order of difference that is used in the first formula].
a(n) = Sum_{i=1..s} [p[i]A060502 for the proof].
(End)
Extensions
Maple code collected together, alternative definition and new formulas added by Antti Karttunen, Aug 24 2016
A275853 a(n) = A060502(n) + A275851(n).
1, 1, 2, 2, 2, 1, 3, 2, 3, 3, 3, 2, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 4, 3, 3, 3, 3, 2, 4, 3, 4, 4, 4, 3, 4, 4, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 4, 3, 4, 4, 4, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 2, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2, 2, 4, 3, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 5
Offset: 0
Comments
These are averages (number of balls) in siteswap-patterns constructed like in A060498, but with 0's replaced by the length of the pattern.
Comments