A060129 -id:A060129 - 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.

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

Antti Karttunen, Mar 22 2001

From Antti Karttunen, Aug 11-24 2016: (Start)
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.
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.
The original definition of this sequence is (essentially):
  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.
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.
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.
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.
(End)

			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.

Antti Karttunen, Table of n, a(n) for n = 0..40320
Index entries for sequences related to factorial base representation

Cf. A000120, A001221, A007489, A007623, A033312, A060117, A060118, A060130, A060498, A225901, A275734, A275806.
Cf. A007489 (positions of records, the first occurrence of each n).
Cf. A276001, A276002, A276003 (positions where a(n) obtains values 1, 2, 3).
Cf. also A060500, A060501, A060125, A084558, A153880, A255411, A260736, A273670, A275804, A275811, A275946, A275947, A275849, A275956, A276004,
A276005, A276010.

# 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));

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:
a(n) = A001221(A275734(n)).
a(n) = A275806(A225901(n)).
a(n) = A000120(A276010(n)).
Other identities and observations. For all n >= 0:
a(n) = A275946(n) + A275947(n).
a(n) = A060500(A060125(n)).
a(n) = A060128(n) + A276004(n).
a(n) = A060129(n) - A060500(n).
a(n) = A084558(n) - A275849(n) = 1 + A084558(n) - A060501(n).
a(A007489(n)) = n. [Particularly, A007489(n) gives the position of the first occurrence of each n.]
A060128(n) <= a(n) <= A060129(n).
a(n!) = 1.
a(A033312(n)) = 1 for all n > 1.
a(A059590(n)) = A000120(n).
a(A060112(n)) = A007895(n).
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)

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

A275725 a(n) = A275723(A002110(1+A084558(n)), n); prime factorization encodings of cycle-polynomials computed for finite permutations listed in the order that is used in tables A060117 / A060118.

Original entry on oeis.org

2, 4, 18, 8, 12, 8, 150, 100, 54, 16, 24, 16, 90, 40, 54, 16, 36, 16, 60, 40, 36, 16, 24, 16, 1470, 980, 882, 392, 588, 392, 750, 500, 162, 32, 48, 32, 270, 80, 162, 32, 108, 32, 120, 80, 72, 32, 48, 32, 1050, 700, 378, 112, 168, 112, 750, 500, 162, 32, 48, 32, 450, 200, 162, 32, 72, 32, 300, 200, 108, 32, 48, 32, 630, 280, 378, 112, 252, 112, 450, 200

Offset: 0

Antti Karttunen, Aug 09 2016

nonn

In this context "cycle-polynomials" are single-variable polynomials where the coefficients (encoded with the exponents of prime factorization of n) are equal to the lengths of cycles in the permutation listed with index n in tables A060117 or A060118. See the examples.

			Consider the first eight permutations (indices 0-7) listed in A060117:
  1 [Only the first 1-cycle explicitly listed thus a(0) = 2^1 = 2]
  2,1 [One transposition (2-cycle) in beginning, thus a(1) = 2^2 = 4]
  1,3,2 [One fixed element in beginning, then transposition, thus a(2) = 2^1 * 3^2 = 18]
  3,1,2 [One 3-cycle, thus a(3) = 2^3 = 8]
  3,2,1 [One transposition jumping over a fixed element, a(4) = 2^2 * 3^1 = 12]
  2,3,1 [One 3-cycle, thus a(5) = 2^3 = 8]
  1,2,4,3 [Two 1-cycles, then a 2-cycle, thus a(6) = 2^1 * 3^1 * 5^2 = 150].
  2,1,4,3 [Two 2-cycles, not crossed, thus a(7) = 2^2 * 5^2 = 100]
and also the seventeenth one at n=16 [A007623(16)=220] where we have:
  3,4,1,2 [Two 2-cycles crossed, thus a(16) = 2^2 * 3^2 = 36].

Antti Karttunen, Table of n, a(n) for n = 0..40319
Indranil Ghosh, Python program for computing this sequence
Index entries for sequences related to factorial base representation

