A373952 Number of integer compositions of n whose run-compression sums to 3.

0, 0, 0, 3, 2, 4, 5, 6, 6, 9, 8, 10, 11, 12, 12, 15, 14, 16, 17, 18, 18, 21, 20, 22, 23, 24, 24, 27, 26, 28, 29, 30, 30, 33, 32, 34, 35, 36, 36, 39, 38, 40, 41, 42, 42, 45, 44, 46, 47, 48, 48, 51, 50, 52, 53, 54, 54, 57, 56, 58, 59, 60, 60, 63, 62, 64, 65, 66

Offset

0,4

Comments

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

Links

John Tyler Rascoe, Table of n, a(n) for n = 0..10000

Formula

G.f.: x^3 * (3-x-x^2-x^3)/((1-x)*(1-x^2)*(1-x^3)). - John Tyler Rascoe, Jul 01 2024

Example

The a(3) = 3 through a(9) = 9 compositions:
  (3)   (112)  (122)   (33)     (1222)    (11222)    (333)
  (12)  (211)  (221)   (1122)   (2221)    (22211)    (12222)
  (21)         (1112)  (2211)   (11122)   (111122)   (22221)
               (2111)  (11112)  (22111)   (221111)   (111222)
                       (21111)  (111112)  (1111112)  (222111)
                                (211111)  (2111111)  (1111122)
                                                     (2211111)
                                                     (11111112)
                                                     (21111111)

Mathematica

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], Total[First/@Split[#]]==3&]], {n, 0, 10}]

Prog

(PARI)
A_x(N)={my(x='x+O('x^N)); concat([0, 0, 0], Vec(x^3 *(3-x-x^2-x^3)/((1-x)*(1-x^2)*(1-x^3))))}
A_x(50) \\ John Tyler Rascoe, Jul 01 2024

Crossrefs

For partitions we appear to have A137719.

Column k = 3 of A373949, rows-reversed A373951.

The compression-sum statistic is represented by A373953, difference A373954.

A003242 counts compressed compositions (anti-runs).

A011782 counts compositions.

A114901 counts compositions with no isolated parts.

A116861 counts partitions by compressed sum, by compressed length A116608.

A124767 counts runs in standard compositions, anti-runs A333381.

A240085 counts compositions with no unique parts.

A333755 counts compositions by compressed length.

A373948 represents the run-compression transformation.

Cf. A037201 (halved A373947), A106356, A124762, A238130, A238279, A238343, A285981, A333213, A333489, A373950.

Sequence in context: A039858 A035558 A089401 * A035044 A359663 A171086

Adjacent sequences: A373949 A373950 A373951 * A373953 A373954 A373955

Keyword

nonn

Author

Gus Wiseman, Jun 29 2024

Extensions

a(26) onwards from John Tyler Rascoe, Jul 01 2024

Status

approved