cp's OEIS Frontend

A composition of n is a finite sequence of positive integers with sum n.

A composition of n is a finite sequence of positive integers summing to n.

Compare to the definition of knapsack partitions (A108917).

The n-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

a(n) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.

From David W. Wilson, Aug 17 2007: (Start)

An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.

An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.

A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)

Positions where A143824 increases (see also A227590). - N. J. A. Sloane, Apr 08 2016

From Gus Wiseman, May 17 2019: (Start)

Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:

0: ()

1: (1)

3: (2,1)

6: (2,3,1)

11: (3,1,5,2)

17: (4,2,3,7,1)

Representatives of corresponding Golomb rulers are:

{0}

{0,1}

{0,2,3}

{0,2,5,6}

{0,3,4,9,11}

{0,4,6,9,16,17}

(End)

Wanted: a recurrence. Are any of A169940-A169954 related to any other entries in the OEIS?

Leading entry in row n of triangle in A169940. Also the number of Sidon sets A with min(A) = 0 and max(A) = n. Odd for all n since {0,n} is the only symmetric Golomb ruler, and reversal preserves the Golomb property. Bounded from above by A032020 since the ruler {0 < r_1 < ... < r_t < n} gives rise to a composition of n: (r_1 - 0, r_2 - r_1, ... , n - r_t) with distinct parts. - Tomas Boothby, May 15 2012

Also the number of compositions of n such that every restriction to a subinterval has a different sum. This is a stronger condition than all distinct consecutive subsequences having a different sum (cf. A325676). - Gus Wiseman, May 16 2019

Number of permutations p of {1,2,...,n} such that p(k)-k takes exactly two distinct values. Example: a(4)=4 because we have 4123, 3412, 2143 and 2341. - Max Alekseyev and Emeric Deutsch, Dec 22 2006

Number of solutions to the Diophantine equation xy + yz = n, with x,y,z >= 1.

In other words, number of ways to write n = (a + b) * k for positive integers a, b, k. - Gus Wiseman, Mar 25 2021

Not the same as A184396(n): a(66) = 136 while A184396(66) = 137. - Wesley Ivan Hurt, Dec 26 2013

From Gus Wiseman, Mar 25 2021: (Start)

Also the number of compositions of n into an even number of parts with alternating parts equal. These are finite even-length sequences q of positive integers summing to n such that q(i) = q(i+2) for all possible i. For example, the a(2) = 1 through a(8) = 11 compositions are:

(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)

(2,1) (2,2) (2,3) (2,4) (2,5) (2,6)

(3,1) (3,2) (3,3) (3,4) (3,5)

(1,1,1,1) (4,1) (4,2) (4,3) (4,4)

(5,1) (5,2) (5,3)

(1,2,1,2) (6,1) (6,2)

(2,1,2,1) (7,1)

(1,1,1,1,1,1) (1,3,1,3)

(2,2,2,2)

(3,1,3,1)

(1,1,1,1,1,1,1,1)

The odd-length version is A062968.

The version with alternating parts weakly decreasing is A114921, or A342528 if odd-length compositions are included.

The version with alternating parts unequal is A342532, or A224958 if odd-length compositions are included (unordered: A339404/A000726).

Allowing odd lengths as well as even gives A342527.

(End)

Inverse Möbius transform of n-1. - Wesley Ivan Hurt, Jun 29 2024

A044813 contains those positive integers that when written in binary, have all run-lengths (of both 0's and 1's) distinct.

A175414 contains those positive integers in A175413 that are not in A044813. (A175414 contains those positive integers that when written in binary, at least one run of 0's is the same length as one run of 1's, even though all run of 0 are of distinct length and all runs of 1's are of distinct length.)

Also numbers whose binary expansion has all distinct runs (not necessarily run-lengths). - Gus Wiseman, Feb 21 2022