Cf. A000040, A001222, A001221, A002110, A007814, A046660, A048675, A051903, A056169, A056170, A084558, A243054, A257510, A275723, A275803, A275832.
Cf. A275807 (terms divided by 2).
Cf. also A060129, A060128, A060130, A060131, A072411, A275726, A275812, A275851.
Cf. also A275733, A275734, A275735 for other such prime factorization encodings of A060117/A060118-related polynomials.

(define (A275725 n) (A275723bi (A002110 (+ 1 (A084558 n))) n)) ;; Code for A275723bi given in A275723.

a(n) = A275723(A002110(1+A084558(n)), n).
Other identities:
A001221(a(n)) = 1+A257510(n) (for all n >= 1).
A001222(a(n)) = 1+A084558(n).
A007814(a(n)) = A275832(n).
A048675(a(n)) = A275726(n).
A051903(a(n)) = A275803(n).
A056169(a(n)) = A275851(n).
A046660(a(n)) = A060130(n).
A072411(a(n)) = A060131(n).
A056170(a(n)) = A060128(n).
A275812(a(n)) = A060129(n).
a(n!) = 2 * A243054(n) = A000040(n)*A002110(n) for all n >= 1.

A060128 a(n) is the number of disjoint cycles (excluding 1-cycles, i.e., fixed elements) in the n-th permutation of A060117 and A060118.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2

Offset: 0

Antti Karttunen, Mar 05 2001

nonn

Antti Karttunen, Table of n, a(n) for n = 0..40320
Index entries for sequences related to factorial base representation

Cf. A055090, A056170, A060118, A060120, A060129, A060130, A275725, A278225, A276004.

Cf. A276005 (positions where coincides with A060502).

A060128(n) = nops(convert(PermUnrank3L(n), 'disjcyc')); # Code for function PermUnrank3L given in A060118.

a(n) = A060129(n) - A060130(n).
From Antti Karttunen, Aug 07 2017: (Start)
a(n) = A056170(A275725(n)).
a(n) = A055090(A060120(n)).
a(n) = A060502(n) - A276004(n).
(End)

A055093 Number of moved (non-fixed) elements in each permutation given in reversed colexicographic ordering A055089, i.e., the sum of their cycle lengths (excluding the 1-cycles, i.e., fixed elements).

Original entry on oeis.org

0, 2, 2, 3, 3, 2, 2, 4, 3, 4, 4, 3, 3, 4, 2, 3, 4, 4, 4, 3, 3, 2, 4, 4, 2, 4, 4, 5, 5, 4, 3, 5, 4, 5, 5, 4, 4, 5, 3, 4, 5, 5, 5, 4, 4, 3, 5, 5, 3, 5, 4, 5, 5, 4, 2, 4, 3, 4, 4, 3, 4, 5, 4, 5, 5, 5, 5, 4, 5, 4, 5, 5, 4, 5, 3, 4, 5, 5, 3, 4, 2, 3, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 5, 5, 4, 4, 5, 4, 4, 3, 5, 5, 4, 3, 3

Offset: 0

Antti Karttunen, Apr 04 2000

nonn

Also number of displacements for permutations in lexicographic order. - Joerg Arndt, Jan 22 2024

Antti Karttunen, Table of n, a(n) for n = 0..40320
Tilman Piesk, Permutations and partitions in the OEIS (Wikiversity)
Index entries for sequences related to factorial base representation

Cf. A055089, A055090, A055091, A055092, A060129, A275812, A290095.

A055093(n) = count_nonfixed(convert(PermRevLexUnrank(j), 'disjcyc')).
count_nonfixed := l -> convert(map(nops,l), `+`);
# Procedure PermRevLexUnrank given in A055089.

a(n) = A055090(n) + A055091(n).

a(n) = A275812(A290095(n)) = A060129(A060126(n)). - Antti Karttunen, Dec 30 2017

Entry revised by Antti Karttunen, Dec 30 2017

A275851 a(n) = number of elements in range [1..(1+A084558(n))] fixed by the permutation with rank n of permutation list A060117 (or A060118).

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 2, 1, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 3, 1, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 2, 1, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 3, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 3, 2, 2, 1, 1, 1, 1, 0, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 3, 2, 1, 1, 2, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 4

