login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A129594 Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n. 18

%I #30 Jan 26 2014 13:31:50

%S 0,1,3,2,4,7,6,5,11,12,15,8,9,14,13,10,20,27,28,19,16,31,24,23,22,25,

%T 30,17,18,29,26,21,43,52,59,36,35,60,51,44,47,48,63,32,39,56,55,40,41,

%U 54,57,38,33,62,49,46,45,50,61,34,37,58,53,42,84,107,116,75,68,123

%N Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n.

%C This sequence is based on the fact that compositions (i.e. ordered partitions) can be mapped 1-to-1 to partitions by taking the partial sums of the list where one is subtracted from each composant except the first. (See table A227189 where the parts for each partition are listed).

%C The inverse process, from partitions to compositions, occurs by inserting the first (i.e. smallest) element of a partition sorted into ascending order to the front of the list obtained by adding one to the first differences of the elements.

%C Compositions map bijectively to nonnegative integers by assigning each run of k consecutive 1's (or 0's) in binary expansion of n with summand k in the composition.

%C The graph of this sequence is quite interesting.

%H Antti Karttunen, <a href="/A129594/b129594.txt">Table of n, a(n) for n = 0..1023</a>

%H Antti Karttunen, <a href="/A129594/a129594_1.txt">Python-program for computing this and related sequences.</a>

%H A. Karttunen et al., <a href="http://oeis.org/wiki/Run-length_encoding">Run-length encoding</a>, OEIS Wiki.

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e a(8) = 11, as 8 is 1000 in binary, mapping to composition 3+1 (we scan the binary expansion from the least to the most significant end), which maps to partition 3+3, whose conjugate-partition is 2+2+2, yielding composition 2+1+1, which maps to binary 1011, 11 in decimal. a(13) = 14, as 13 is 1101 in binary, mapping to composition 1+1+2, which maps to the partition 1+1+2, whose conjugate-partition is 1+3, yielding composition 1+3, which maps to binary 1110, 14 in decimal. a(11) = 8 and a(14) = 13, as taking the conjugate of a partition is a self-inverse operation.

%o (MIT/GNU Scheme)

%o (define (A129594 n) (if (zero? n) n (ascpart_to_binexp (conjugate-partition (binexp_to_ascpart n)))))

%o (define (conjugate-partition ascpart) (let loop ((conjpart (list)) (ascpart ascpart)) (cond ((null? ascpart) conjpart) (else (loop (cons (length ascpart) conjpart) (delete-matching-items! (map -1+ ascpart) zero?))))))

%o (define (binexp_to_ascpart n) (let ((runlist (reverse! (binexp->runcount1list n)))) (PARTSUMS (cons (car runlist) (map -1+ (cdr runlist))))))

%o (define (ascpart_to_binexp ascpart) (runcount1list->binexp (reverse! (cons (car ascpart) (map 1+ (DIFF ascpart))))))

%o (define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))

%o (define (runcount1list->binexp lista) (let loop ((lista lista) (s 0) (state 1)) (cond ((null? lista) s) (else (loop (cdr lista) (+ (* s (expt 2 (car lista))) (* state (- (expt 2 (car lista)) 1))) (- 1 state))))))

%o (define (DIFF a) (map - (cdr a) (reverse! (cdr (reverse a)))))

%o (define (PARTSUMS a) (cdr (reverse! (fold-left (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a))))

%Y a(n) = A075158(A122111(1+A075157(n)) - 1). See A129595 for another kind of encoding of integer partitions.

%Y Sequences related to partitions encoded in this way:

%Y Cf. A227189 (parts of partitions listed on separate rows of the array).

%Y Cf. A005811 (number of parts in the partition).

%Y Cf. A136480 (for n>= 1, the smallest part).

%Y Cf. A227185 (the largest part).

%Y Cf. A227183 (sum of parts).

%Y Cf. A227184 (product of parts).

%Y Note that this permutation maps between A005811 and A227185 as follows: A005811(n) = A227185(a(n)) and vice versa: A227185(n) = A005811(a(n)). On the other hand, it keeps A227183 fixed, as A227183(n) = A227183(a(n)).

%Y Cf. also A226062.

%K nonn,look

%O 0,3

%A _Antti Karttunen_, May 01 2007

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:44 EDT 2024. Contains 371265 sequences. (Running on oeis4.)