A374251 Irregular triangle read by rows where row n is the run-compression of the n-th composition in standard order.

1, 2, 1, 3, 2, 1, 1, 2, 1, 4, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 5, 4, 1, 3, 2, 3, 1, 2, 3, 2, 1, 2, 1, 2, 2, 1, 1, 4, 1, 3, 1, 1, 2, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 6, 5, 1, 4, 2, 4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 1, 2, 4, 2, 3, 1, 2, 2, 1, 2, 1, 3

Offset

1,2

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, run-compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has run-compression (1,2,1).

Links

Table of n, a(n) for n=1..84.

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

Example

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

Mathematica

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[First/@Split[stc[n]], {n, 100}]

Crossrefs

Last column is A001511.

First column is A065120.

Row-lengths are A124767.

Using prime indices we get A304038, row-sums A066328.

Row n has A334028(n) distinct elements.

Rows are ranked by A373948 (standard order).

Row-sums are A373953.

A003242 counts run-compressed compositions, i.e., anti-runs, ranks A333489.

A007947 (squarefree kernel) represents run-compression of multisets.

A037201 run-compresses first differences of primes, halved A373947.

A066099 lists the parts of compositions in standard order.

A116861 counts partitions by sum of run-compression.

A238279 and A333755 count compositions by number of runs.

A373949 counts compositions by sum of run-compression, opposite A373951.

Cf. A000120, A070939, A106356, A124762, A233564, A238130, A238343, A272919, A333381, A333382, A333627, A373954, A374250.

Sequence in context: A114890 A374629 A145327 * A255191 A277818 A324607

Adjacent sequences: A374248 A374249 A374250 * A374252 A374253 A374254

Keyword

nonn,tabf

Author

Gus Wiseman, Jul 09 2024

Status

approved