Offset: 0

Antti Karttunen, Aug 11 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..40320
Index entries for sequences related to factorial base representation

Cf. A060117, A060118.
Cf. A056169, A060129, A084558, A275725.
Cf. A275852 (indices of zeros).

a(n) = A056169(A275725(n)).

a(n) = 1 + A084558(n) - A060129(n).

A278225 Filter-sequence for factorial base (cycles in A060117/A060118-permutations): Least number with the same prime signature as A275725.

Original entry on oeis.org

2, 4, 12, 8, 12, 8, 60, 36, 24, 16, 24, 16, 60, 24, 24, 16, 36, 16, 60, 24, 36, 16, 24, 16, 420, 180, 180, 72, 180, 72, 120, 72, 48, 32, 48, 32, 120, 48, 48, 32, 72, 32, 120, 48, 72, 32, 48, 32, 420, 180, 120, 48, 120, 48, 120, 72, 48, 32, 48, 32, 180, 72, 48, 32, 72, 32, 180, 72, 72, 32, 48, 32, 420, 120, 120, 48, 180, 48, 180, 72, 48, 32, 72, 32, 120, 48, 48

Offset: 0

Antti Karttunen, Nov 16 2016

nonn

This sequence can be used for filtering certain sequences related to cycle-structures in finite permutations as ordered by lists A060117 / A060118 (and thus also related to factorial base representation, A007623) because it matches only with any such sequence b that can be computed as b(n) = f(A275725(n)), where f(n) is any function that depends only on the prime signature of n (some of these are listed under the index entry for "sequences computed from exponents in ...").

Matching in this context means that the sequence a matches with the sequence b iff for all i, j: a(i) = a(j) => b(i) = b(j). In other words, iff the sequence b partitions the natural numbers to the same or coarser equivalence classes (as/than the sequence a) by the distinct values it obtains.

Cf. A007623, A060117, A060118, A046523, A275725.
Other filter-sequences related to factorial base: A278234, A278235, A278236.
Sequences that partition N into same or coarser equivalence classes: A048764, A048765, A060129, A060130, A060131, A084558, A275803, A275851, A257510.

(define (A278225 n) (A046523 (A275725 n)))

a(n) = A046523(A275725(n)).

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

Original entry on oeis.org

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

Antti Karttunen, Mar 22 2001

nonn

Antti Karttunen, Table of n, a(n) for n = 0..40320
Index entries for sequences related to factorial base representation

Cf. A060125, A060129, A060501, A060502, A275849, A275851.

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

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

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].
a(n) = A060502(A060125(n)).
a(n) = A060129(n) - A060502(n).
a(n) = A060501(n) - A275851(n) = 1 + A275849(n) - A275851(n).
(End)

Maple code collected together, alternative definition and new formulas added by Antti Karttunen, Aug 24 2016

Showing 1-9 of 9 results.

cp's OEIS Frontend

A060117 A list of all finite permutations in "PermUnrank3R" ordering. (Inverses of the permutations of A060118.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A060130 Number of nonzero digits in factorial base representation (A007623) of n; minimum number of transpositions needed to compose each permutation in the lists A060117 & A060118.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Scheme

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A275725 a(n) = A275723(A002110(1+A084558(n)), n); prime factorization encodings of cycle-polynomials computed for finite permutations listed in the order that is used in tables A060117 / A060118.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A060128 a(n) is the number of disjoint cycles (excluding 1-cycles, i.e., fixed elements) in the n-th permutation of A060117 and A060118.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A055093 Number of moved (non-fixed) elements in each permutation given in reversed colexicographic ordering A055089, i.e., the sum of their cycle lengths (excluding the 1-cycles, i.e., fixed elements).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A275851 a(n) = number of elements in range [1..(1+A084558(n))] fixed by the permutation with rank n of permutation list A060117 (or A060118).

Views

Author

Keywords

Links

Crossrefs

Formula

A278225 Filter-sequence for factorial base (cycles in A060117/A060118-permutations): Least number with the same prime signature as A275725.

Views

Author

Keywords

Comments