cp's OEIS Frontend

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.

%I A060502 #86 May 17 2025 00:33:53
%S A060502 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,
%T A060502 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,
%U A060502 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
%N 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.
%C A060502 From _Antti Karttunen_, Aug 11-24 2016: (Start)
%C A060502 a(n) gives the number of occupied "digit slopes" in the factorial base representation of n, or more formally, the number of distinct elements in a multiset [(i_x - d_x) | where d_x ranges over each nonzero digit present in factorial base representation of n and i_x is that digit's position from the right]. Here one-based indexing is used, thus the least significant digit is in position 1. Each value {digit's position} - {digit's value} determines on which slope that particular nonzero digit is. The nonzero digits for which (position - digit) = 0, are said to be on the "maximal slope" (see A260736), those with value 1 on "sub-maximal", etc.
%C A060502 The number of occupied digit slopes translates directly to the number of drops in the n-th permutation as given in the list A060117 because only the largest (and thus leftmost) of all nonzero digits on any particular slope adds a (single) drop to the permutation, when constructed by the unranking algorithm employed in A060117.
%C A060502 The original definition of this sequence is (essentially):
%C A060502   a(n) = the average of digits (where "digits" may eventually obtain also any values > 9) in each siteswap pattern A060498(n) constructed from each permutation in list A060117, which is equal to number of balls used in that pattern.
%C A060502 The equivalence of the old and the new definitions is seen from the following (as kindly pointed by _Olivier Gérard_ in personal mail): For any permutation p of [1..n], Sum(i=1..n) p(i)-i = 0 (whether taken modulo n or not), thus Sum(i=1..n) (p(i)-i modulo n) = Sum(i={set of nondrops}) (p(i)-i) + Sum(i={set of drops}) (n + (p(i)-i)) = 0 + n * #{set of drops}, where drops is the set of those i where p[i] < i and nondrops are those i for which p[i] >= 1.
%C A060502 Involution A225901 maps this metric to another metric A275806 which gives the number of distinct nonzero digits in factorial base representation of n. See also A275811.
%C A060502 A007489 (repunits in this context) gives the positions where a(n) = A084558(n) (the length of factorial base representation of n). These are also the positions of records.
%C A060502 (End)
%H A060502 Antti Karttunen, <a href="/A060502/b060502.txt">Table of n, a(n) for n = 0..40320</a>
%H A060502 <a href="/index/Fa#facbase">Index entries for sequences related to factorial base representation</a>
%F A060502 From _Antti Karttunen_, Aug 11-21 2016: (Start)
%F A060502 The following formula reflects the original definition of computing the average, with a few unnecessary steps eliminated:
%F A060502 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).
%F A060502 a(n) = Sum_{i=1..s} [p[i]<i]. [This is equal to the number of drops in permutation p (see comments).]
%F A060502 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].
%F A060502 Following formulas do not need intermediate construction of permutation lists:
%F A060502 a(n) = A001221(A275734(n)).
%F A060502 a(n) = A275806(A225901(n)).
%F A060502 a(n) = A000120(A276010(n)).
%F A060502 Other identities and observations. For all n >= 0:
%F A060502 a(n) = A275946(n) + A275947(n).
%F A060502 a(n) = A060500(A060125(n)).
%F A060502 a(n) = A060128(n) + A276004(n).
%F A060502 a(n) = A060129(n) - A060500(n).
%F A060502 a(n) = A084558(n) - A275849(n) = 1 + A084558(n) - A060501(n).
%F A060502 a(A007489(n)) = n. [Particularly, A007489(n) gives the position of the first occurrence of each n.]
%F A060502 A060128(n) <= a(n) <= A060129(n).
%F A060502 a(n!) = 1.
%F A060502 a(A033312(n)) = 1 for all n > 1.
%F A060502 a(A059590(n)) = A000120(n).
%F A060502 a(A060112(n)) = A007895(n).
%F A060502 a(n) = a(A153880(n)) = a(A255411(n)). [The shift-operations do not change the number of distinct slopes.]
%F A060502 a(A275804(n)) = A060130(A275804(n)). [A275804 gives all the positions where this coincides with A060130.]
%F A060502 (End)
%e A060502 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.
%e A060502 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.
%e A060502 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.
%p A060502 # The following program follows the original 2001 interpretation of this sequence:
%p A060502 A060502 := n -> avg(Perm2SiteSwap3(PermUnrank3R(n)));
%p A060502 with(group);
%p A060502 permul := (a, b) -> mulperms(b, a);
%p A060502 # factorial_base(n) gives the digits of A007623(n) as a list, uncorrupted even when there are digits > 9:
%p A060502 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;
%p A060502 # PermUnrank3R(r) gives the permutation with rank r in list A060117:
%p A060502 PermUnrank3R := proc(r) local n; n := nops(factorial_base(r)); convert(PermUnrank3Raux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end;
%p A060502 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;
%p A060502 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;
%p A060502 avg := a -> (convert(a, `+`)/nops(a));
%o A060502 (Scheme, different versions)
%o A060502 (define (A060502 n) (A001221 (A275734 n)))
%o A060502 (define (A060502 n) (A275806 (A225901 n)))
%o A060502 ;; This version follows the original definition (where we count the average of siteswap-"digits", that is, the number of balls. A few unnecessary twists of the original Maple-programs have been optimized away:
%o A060502 (define (A060502 n) (let ((s (+ 1 (A084558 n))) (p (A060118permvec-short n))) (let loop ((a 0) (i 1)) (if (> i s) (/ a s) (loop (+ a (modulo (- i (vector-ref p (- i 1))) s)) (+ 1 i))))))
%o A060502 (define (A060502 n) (let ((s (+ 1 (A084558 n))) (p (A060117permvec-short n))) (let loop ((a 0) (i 1)) (if (> i s) (/ a s) (loop (+ a (modulo (- (vector-ref p (- i 1)) i) s)) (+ 1 i))))))
%o A060502 ;; By the proof given in comments, that average is equal to the number of drops in permutations obtained from list A060117:
%o A060502 (define (A060502 n) (let ((s (+ 1 (A084558 n))) (p (A060117permvec-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))))))
%o A060502 (define (A060117permvec-short rank) (permvec1inverse-of (permute-A060118 (make-initialized-vector (+ 1 (A084558 rank)) 1+) (+ 1 (A084558 rank)) rank)))
%o A060502 (define (permvec1inverse-of permvec) (make-initialized-vector (vector-length permvec) (lambda (i) (permvec1find-pos-of-i-from (+ 1 i) permvec))))
%o A060502 (define (permvec1find-pos-of-i-from i permvec) (let loop ((k 0)) (cond ((= k (vector-length permvec)) #f) ((= i (vector-ref permvec k)) (+ 1 k)) (else (loop (+ k 1))))))
%o A060502 (define (A060118permvec-short rank) (permute-A060118 (make-initialized-vector (+ 1 (A084558 rank)) 1+) (+ 1 (A084558 rank)) rank))
%o A060502 (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)))))))
%Y A060502 Cf. A000120, A001221, A007489, A007623, A033312, A060117, A060118, A060130, A060498, A225901, A275734, A275806.
%Y A060502 Cf. A007489 (positions of records, the first occurrence of each n).
%Y A060502 Cf. A276001, A276002, A276003 (positions where a(n) obtains values 1, 2, 3).
%Y A060502 Cf. also A060500, A060501, A060125, A084558, A153880, A255411, A260736, A273670, A275804, A275811, A275946, A275947, A275849, A275956, A276004,
%Y A060502 A276005, A276010.
%K A060502 nonn,base
%O A060502 0,4
%A A060502 _Antti Karttunen_, Mar 22 2001
%E A060502 Entry revised, with a new interpretation and formulas. Maple-code cleaned up. - _Antti Karttunen_, Aug 11 2016
%E A060502 Another new interpretation added and the original definition moved to the comments - _Antti Karttunen_, Aug 24 2016