A391628 Number of integer compositions of n that are the first sums of more than one composition.

0, 0, 1, 1, 1, 2, 3, 4, 6, 8, 12, 16, 23, 31, 44, 59, 83, 111, 155, 207, 287, 383, 528, 704, 966, 1287, 1759, 2342, 3190, 4245, 5765, 7668, 10387, 13810, 18665, 24807, 33462, 44459, 59866, 79518, 106909, 141968, 190608, 253058, 339341, 450431, 603345, 800718

Offset

1,6

Comments

The first sums of a nonempty sequence (a, b, c, d, ...) are (a+b, b+c, c+d, ...).

Also the number of compositions c of n such that there is more than one integer b such that the b-based partial alternating sums of c are all positive. Here, the b-based partial alternating sums of a finite sequence q are given by pas(q,b)_j = (-1)^j * b + Sum_{i=1..j} (-1)^(i+j) * q_i. This is a signed version of the partial sums transformation, inverse to the "first sums" transformation.

Are all these compositions free of 2?

From Christian Sievers, Jan 09 2026: (Start)

The terms in these compositions are all at least 3: for a different composition to have the same first sums as (a, b, c, d, e, ...) has, it has to be of the form (a+k, b-k, c+k, d-k, e+k, ...) for some nonzero integer k. For a first sum to be 2, it has to come from two adjacent 1 terms. But then the second composition giving the same first sums would have a term 1-|k| < 1, which is not allowed.

Equivalently, number of compositions of n that are the first sums of a composition with terms that are at least 2 at every other position. (End)

Links

Christian Sievers, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (0,2,1,0,-1,-1,-1).

Formula

G.f.: (x^3+x^4-x^5-x^6)/(1-2*x^2-x^3+x^5+x^6+x^7). - Christian Sievers, Jan 11 2026

Example

The composition (2,4,3) is not the first sums of any composition, so (2,4,3) is not counted under a(9).
The composition (3,4,3) is the first sums of (1,2,2,1) only, so (3,4,3) is not counted under a(10).
The composition (3,3,5) is the first sums of (1,2,1,4) and (2,1,2,3), so (3,3,5) is counted under a(11).
The a(3) = 1 through a(11) = 12 compositions are:
  (3)  (4)  (5)  (6)    (7)    (8)    (9)      (10)     (11)
                 (3,3)  (3,4)  (3,5)  (3,6)    (3,7)    (3,8)
                        (4,3)  (4,4)  (4,5)    (4,6)    (4,7)
                               (5,3)  (5,4)    (5,5)    (5,6)
                                      (6,3)    (6,4)    (6,5)
                                      (3,3,3)  (7,3)    (7,4)
                                               (3,3,4)  (8,3)
                                               (4,3,3)  (3,3,5)
                                                        (3,4,4)
                                                        (4,3,4)
                                                        (4,4,3)
                                                        (5,3,3)

Mathematica

pas[y_, k_]:=Table[(-1)^j*k+Sum[(-1)^(i+j)*y[[i]], {i, j}], {j, 0, Length[y]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Select[Table[pas[#, b], {b, 0, Max[#]}], Min@@#>=1&]]>1&]], {n, 1, 10}]

Prog

(PARI) a(n)=polcoef((x^3+x^4-x^5-x^6)/(1-2*x^2-x^3+x^5+x^6+x^7)+O(x*x^n), n) \\ Christian Sievers, Jan 11 2026

Crossrefs

The compositions are ranked by A391627.

For a unique choice we have A391644, ranks A390745.

For no choices we have A391680, ranks A390677.

For nonnegative sequences we have A391682, ranks A391623.

For at least one choice we have A391683, ranks A390676 (union of A390568).

A011782 counts compositions.

A357213 counts compositions by sum of first sums.

A390432 lists first sums of standard compositions.

A390673 ranks compositions with distinct first sums, counted by A390567.

A390678 ranks compositions with no 1's that are not first sums.

A391621 counts nonnegative sequences with standard first sums.

A391642 counts compositions with standard first sums.

Cf. A008965, A022340, A342527, A066099, A070211, A390446, A390675, A391235, A391983.

Sequence in context: A241344 A064428 A052810 * A364964 A320315 A364956

Adjacent sequences: A391625 A391626 A391627 * A391629 A391630 A391631

Keyword

nonn,easy

Author

Gus Wiseman, Jan 07 2026

Extensions

a(21) onward from Christian Sievers, Jan 11 2026

Status

approved