0,3

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.

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.

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.

The graph of this sequence is quite interesting.

A. Karttunen, Table of n, a(n) for n = 0..1023

Index entries for sequences that are permutations of the natural numbers

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.

(MIT Scheme:)

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

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

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

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

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

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

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

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

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

Sequence in context: A054086 A163329 A105025 this_sequence A158441 A102787 A014193

Adjacent sequences: A129591 A129592 A129593 this_sequence A129595 A129596 A129597

nonn

Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), May 01 2007