cp's OEIS Frontend

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

%I A129594 #30 Jan 26 2014 13:31:50
%S A129594 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 A129594 30,17,18,29,26,21,43,52,59,36,35,60,51,44,47,48,63,32,39,56,55,40,41,
%U A129594 54,57,38,33,62,49,46,45,50,61,34,37,58,53,42,84,107,116,75,68,123
%N A129594 Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n.
%C A129594 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 A129594 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 A129594 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 A129594 The graph of this sequence is quite interesting.
%H A129594 Antti Karttunen, <a href="/A129594/b129594.txt">Table of n, a(n) for n = 0..1023</a>
%H A129594 Antti Karttunen, <a href="/A129594/a129594_1.txt">Python-program for computing this and related sequences.</a>
%H A129594 A. Karttunen et al., <a href="http://oeis.org/wiki/Run-length_encoding">Run-length encoding</a>, OEIS Wiki.
%H A129594 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A129594 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 A129594 (MIT/GNU Scheme)
%o A129594 (define (A129594 n) (if (zero? n) n (ascpart_to_binexp (conjugate-partition (binexp_to_ascpart n)))))
%o A129594 (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 A129594 (define (binexp_to_ascpart n) (let ((runlist (reverse! (binexp->runcount1list n)))) (PARTSUMS (cons (car runlist) (map -1+ (cdr runlist))))))
%o A129594 (define (ascpart_to_binexp ascpart) (runcount1list->binexp (reverse! (cons (car ascpart) (map 1+ (DIFF ascpart))))))
%o A129594 (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 A129594 (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 A129594 (define (DIFF a) (map - (cdr a) (reverse! (cdr (reverse a)))))
%o A129594 (define (PARTSUMS a) (cdr (reverse! (fold-left (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a))))
%Y A129594 a(n) = A075158(A122111(1+A075157(n)) - 1). See A129595 for another kind of encoding of integer partitions.
%Y A129594 Sequences related to partitions encoded in this way:
%Y A129594 Cf. A227189 (parts of partitions listed on separate rows of the array).
%Y A129594 Cf. A005811 (number of parts in the partition).
%Y A129594 Cf. A136480 (for n>= 1, the smallest part).
%Y A129594 Cf. A227185 (the largest part).
%Y A129594 Cf. A227183 (sum of parts).
%Y A129594 Cf. A227184 (product of parts).
%Y A129594 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 A129594 Cf. also A226062.
%K A129594 nonn,look
%O A129594 0,3
%A A129594 _Antti Karttunen_, May 01 2007