A373948 Run-compression encoded as a transformation of compositions in standard order.

0, 1, 2, 1, 4, 5, 6, 1, 8, 9, 2, 5, 12, 13, 6, 1, 16, 17, 18, 9, 20, 5, 22, 5, 24, 25, 6, 13, 12, 13, 6, 1, 32, 33, 34, 17, 4, 37, 38, 9, 40, 41, 2, 5, 44, 45, 22, 5, 48, 49, 50, 25, 52, 13, 54, 13, 24, 25, 6, 13, 12, 13, 6, 1, 64, 65, 66, 33, 68, 69, 70, 17, 72

Offset

0,3

Comments

The k-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 k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define the (run-) compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).

For the present sequence, the a(n)-th composition in standard order is obtained by compressing the n-th composition in standard order.

Links

Table of n, a(n) for n=0..72.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Formula

A029837(a(n)) = A373953(n).

A000120(a(n)) = A124767(n).

Example

The standard compositions and their compressions begin:
   0: ()        -->  0: ()
   1: (1)       -->  1: (1)
   2: (2)       -->  2: (2)
   3: (1,1)     -->  1: (1)
   4: (3)       -->  4: (3)
   5: (2,1)     -->  5: (2,1)
   6: (1,2)     -->  6: (1,2)
   7: (1,1,1)   -->  1: (1)
   8: (4)       -->  8: (4)
   9: (3,1)     -->  9: (3,1)
  10: (2,2)     -->  2: (2)
  11: (2,1,1)   -->  5: (2,1)
  12: (1,3)     --> 12: (1,3)
  13: (1,2,1)   --> 13: (1,2,1)
  14: (1,1,2)   -->  6: (1,2)
  15: (1,1,1,1) -->  1: (1)

Mathematica

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[First/@Split[stc[n]]], {n, 0, 30}]

Crossrefs

Positions of 1's are A000225.

The image is A333489, counted by A003242.

Sum of standard composition for a(n) is given by A373953, length A124767.

A037201 gives compression of first differences of primes, halved A373947.

A066099 lists the parts of all compositions in standard order.

A114901 counts compositions with no isolated parts.

A116861 counts partitions by compressed sum, by length A116608.

A240085 counts compositions with no unique parts.

A333755 counts compositions by compressed length.

A373949 counts compositions by compressed sum, opposite A373951.

Cf. A106356, A124762, A238130, A238279, A272919, A333381, A333382, A333627, A373952, A373954.

Sequence in context: A144774 A326056 A365689 * A074720 A323456 A326058

Adjacent sequences: A373945 A373946 A373947 * A373949 A373950 A373951

Keyword

nonn

Author

Gus Wiseman, Jun 24 2024

Status

approved