A389508 Number of integer compositions of n with no maximal runs of the form (k)^k for any k.

1, 0, 2, 2, 4, 8, 14, 25, 48, 85, 160, 288, 534, 973, 1792, 3277, 6017, 11026, 20225, 37077, 68002, 124670, 228641, 419211, 768739, 1409581, 2584755, 4739564, 8690891, 15936209, 29221983, 53583564, 98255140, 180168067, 330370382, 605792537, 1110828543, 2036901137

Offset

0,3

Comments

These are compositions whose maximal runs R all satisfy length(R) != first(R).

No composition containing a single 1 is counted. Thus in computations, no permutation of any partition with a single 1 needs to be explored. - Michael S. Branicky, Oct 12 2025

Links

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

Formula

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

Example

The a(0) = 1 through a(6) = 14 compositions:
  ()  .  (2)   (3)    (4)     (5)      (6)
         (11)  (111)  (112)   (23)     (24)
                      (211)   (32)     (33)
                      (1111)  (113)    (42)
                              (311)    (114)
                              (1112)   (222)
                              (2111)   (411)
                              (11111)  (1113)
                                       (2112)
                                       (3111)
                                       (11112)
                                       (11211)
                                       (21111)
                                       (111111)

Mathematica

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

Prog

(Python)
from itertools import groupby
from sympy.combinatorics.partitions import IntegerPartition
from sympy.utilities.iterables import partitions, multiset_permutations
def compositions(n): yield from (c for p in partitions(n) for c in multiset_permutations(IntegerPartition(p).partition))
def cond(t): return not any(len(list(g))==k for k, g in groupby(t))
def a(n): return sum(1 for p in partitions(n) if not (1 in p and p[1] == 1) for c in multiset_permutations(IntegerPartition(p).partition) if cond(c))
print([a(n) for n in range(20)]) # Michael S. Branicky, Oct 12 2025
(PARI)
A_x(N) = {Vec(1/(1 - sum(k=1, N, (-x^(k^2)+x^(k+k^2)+x^k)/(-x^(k^2)+x^(k+k^2)+1))) + O('x^(N+1)))} \\ John Tyler Rascoe, Nov 14 2025

Crossrefs

For partitions instead of compositions we have A276429, ranks A325130.

A complimentary version is A301503, ranks A389530.

These compositions are ranked by A389531.

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.

Cf. A000041, A000079, A008965, A032020, A070211, A098504, A124767, A175342, A238279, A325551.

Sequence in context: A000018 A357307 A306604 * A354784 A075126 A300998

Adjacent sequences: A389505 A389506 A389507 * A389509 A389510 A389511

Keyword

nonn

Author

Gus Wiseman, Oct 09 2025

Extensions

a(21)-a(33) from Michael S. Branicky, Oct 12 2025

a(34)-a(37) from John Tyler Rascoe, Nov 14 2025

Status

approved