A389601 Number of integer compositions of n with all distinct 0-prepended first differences.

1, 1, 2, 2, 5, 10, 14, 28, 40, 67, 106, 184, 293, 481, 733, 1198, 1811, 2817, 4366, 6767, 10402, 15956, 24378, 36624, 55512, 82360, 123719, 183573, 274312, 404868, 601108, 882082, 1300140, 1892324, 2764721

Offset

0,3

Links

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

Example

The composition c = (2,3,1) has 0-prepended first differences (2,1,-2), which are all distinct, so c is counted under a(6).
The composition d = (2,1,3) has 0-prepended first differences (2,-1,2), which are not all distinct, so d is not counted under a(6).
The a(1) = 1 through a(6) = 14 compositions:
  (1)  (2)    (3)    (4)      (5)      (6)
       (1,1)  (2,1)  (1,3)    (1,4)    (1,5)
                     (2,2)    (2,3)    (3,3)
                     (3,1)    (3,2)    (4,2)
                     (2,1,1)  (4,1)    (5,1)
                              (1,1,3)  (1,1,4)
                              (1,3,1)  (1,3,2)
                              (2,1,2)  (1,4,1)
                              (2,2,1)  (2,3,1)
                              (3,1,1)  (3,1,2)
                                       (4,1,1)
                                       (1,1,3,1)
                                       (1,3,1,1)
                                       (2,1,1,2)

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@Differences[Prepend[#, 0]]&]], {n, 0, 15}]

Prog

(Python)
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 diffs(t): return [t[i]-t[i-1] for i in range(1, len(t))]
def a(n): return sum(1 for c in compositions(n) if len(t:=diffs([0]+c))==len(set(t)))
print([a(n) for n in range(20)]) # Michael S. Branicky, Oct 25 2025

Crossrefs

For equal instead of distinct differences we have A007862, ranks A389732.

Subsets of this type are counted by A303664, non 0-prepended A364465.

For multisets instead of compositions we have A325324, ranks A325367.

For partitions instead of compositions we have A325325, ranks A325368.

The non 0-prepended version is A325545, ranks A389597.

These compositions are ranked by A389734.

The complement is counted by A389744, ranks A389738.

A000120 gives length of standard composition.

A011782 counts compositions.

A175342 counts arithmetic progressions, ranks A389731, subsets A051336.

A358133 lists first differences of standard compositions, 0-prepended A389733.

Cf. A000740, A049988, A070211, A325547, A325557, A389741, A389742, A389743.

Sequence in context: A246864 A262924 A392702 * A331540 A329676 A391595

Adjacent sequences: A389598 A389599 A389600 * A389602 A389603 A389604

Keyword

nonn,more

Author

Gus Wiseman, Oct 23 2025

Extensions

a(26)-a(34) from Michael S. Branicky, Oct 25 2025

Status

approved