A389509 Number of integer compositions of n whose maximal runs R all satisfy length(R) >= first(R).

1, 1, 1, 1, 2, 3, 5, 7, 10, 15, 22, 32, 47, 70, 103, 153, 227, 335, 494, 729, 1078, 1593, 2355, 3478, 5138, 7592, 11218, 16570, 24479, 36167, 53435, 78947, 116638, 172321, 254588, 376135, 555710, 821016, 1212986, 1792089, 2647665, 3911714, 5779246, 8538361

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Formula

G.f.: 1/(1 - Sum_{k>0} ( x^(k^2)/(1 - x^k + x^(k^2)) )). - John Tyler Rascoe, Oct 09 2025

Example

The composition c = (1,1,3,3,3,2,2,1) has maximal runs ((1,1),(3,3,3),(2,2),(1)), which all satisfy length >= first, so c is counted under n = 16.
The a(1) = 1 through a(8) = 10 compositions:
  (1)  (11)  (111)  (22)    (122)    (222)     (1222)     (2222)
                    (1111)  (221)    (1122)    (2221)     (11222)
                            (11111)  (1221)    (11122)    (12221)
                                     (2211)    (11221)    (22211)
                                     (111111)  (12211)    (111122)
                                               (22111)    (111221)
                                               (1111111)  (112211)
                                                          (122111)
                                                          (221111)
                                                          (11111111)

Maple

b:= proc(n, l) option remember; `if`(n=0, 1, add(
     `if`(i=l, 0, add(b(n-i*j, i), j=i..n/i)), i=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..43);  # Alois P. Heinz, Dec 17 2025

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@Table[Length[k]>=First[k], {k, Split[#]}]&]], {n, 0, 15}]

Prog

(PARI)
A_x(N) = {Vec(1/(1 - sum(k=1, N/2, x^(k^2)/(1 - x^k + x^(k^2)))) + O('x^(N+1)))} \\ John Tyler Rascoe, Oct 09 2025

Crossrefs

For partitions instead of compositions we have A117144, ranks A324525.

An opposite version is A389510, ranked by A389514.

A strict version is A389511, ranked by A389515.

A complimentary version is A389512, ranked by A389516.

These compositions are ranked by A389513.

A003242 counts anti-run compositions, ranks A333489.

A005811 counts runs in binary expansion.

A011782 counts compositions, standard order A066099.

A098124 counts compositions with max part = length, ranks A389532.

A238130 and A333755 count compositions by maximal runs, partitions A365676.

A353860 counts collapsible compositions, ranks A354908.

Cf. A000079, A008965, A032020, A070211, A098504, A124767, A175342, A238279, A276429, A301503, A389508.

Sequence in context: A301756 A170877 A003410 * A362757 A018133 A261081

Adjacent sequences: A389506 A389507 A389508 * A389510 A389511 A389512

Keyword

nonn

Author

Gus Wiseman, Oct 09 2025

Extensions

a(24) onwards from John Tyler Rascoe, Oct 09 2025

Status

approved